計算理論の基礎 (ケイサンリロンのキソ)

原題は、
Introduction to the Theory of Computation

オートマトンと(形式)言語の理論、
計算可能性の理論、
及び計算の複雑さの理論について、
Ｓｉｐｓｅｒ教授のＭＩＴでの講義ノートを
元にまとめられた
計算の理論のテキスト。

----------------------------------------------------------------

【目次】

第０章　序論
0.1　オートマトン，計算可能性，複雑さ
0.2　数学的概念や用語
0.3　定義，定理，証明
0.4　証明のタイプ

第1部　オートマトンと言語
第1章　正規言語
1.1　有限オートマトン
1.2　非決定性
1.3　正規表現
1.4　非正規言語

第2章　文脈自由文法
2.1　文脈自由文法
2.2　プッシュダウン・オートマトン
2.3　非文脈自由言語

第2部　計算可能性の理論
第3章　Church-Turingの提唱
3.1　Turing機械
3.2　Turing機械の変型
3.3　アルゴリズムの定義

第4章　判定可能性
4.1　判定可能な言語
4.2　停止問題

第5章　帰着可能性
5.1　言語理論における判定不可能問題
5.2　単純な判定不可能問題
5.3　写像帰着可能性

第6章　計算可能性の理論における先進的な話題
6.1　再帰定理
6.2　数理論理における判定可能性
6.3　Turing帰着可能性
6.4　情報の定義

第3部　複雑さの理論
第7章　時間の複雑さ
7.1　複雑さの測定
7.2　クラスP
7.3　クラスNP
7.4　NP完全性
7.5　他のNP完全問題

第8章　領域の複雑さ
8.1　Savitchの定理
8.2　クラスPSPACE
8.3　PSPACE完全
8.4　クラスLとクラスNL
8.5　NL完全性
8.6　NLとcoNLの等価性

第9章　問題の扱いにくさ
9.1　階層定理
9.2　相対化
9.3　回路の複雑さ

第10章　計算の複雑さの理論における先進的な話題
10.1　近似アルゴリズム
10.2　確率的アルゴリズム
10.3　交替性
10.4　対話証明系
10.5　並列計算
10.6　暗号

----------------------------------------------------------------

• http://www.amazon.co.jp/exec/obidos/...