2024年度 秋学期 木曜 1時限（9:00〜10:40）
授業形態: 対面授業
登録コードSIC20500
計算理論を学ぶ意義
オートマトンと正規言語，演習問題の解答例
オートマタの例（1, 2, 3）
正規表現と非決定性有限オートマトン，演習問題の解答例
非正規言語とpumping補題，演習問題の解答例
文脈自由文法と文脈自由言語，演習問題の解答例
Turing機械，演習問題の解答例
Turing機械に関するいい感じのページ（Turing機械をExcelで実現，Turing機械を物理的に実現，Turing機械を木製機械で実現)
前回の続き
アルゴリズムと停止問題
計算問題と多項式時間アルゴリズム
PとNP，NP-完全，NP-困難