計算理論導引（第2版）

出版者的話
專家指導委員會
譯者序
譯者簡介
第1版前言
第2版前言
第0章 緒論
0.1    自動機、可計算性與復(fù)雜性
0.2    數(shù)學概念和術(shù)語
0.3    定義、定理和證明
0.4    證明的類型
練習
問題
習題選解
第一部分 自動機與語言
第1章 正則語言
1.1    有窮自動機
1.2    非確定性
1.3    正則表達式
1.4    非正則語言
練習
問題
習題選解
第2章 上下文無關(guān)文法
2.1    上下文無關(guān)文法概述
2.2    下推自動機
2.3    非上下文無關(guān)語言
練習
問題
習題選解
第二部分 可計算性理論
第3章 丘奇-圖靈論題
3.1    圖靈機
3.2    圖靈機的變形
3.3    算法的定義
練習
問題
習題選解
第4章 可判定性
4.1    可判定語言
4.2    停機問題
練習
問題
習題選解
第5章 可歸約性
5.1    語言理論中的不可判定問題
5.2    一個簡單的不可判定問題
5.3    映射可歸約性
練習
問題
習題選解
第6章 可計算性理論的高級專題
6.1    遞歸定理
6.2    邏輯理論的可判定性
6.3    圖靈可歸約性
6.4    信息的定義
練習
問題
習題選解
第三部分 復(fù)雜性理論
第7章 時間復(fù)雜性
7.1    度量復(fù)雜性
7.2    P類
7.3    NP類
7.4    NP完全性
7.5    幾個NP完全問題
練習
問題
習題選解
第8章 空間復(fù)雜性
8.1    薩維奇定理
8.2    PSPACE類
8.3    PSPACE完全性
8.4    L類和NL類
8.5    NL完全性
8.6    NL等于coNL
練習
問題
習題選解
第9章 難解性
9.1    層次定理
9.2    相對化
9.3    電路復(fù)雜性
練習
問題
習題選解
第10章 復(fù)雜性理論高級專題
10.1    近似算法
10.2    概率算法
10.3    交錯式
10.4    交互式證明系統(tǒng)
10.5    并行計算
10.6    密碼學
練習
問題
習題選解
參考文獻
索引