アルゴリズムとデータ構造 (演習: C scheme )

担当: 五十嵐 健夫
教室: 教養学部 555教室
時間: 火曜日3限(13:00-14:30)

趣旨:
計算機科学の基礎の一つであるアルゴリズムとデータ構造について学ぶ。
ほぼ教科書に沿った内容にする。

単位の認定:

試験による。出席は取らない。

教科書:

情報処理シリーズ11 データ構造とアルゴリズム
A.V. エイホ, J.E. ホップクロフト 著, 大野義夫訳
培風館 (ISBN4-563-00791-9 C3355)

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

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

参考:

2001年度の試験問題: 本試験, 追試験
2002年度の試験問題: 中間試験, 期末試験

連絡先:

五十嵐 健夫 理学部7号館303号室 takeo @ is.s.u-tokyo.ac.jp