計算論 (Computation Theory)  月曜日1時限

担当: 竹田正幸(大学院システム情報科学研究院)

教科書: Michael Sipser, Introduction to the Theory of Computation
      (邦訳:計算理論の基礎,共立出版株式会社)



講義予定と講義資料(変更することがあります)
2018.04.09休講  
2018.04.16第1回 イントロダクション
2018.04.23第2回 有限オートマトンと正規表現 Finite-state automata and regular expressions
2018.05.07第3回 有限オートマトンで受理できない言語 Languages not accepted by finite-state automata 
2018.05.14第4回 プッシュダウンオートマトンと文脈自由文法 Pushdown automata and context-free grammars
2018.05.21第5回 プッシュダウンオートマトンで受理できない言語 Lauguages not accepted by pushdown automata
2018.05.28第6回 Turing機械とその変型 Turing machines and their variants
2018.06.04第7回 判定可能性 Decidability
2018.06.11第8回 判定不可能な言語(1) Undecidable languages (1)
2018.06.18第9回 判定不可能な言語(2) Undecidable languages (2)
2018.06.25第10回 ポストの対応問題 Post correspondence problem
2018.07.02第11回 まとめ  
2018.07.09第12回