アルゴリズム基礎（前期2単位）

教授 大久保隆夫　教授 大塚玲　教授 松井俊浩

１．授業のねらい・到達目標

コンピュータの内部では与えられた手順に従い膨大な計算処理が行われている。アルゴリズムとはその計算手順のことであり、アルゴリズム論は「より良い」計算手順を研究する学問である。よりよいプログラミング、セキュリティシステムの構築にもアルゴリズムが設計できることが必要であり、また暗号理論等でもアルゴリズム解析は必要となる。本授業はアルゴリズムの設計解析手法、効率的な基本アルゴリズム等について解説する。

２．到達目標

データ構造の基礎、および、データ構造を活用した既存のソーティングアルゴリズムの仕組み、およびその実行時間の違いについて理解する。
また、実行時間の求め方と基礎的なグラフアルゴリズムについて理解する。

３．授業計画

1. Turing機械
2. 判定可能性と判定可能な言語
3. 停止問題
4. 帰着可能性
5. 判定不能な問題、写像帰着
   計算の複雑さ クラスP, クラスNP, NP完全
6. データ構造(1)
   配列、挿入ソート,スタック・キュー、連結リスト
7. データ構造(2)
   ハッシュ表、ハッシュ関数
8. データ構造(3)
   2分探索木、2色木
9. アルゴリズムの解析、漸近記法
10. ソートアルゴリズムと実行時間(1)
    マージソート、クイックソート
11. ソートアルゴリズムと実行時間(2)
    順序統計量、ヒープソート、計数ソート
12. 漸化式の解き方
    置き換え法、再帰木法、分類法
13. グラフアルゴリズムの基礎
    BFS,DFS
14. 統計、数値計算、幾何アルゴリズム
15. 文字列、符号、言語処理、信号処理、アルゴリズムの高速化

４．教科書

• 計算理論の基礎 [原著第2版] 2.計算可能性の理論 Michael Sipser (著), 太田 和夫 (翻訳), 田中 圭介 (翻訳), 阿部 正幸 (翻訳)
• 計算理論の基礎 [原著第2版] 3.複雑さの理論 Michael Sipser (著), 太田 和夫 (翻訳), 田中 圭介 (翻訳), 阿部 正幸 (翻訳)

５．参考書

• ヴィルト著 アルゴリズムとデータ構造、近代科学社、1990年
• Cormen, Leisrson, Rivest, Stein. Introduction to Algorithms 2nd ed., MIT Press, 2001.

６．関連科目

コンピュータ及びプログラミングに関する基礎知識を有することが望ましいが、これらについての知識を適宜補いながら授業を進める。

７．成績評価の方法

到達目標を充足しているかどうかを評価の基準として、それぞれの担当ごとのレポートにより評価する（90％）。
なお、ディスカッションなど講義への積極的な参加も評価対象とする（10％）。