概要:
データの表現方法や効率の良いアルゴリズムの実装能力を身につけるため，基本的かつ代表的なアルゴリズムとデータ構造について学習する．
授業の進め方・方法:
原則として，毎回の授業で課題の説明を行い，残りの時間はプログラムを作成する演習時間とする．
注意点:
各授業の後半でプログラミング演習を行なう．課題が授業時間内に終わらないことも予想されるので，自宅にプログラム開発環境を構築することが望ましい．また本科目の単位を修得するための条件など，詳細は最初の授業で説明する．
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 後期 |
| 3rdQ |
| 1週 |
文字列検索（１）力まかせ法とKMP法 |
力まかせ法・KMP法のアルゴリズムを理解し実装できる．
|
| 2週 |
文字列検索（２）BM法 |
BM法のアルゴリズムを理解し実装できる．
|
| 3週 |
ハッシュ関数を利用した検索 |
ハッシュ法のアルゴリズムを理解し実装できる．
|
| 4週 |
木構造の表現法と探索 |
木構造の概念を理解し木構造を応用した簡単なデータ処理機能を実装できる．
|
| 5週 |
グラフ構造を用いた経路探索（１）深さ優先探索 |
深さ優先探索のアルゴリズムを理解し実装できる．
|
| 6週 |
グラフ構造を用いた経路探索（２）幅優先探索 |
幅優先探索のアルゴリズムを理解し実装できる．
|
| 7週 |
中間試験前の総復習 |
学習内容の定着度を確認しながら，これまでの学習内容のポイントを整理する．
|
| 8週 |
中間試験 |
中間試験により，これまでの学習内容の定着度を確認する．
|
| 4thQ |
| 9週 |
グラフ構造を用いた経路探索（３）ダイクストラ法 |
ダイクストラ法のアルゴリズムを理解し実装できる．
|
| 10週 |
グラフ構造を用いた経路探索（４）フロイド法 |
フロイド法のアルゴリズムを理解し実装できる．
|
| 11週 |
動的計画法 |
動的計画法を理解し，動的計画法の概念を利用したアルゴリズムの実装ができる．
|
| 12週 |
セグメント木 |
セグメント木の概念を理解し，セグメント木を用いたアルゴリズムの実装ができる．
|
| 13週 |
平面走査（１） |
平面走査による解法が有効な問題に対して，力任せ法による問題解決のためのプログラムが実装できる．
|
| 14週 |
平面走査（２） |
平面走査の概念を理解し，平面走査のアルゴリズムが実装できる．
|
| 15週 |
期末試験前の総復習 |
学習内容の定着度を確認しながら，学習内容のポイントを整理する．
|
| 16週 |
期末試験 |
|
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | プログラミング | 与えられた問題に対して、それを解決するためのソースプログラムを記述できる。 | 3 | |
| 要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを設計できる。 | 1 | |
| ソフトウェア | アルゴリズムの概念を説明できる。 | 4 | 後15 |
| 与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 4 | 後15 |
| 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 4 | 後1 |
| 整列、探索など、基本的なアルゴリズムについて説明できる。 | 4 | 後15 |
| コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 4 | 後15 |
| 同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 4 | 後15 |
| リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 4 | 後4,後5,後6 |
| リスト構造、スタック、キュー、木構造などの基本的なデータ構造を実装することができる。 | 4 | 後4,後5,後6 |
| 情報数学・情報理論 | コンピュータ上での数値の表現方法が誤差に関係することを説明できる。 | 2 | |
| コンピュータ向けの主要な数値計算アルゴリズムの概要や特徴を説明できる。 | 4 | 後1 |
| 分野別の工学実験・実習能力 | 情報系分野【実験・実習能力】 | 情報系【実験・実習】 | 標準的な開発ツールを用いてプログラミングするための開発環境構築ができる。 | 3 | 後1 |
| 要求仕様にあったソフトウェア(アプリケーション)を構築するために必要なツールや開発環境を構築することができる。 | 3 | 後1 |