計算理論の基礎

計算理論の基礎
著者 Michael Sipser 著渡辺 治 監訳太田 和夫 監訳阿部 正幸 訳植田 広樹 訳田中 圭介 訳藤岡 淳 訳
分野 情報・コンピュータ  > 情報数学
発売日 2000/04/15
ISBN 9784320029484
体裁 B5変・504頁
定価 8,470円 (本体7,700円 + 税10%)
在庫 品切れ・重版未定
  • この本の
    内容
  • 目次
「計算の理論の世界へ、ようこそ!」
 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 暗号

Shopping
ご注文

8,470円
(本体7,700円 + 税10%)

ネット書店で購入

  • Amazon
  • 紀伊國屋書店ウェブストア
  • 楽天ブックス
  • honto
  • HMV&BOOKS online
  • ヨドバシ.com
  • Honya Club.com
  • TSUTAYA オンラインショッピング
  • e-hon 全国書店ネットワーク
  • セブンネットショッピング
  • bookfanプレミアム