可計(jì)算性與計(jì)算復(fù)雜性導(dǎo)引

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