授業科目名 計算論
履修期 春 2単位 履修基準年度 3年
授業目的
与えられた問題に対して効率の良いプログラムが作れるのか，そもそも本質的に作れないのかという問いをどのように扱えばよいのだろうか．本講義は，このような問いを理論的に扱う計算理論の基礎を理解することを目的とする．
到達目標
計算モデル，計算可能性，計算の複雑さ（計算量）について，基本的な概念を理解する．
授業計画
第1回ガイダンス，基礎的概念
第2回チューリングマシン（1）（定義と性質）
第3回チューリングマシン（2）（非決定性チューリングマシン）
第4回計算可能性（1）（認識可能性）
第5回計算可能性（2）（判定可能性）
第6回計算複雑性（1）（計算量の定義）
第7回計算複雑性（2）（クラスPとクラスNP）
第8回計算複雑性（3）（帰着）
第9回計算複雑性（4）（NP完全性）
第10回計算複雑性（5）（領域量，様々な計算量クラス）
第11回確率アルゴリズム
第12回近似アルゴリズム（1）
第13回近似アルゴリズム（2）
第14回先進的な話題，総合演習