計算理論

なし

本講義では計算機科学理論のうち、「計算可能性の理論」および「計算量理論」と呼ばれる分野を扱う。計算可能性の理論においては、計算・アルゴリズムとは何かについて考え、実際に計算不可能な問題が存在することを示す。 計算量理論においては、問題を解くために必要な計算時間や記憶容量などを分析する。このような計算可能性の理論、計算量理論の基本的考え方について理解をしてもらうことが本講義の目標である。

離散数学

形式言語理論、アルゴリズム論第一

教科書:なし
参考書:M.Sipser「計算理論の基礎」共立出版
笠井琢美、戸田誠之助「計算の理論」共立出版
渡辺治「計算可能性・計算の複雑さ入門」近代科学社
など

(a)授業内容
第1回:チューリング機械
第2回:チューリング機械の変形と計算能力
第3回:ランダムアクセス機械、計算可能性とチャーチの提唱
第4回:判定可能、認識可能な言語とその性質
第5回:認識可能でない言語
第6回:判定可能でない言語
第7回:帰着
第8回:帰着を用いた判定・認識不可能性の証明
第9回:時間計算量とチューリング機械
第10回:クラスP、クラスNP
第11回:NP完全性
第12回:様々なNP完全問題
第13回:Cook-Levinの定理、領域計算量とクラスPSPACE
第14回:PSPACE完全性、クラス間の関係
第15回:ゲーム・パズルの計算量

(b) 授業の進め方
本講義の前半では、計算可能性の理論について、計算可能/計算不可能とはどのようなことか議論し、実際に計算不可能な問題が存在することを示す。後半では、計算量理論について、応用上も重要なNP完全性に重点を置いて説明する。

授業中に十分理解できなかったと思われる部分は、ノートや教科書等で理解しておくことが望ましい。

試験は行わず、4回程度のレポート課題の結果に基づいて評価を行なう。 計算可能性および計算量理論の基本的概念について理解することが合格の最低条件である。

なるべく授業終了後に教室で相談すること。それ以外はまずメールで連絡してください。

なし

なし