計算理論

なし

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

離散数学

形式言語理論(オートマトン理論)

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

(a)授業内容
第1回:チューリング機械(武永)
第2回:チューリング機械の変形と計算能力(武永)
第3回:ランダムアクセス機械、計算可能性とチャーチの提唱(武永)
第4回:判定可能、認識可能な言語とその性質(武永)
第5回:認識可能でない言語(武永)
第6回:判定可能でない言語(武永)
第7回:帰着(武永)
第8回:帰着を用いた判定・認識不可能性の証明(武永)
第9回:計算量理論イントロ:組合せ論的モデル:比較計算量(垂井)
第10回:組合せ論的モデル:質問計算量(垂井)
第11回:組合せ論的モデル:通信計算量(垂井)
第12回:計算量理論核心部:時間計算量、多項式時間計算(垂井)
第13回:クラスP、クラスNP、P vs NP予想(垂井)
第14回:NP完全性の説明(垂井)
第15回:NP完全性の証明(垂井)

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

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

試験は行わず、武永担当前半部については2回のレポート課題、垂井担当後半部については、4回か5回のレポート課題(宿題)の結果に基づいて評価を行なう。 計算可能性および計算量理論の基本的概念について理解することが合格の最低条件である。

武永担当前半と垂井担当後半、それぞれの評価の単純平均を授業全体の評価とする。

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

なし

なし