計算論 (Computation Theory)  木曜日3時限

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

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



講義予定と講義資料(変更することがあります)
2017.04.13休講  
2017.04.20第1回 イントロダクション
2017.04.27第2回 有限オートマトンと正規表現 Finite-state automata and regular expressions
2017.05.01休講  
2017.05.11第3回 有限オートマトンで受理できない言語 Languages not accepted by finite-state automata 
2017.05.18第4回 プッシュダウンオートマトンと文脈自由文法,
プッシュダウンオートマトンで受理できない言語
Pushdown automata and context-free grammars,
Lauguages not accepted by pushdown automata
2017.05.25第5回 Turing機械とその変型 Turing machines and their variants
2017.06.01第6回 判定可能性 Decidability
2017.06.08休講
2017.06.15第7回 判定不可能な言語(1) Undecidable languages (1)
2017.06.22第8回 判定不可能な言語(2) Undecidable languages (2)
2017.06.29第9回 ポストの対応問題 Post correspondence problem
2017.07.06休講  
2017.07.20第10回 まとめ