計算理論の基礎

この書籍は現在お取り扱いできません。

書籍情報
ISBN978-4-320-02948-4
判型B5変型 
ページ数504ページ
発行年月2000年04月
本体価格7,700円
計算理論の基礎 書影
計算理論の基礎

「計算の理論の世界へ,ようこそ!」
 Michael Sipser教授の「Theory of Computation」の講義も,本書と同様に,このフレンドリーな挨拶から始まりました。彼の講義はMIT屈指の名講義で,教室には活気と笑いがあふれていました。2,3回の聴講を考えていた私はその魅力に魅せられて,91年秋学期の全講義に出席することになりました。
 本書は,Sipser教授のMITでの講義ノートをもとにまとめられたものです。計算の理論の主テーマである,オートマトンと言語の理論,計算可能性の理論,そして計算の複雑さの理論をカバーしています。
 「まえがき」を含めて,随所に講義の雰囲気が感じられます。定理を述べたあと直ちに証明に取り かからず,証明のアイディアを与える工夫,証明の失敗例に言及して理解を深めさせるなど,教育的 配慮の行き届いた教科書だと言えましょう。――訳者まえがきより

目次

0章 序論
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 暗号