駆け足で読む『計算理論の基礎』目次

計算理論の基礎 [原著第2版] 1.オートマトンと言語

計算理論の基礎 [原著第2版] 2.計算可能性の理論

計算理論の基礎 [原著第2版] 3.複雑さの理論

• 第１巻：オートマトンと言語、0章以降
  • 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 非文脈自由言語
• 第２巻：計算可能性の理論
  • 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 情報の定義
• 第３巻：複雑さの理論
  • 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 暗号