計算論
| 授業目的 |
|---|
| 与えられた問題に対して効率の良いプログラムが作れるのか，そもそも本質的に作れないのかという問いをどのように扱えばよいのだろうか．本講義は，このような問いを理論的に扱う計算理論の基礎を理解することを目的とする． |
| 到達目標 |
| 計算モデル，計算可能性，計算の複雑さ（計算量）について，基本的な概念を理解する． |
| 授業計画 | |
|---|---|
| 第1回 | ガイダンス，基礎的概念 【授業外学修】別途指示する演習課題を解くこと． |
| 第2回 | チューリングマシン（1）（定義と性質） 【授業外学修】別途指示する演習課題を解くこと． |
| 第3回 | チューリングマシン（2）（非決定性チューリングマシン） 【授業外学修】別途指示する演習課題を解くこと． |
| 第4回 | 計算可能性（1）（認識可能性） 【授業外学修】別途指示する演習課題を解くこと． |
| 第5回 | 計算可能性（2）（判定可能性） 【授業外学修】別途指示する演習課題を解くこと． |
| 第6回 | 計算複雑性（1）（計算量の定義） 【授業外学修】別途指示する演習課題を解くこと． |
| 第7回 | 計算複雑性（2）（クラスPとクラスNP） 【授業外学修】別途指示する演習課題を解くこと． |
| 第8回 | 計算複雑性（3）（帰着） 【授業外学修】別途指示する演習課題を解くこと． |
| 第9回 | 計算複雑性（4）（NP完全性） 【授業外学修】別途指示する演習課題を解くこと． |
| 第10回 | 計算複雑性（5）（領域量，様々な計算量クラス） 【授業外学修】別途指示する演習課題を解くこと． |
| 第11回 | 確率アルゴリズム 【授業外学修】別途指示する演習課題を解くこと． |
| 第12回 | 近似アルゴリズム 【授業外学修】別途指示する演習課題を解くこと． |
| 第13回 | 先進的な話題（1）（定数時間アルゴリズム，オンラインアルゴリズム，ストリームアルゴリズム） 【授業外学修】別途指示する演習課題を解くこと． |
| 第14回 | 先進的な話題（2）（量子計算，ゼロ知識証明），まとめ 【授業外学修】別途指示する演習課題およびこれまでの演習課題で残したものを解くこと． |
| 【授業外学修】 | 離散数理，データ構造とアルゴリズム，グラフ・ネットワーク理論，最適化理論，数理計画法実習を履修していることが望ましい． 授業中に適宜指示する演習課題に取り組むこと． |