計算理論 I
Theory of Computation I
講義内容
計算理論は， 情報科学において多くの重要な方法論と結果をもたらした。例
えば， 有限オートマトンに関する基礎的な事柄は， 情報科学の多くの分野で
必須の知識となっている。
本講義の前半では， 有限オートマトンと文脈自由文法に話題を絞り， 形式言
語理論のエッセンスを解説する。 後半では， 「計算機で解けない問題がある
のだろうか」「計算機で問題を解くときの， 問題の難しさをはかる尺度はあ
るのだろうか」といった疑問に答えていく。
- 正規言語
- 有限オートマトン（定義， 決定性モデルと非決定性モデルの等価性）
- 正規表現（定義， 有限オートマトンとの等価性）
- 有限オートマトンの簡単化
- 文脈自由言語
- 文脈自由文法（定義， 簡単化， チョムスキー標準形）
- 文脈自由言語の性質
（言語演算に対する閉包性， パンピングレンマ， 認識アルゴリズム）
- 計算可能性
- チューリング機械（定義， 能力を限定／拡張したモデル）
- 決定不能性（対角線論法， 還元による証明法）
- 計算複雑さ
- 計算複雑さの定義とその諸性質
- ＮＰ完全性（Cookの定理， 還元による証明法）
注意：本講義は計算理論の基礎を学んだことのない人を， 対象としています。
既に学部でこのような内容を学んだ人は， 受講しないで下さい。
教科書
J.ホップクロフト・J.ウルマン著，野崎・高橋・町田・山崎訳 ：
オートマトン 言語理論 計算論 I，サイエンス社，1984
参考書
- J.E.Hopcroft and J.D.Ullman : Introduction to Automata Theory, Languages,
and Computation, Addison-Wesley, 1979
（本講義の教科書の原典）
- 富田悦次・横森貴著 : オートマトン・言語理論， 森北出版
（基本となる概念を丁寧に説明したテキスト）
前提とする知識(必ずしも先修条件ではない)
- アルゴリズムとデータ構造（アルゴリズム概論 ）
- ブール代数（計算機構造概論）