概要:
これまでに開発されている，問題解決のための各種のアルゴリズムと，関連するデータ構造について理解すること．そして，プログラミング上の応用問題において，それらを活用できる能力を養うこと．理論だけでなくコーディングも重視していく．
授業の進め方・方法:
・各週の内容は，電子情報工学科学習・教育到達目標(B)＜専門＞の項目に相当する．
・授業は講義・輪講形式で行う．講義中は集中して聴講する．
・「授業計画」における各週の「到達目標」はこの授業で習得する「知識・能力」に相当するものとする．
注意点:
＜到達目標の評価方法と基準＞下記授業計画の「到達目標」を網羅した問題を2回の中間試験，2回の定期試験で出題し，目標の達成度を評価する．各到達目標に関する重みは同じである．合計点の60％の得点で，目標の達成を確認できるレベルの試験を課す．
＜学業成績の評価方法および評価基準＞前期中間・前期末・後期中間・学年末の4回の試験の平均点による評価を80％，プログラミング課題等に対するレポートの評価を20％として学業成績を評価する．ただし，試験の得点が60点に満たない場合は，補講の受講やレポート提出等の後，再試験により再度評価し，合格点の場合は先の試験の得点を60点と見なす．
＜単位修得要件＞学業成績で60点以上を取得すること．
＜あらかじめ要求される基礎知識の範囲＞本教科はプログラミングI，プログラミングII，マイクロコンピュータ基礎，プログラム設計，オペレーティングシステムの学習が基礎となる教科である．また，数学の基本事項について理解していることも必要である．
＜レポート等＞授業中に演習（C++プログラミング）を適宜行う．また，プログラミング課題に対するレポート提出を求める．さらに，それ以外に，計算問題等に対するレポート提出を求めることがある．
＜備考＞データ構造とアルゴリズムに関する理解は，情報工学分野における最も重要な基盤の一つである．具体例で確認・理解すると同時に，数学的な表現を理解できることも必要である．論理的・数学的な思考力を，さらに培っていくことが大切である．本教科は後に学習するソフトウェア工学，人工知能，数値解析の基礎となる教科である．
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
計算のモデル，計算量 |
1. アルゴリズムの基礎概念について説明できる．
|
| 2週 |
再帰的アルゴリズム |
1. アルゴリズムの基礎概念について説明できる．
|
| 3週 |
グラフと木 |
1. アルゴリズムの基礎概念について説明できる．
|
| 4週 |
リスト |
2. 基本データ構造について説明でき，実装することができる．
|
| 5週 |
スタック，キュー |
2. 基本データ構造について説明でき，実装することができる．
|
| 6週 |
ヒープ |
2. 基本データ構造について説明でき，実装することができる．
|
| 7週 |
演習 |
上記1～2
|
| 8週 |
中間試験 |
これまでに学習した内容を説明できる．
|
| 2ndQ |
| 9週 |
バケットソート，素朴なソーティング |
3. ソーティングについて説明でき，実装することができる．
|
| 10週 |
マージソート，クイックソート |
3. ソーティングについて説明でき，実装することができる．
|
| 11週 |
ヒープソート |
3. ソーティングについて説明でき，実装することができる．
|
| 12週 |
2分探索 |
4. 探索について説明でき，実装することができる．
|
| 13週 |
2分探索木 |
4. 探索について説明でき，実装することができる．
|
| 14週 |
ハッシング |
4. 探索について説明でき，実装することができる．
|
| 15週 |
演習 |
上記3～4
|
| 16週 |
|
|
| 後期 |
| 3rdQ |
| 1週 |
素朴なストリングマッチング |
5. ストリングマッチングについて説明できる．
|
| 2週 |
クヌース・モーリス・プラットのアルゴリズム |
5. ストリングマッチングについて説明できる．
|
| 3週 |
ボイヤー・ムーアのアルゴリズム |
5. ストリングマッチングについて説明できる．
|
| 4週 |
離散フーリエ変換 |
6. 高速フーリエ変換について説明できる．
|
| 5週 |
高速フーリエ変換のアルゴリズム |
6. 高速フーリエ変換について説明できる．
|
| 6週 |
グラフの表現，グラフの探索 |
7. グラフのアルゴリズムについて説明でき，実装することができる．
|
| 7週 |
演習 |
上記5～7
|
| 8週 |
中間試験 |
これまでに学習した内容を説明できる．
|
| 4thQ |
| 9週 |
最小スパニング木 |
7. グラフのアルゴリズムについて説明でき，実装することができる．
|
| 10週 |
最短路 |
7. グラフのアルゴリズムについて説明でき，実装することができる．
|
| 11週 |
最大フロー |
7. グラフのアルゴリズムについて説明でき，実装することができる．
|
| 12週 |
分割統治法 |
8. アルゴリズム設計の基本的技法について説明できる．
|
| 13週 |
動的計画法 |
8. アルゴリズム設計の基本的技法について説明できる．
|
| 14週 |
グリーディ法，分枝限定法，局所探索法と発見的アルゴリズム |
8. アルゴリズム設計の基本的技法について説明できる．
|
| 15週 |
演習 |
上記7～8
|
| 16週 |
|
|
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | ソフトウェア | アルゴリズムの概念を説明できる。 | 4 | |
| 与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 4 | |
| 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 4 | |
| 整列、探索など、基本的なアルゴリズムについて説明できる。 | 4 | |
| 時間計算量によってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
| 領域計算量などによってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
| コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 4 | |
| 同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 4 | |
| リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 4 | |
| リスト構造、スタック、キュー、木構造などの基本的なデータ構造を実装することができる。 | 4 | |
| ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。 | 4 | |
| 同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。 | 4 | |