| 教授 | 五十嵐治一 |  |
データ構造とアルゴリズム２ |
Data Structure and Algorithms 2 |
開講部 | 工学部 |
開講学科 | 情報工学科 |
開講学年 | 2年次 |
開講時期 | 後期 |
単位数 | 2 |
単位区分 | 選択必修 |
系列区分 | 専門 |
講義区分 | 講義 |
| 教授 | 五十嵐治一 | |
| 1. | 基本的なグラフアルゴリズムを理解する（授業計画の1〜7）。 |
| 2. | 文字列の照合問題のための基本的解法を理解する（授業計画の8〜9）。 |
| 3. | 各種のアルゴリズム設計手法による代表的な問題解法を理解する（授業計画の10〜14）。 |
| 【授業計画】 | 【授業時間外課題（予習および復習を含む）】 | |
| 1. | グラフアルゴリズム (I)：グラフの表現 | シラバスを確認しておく。テキストpp.105-110に目を通す。 |
| 2. | グラフアルゴリズム (II)：幅優先探索 | テキストpp.111-113に目を通す。 |
| 3. | グラフアルゴリズム (III)：深さ優先探索 | テキストpp.114-117に目を通す。 |
| 4. | グラフアルゴリズム (IV)：最短経路問題（ダイクストラ法のアルゴリズム） | テキストpp.118-120に目を通す。 |
| 5. | グラフアルゴリズム (V)：最短経路問題（ダイクストラ法における計算量） | 第4回の講義で紹介した例題を自分で解いてみる。テキストpp.121-122に目を通す。 |
| 6. | グラフアルゴリズム (VI)：ネットワークフロー、最大流最小カット定理 | テキストpp.123-127に目を通す。 |
| 7. | グラフアルゴリズム (VII)：最大流アルゴリズム | テキストpp.128-129に目を通す。 |
| 8. | 文字列のアルゴリズム(I)：力まかせ法、ラビン・カープ法、KMP法 | テキストpp.131-140に目を通す。 |
| 9. | 文字列のアルゴリズム(II)：ボイヤー・ムーア法 | テキストpp.141-145に目を通す。 |
| 10. | アルゴリズムの設計手法(I)：再帰、数学的帰納法、ユークリッドの互除法 | テキストpp.147-151に目を通す。 |
| 11. | アルゴリズムの設計手法(II)：分割統治法、最大値探索問題、充足可能性問題 | テキストpp.152-155に目を通す。 |
| 12. | アルゴリズムの設計手法(III)：動的計画法、フィボナッチ数列、ナップサック問題 | テキストpp.156-161に目を通す。 |
| 13. | アルゴリズムの設計手法(IV)：グリーディ法、硬貨の交換問題、最小全域木問題 | テキストpp.162-165に目を通す。 |
| 14. | アルゴリズムの設計手法(V)：計算の複雑さ | オーダ記法（テキストpp.29-30について復習しておく。 |
| 15. | 期末試験と質疑応答 | 第1回〜第14回の講義内容を復習し、よく理解しておく。一般的なアルゴリズムが示されたら、それに従って簡単な例題が解けるぐらいに習熟しておく。 |
| ・ | 後期水曜日12:10-13:00大宮校舎4号館3階講師控室にて。 |
| ・ | 対課題基礎力を育成する科目 |