単位の認定:

教科書:

スケジュール (括弧内は演習の内容):

10/7 アルゴリズムの設計と解析	擬似言語、実行時間
10/14 基本的な抽象データ型	リスト, スタック, 待ち行列 ( C言語入門 )
10/21 木	二分木, ハフマンコード
10/28 集合の基本操作	ハッシュ, ハッシュの効率、 ( 優先度付き待ち行列 )
11/4 （休講）
11/11 集合の高度な表現方法	２分探索木, その時間解析, MFSET, LCS （２−３木）
11/18 有向グラフ	ダイクストラ, フロイド, DAG, 強成分
11/25 無向グラフ	プリム, クラスカル, 関節点, 最大マッチング （グラフィクス入門）
12/2 ソート 前半	バブルソート, 内挿ソート, 選択ソート, クイックソート, その時間解析
12/9 ソート 後半	ヒープソート, ビンソート, 基数ソート （シェルソート、マージソート）
12/16 文字列 (教科書外。※)	KMPアルゴリズム, BMアルゴリズム
1/13 解析法	再帰方程式の解法 （動的計画法）
1/20 設計法	欲張り、α—β枝刈り、分岐制約探索法、
1/27 [ テスト]

※ 文字列に関しては、岩波講座ソフトウェア科学「アルゴリズムとデータ構造」(石畑清著)のpp.298-321ページを講義する。また、KMPおよびBMアルゴリズムのデモプログラムは ここを参照のこと。

参考:

連絡先: