データ構造とアルゴリズム２

種々のデータ構造と、それを取り扱う基本的なアルゴリズムを通して、アルゴリズムの設計や解析を行うための基本的な手法を習得する。さらに、その基本手法を応用できる能力を養うことを目指す。

達成目標

1.	基本的なグラフアルゴリズムを理解する（授業計画の1〜7）。
2.	文字列の照合問題のための基本的解法を理解する（授業計画の8〜9）。
3.	各種のアルゴリズム設計手法による代表的な問題解法を理解する（授業計画の10〜14）。

授業計画

1.	グラフアルゴリズム (I)：グラフの表現
2.	グラフアルゴリズム (II)：幅優先探索
3.	グラフアルゴリズム (III)：深さ優先探索
4.	グラフアルゴリズム (IV)：最短経路問題（ダイクストラ法のアルゴリズム）
5.	グラフアルゴリズム (V)：最短経路問題（ダイクストラ法における計算量）
6.	グラフアルゴリズム (VI)：ネットワークフロー、最大流最小カット定理
7.	グラフアルゴリズム (VII)：最大流アルゴリズム
8.	文字列のアルゴリズム(I)：力まかせ法、ラビン・カープ法、KMP法
9.	文字列のアルゴリズム(II)：ボイヤー・ムーア法
10.	アルゴリズムの設計手法(I)：再帰、数学的帰納法、ユークリッドの互除法
11.	アルゴリズムの設計手法(II)：分割統治法、最大値探索問題、充足可能性問題
12.	アルゴリズムの設計手法(III)：動的計画法、フィボナッチ数列、ナップサック問題
13.	アルゴリズムの設計手法(IV)：グリーディ法、硬貨の交換問題、最小全域木問題
14.	アルゴリズムの設計手法(V)：計算の複雑さ
15.	期末試験