可計算性與計算復雜性導引

第一章程序設計語言少和可計算函數(shù)
1.1預備知識
1.2Church-Turing論題
1.3程序設計語言少
1.4可計算函數(shù)
1.5宏指令
習題
第二章原始遞歸函數(shù)
2.1原始遞歸函數(shù)
2.2原始遞歸謂詞
2.3迭代運算.有界量詞和極小化
2.4配對函數(shù)和Godel數(shù)
2.5原始遞歸運算
2.6Ackermann函數(shù)
2.7字函數(shù)的可計算性
習題
第三章通用程序
3.1程序的代碼
3.2停機問題
3.3通用程序
3.4遞歸可枚舉集
習題
第四章Turing機
4.1Turing機的基本模型
4.2Turing機的各種形式
4.3Turing機與可計算性
4.4Turing機接受的語言
4.5非確定型Turing機
習題
第五章過程與文法
5.1半Thue過程
5.2用半Thue過程模擬Turing機
5.3文法
5.4再論遞歸可枚舉集
5.5部分遞歸函數(shù)
5.6再論Church-Turing論題
習題
第六章不可判定的問題
6.1判定問題
6.2Turing機的停機問題
6.3字問題和Post對應問題
6.4有關文法的不可判定問題
6.5一階邏輯中的判定問題
習題
第七章正則語言
7.1Chomsky譜系
7.2有窮自動機
7.3有窮自動機與正則文法的等價性
7.4正則表達式
7.5非正則語言
習題
第八章上下文無關語言
8.1上下文無關文法
8.2Chomsky范式
8.3Bar-Hillel泵引理
8.4下推自動機
8.5上下文無關文法與下推自動機的等價性
8.6確定型下推自動機
8.7上-F文有關文法
習題
第九章時間復雜性與空間復雜性
9.1Turing機的運行時間和工作空間
9.2計算復雜性類
9.3復雜性類的真包含關系
習題
第十章NP完全性
10.1P與NP
10.2多項式時間變換和NP完全性
10.3Cook定理
10.4若千NP完全問題
10.5coNP
習題
第十一章NP類的外面
11.1PSPACE完全問題
11.2一個難解問題
習題
第十二章P類的里面
12.1若干例子
12.2對數(shù)空間變換
12.3NL類
12.4P完全問題
習題
第十三章隨機算法與隨機復雜性類
13.1隨機算法
13.2隨機復雜性類
習題
附錄
附錄A記號
附錄B中英文名詞索引
參考文獻