可计算性与计算复杂性导引 第2版PDF电子书下载

第一章 程序设计语言？和可计算函数 1

1.1 预备知识 1

1.2 Church-Turing论题 2

1.3程序设计语言？ 3

1.4可计算函数 9

1.5宏指令 10

习题 12

第二章 原始递归函数 13

2.1原始递归函数 13

2.2原始递归谓词 17

2.3迭代运算、有界量词和极小化 18

2.4配对函数和G？del数 22

2.5原始递归运算 24

2.6Ackermann函数 28

2.7字函数的可计算性 33

习题 36

第三章 通用程序 39

3.1程序的代码 39

3.2停机问题 41

3.3通用程序 42

3.4递归可枚举集 45

习题 48

4.1 Turing机的基本模型 50

第四章 Turing机 50

4.2 Turing机的各种形式 55

4.3 Turing机与可计算性 60

4.4 Turing机接受的语言 63

4.5非确定型Turing机 65

习题 67

第五章 过程与文法 69

5.1半Thue过程 69

5.2用半Thue过程模拟Turing机 70

5.3文法 72

5.4再论递归可枚举集 75

5.5部分递归函数 77

5.6再论Church-Turing论题 78

习题 79

第六章 不可判定的问题 80

6.1 判定问题 80

6.2 Turing机的停机问题 81

6.3字问题和Post对应问题 83

6.4有关文法的不可判定问题 86

6.5一阶逻辑中的判定问题 86

习题 89

7.1 Chomsky谱系 90

第七章 正则语言 90

7.2有穷自动机 93

7.3有穷自动机与正则文法的等价性 101

7.4正则表达式 103

7.5非正则语言 109

习题 110

第八章 上下文无关语言 112

8.1上下文无关文法 112

8.2 Chomsky范式 115

8.3 Bar-Hillel泵引理 119

8.4下推自动机 121

8.5上下文无关文法与下推自动机的等价性 126

8.6确定型下推自动机 129

8.7上下文有关文法 134

习题 136

第九章 时间复杂性与空间复杂性 138

9.1Turing机的运行时间和工作空间 138

9.2计算复杂性类 141

9.3复杂性类的真包含关系 144

习题 146

第十章 NP完全性 147

10.1 P与NP 147

10.2多项式时间变换和NP完全性 151

10.3 Cook定理 153

10.4若干NP完全问题 157

10.5 coNP 168

习题 170

第十一章 NP类的外面 171

11.1 PSPACE完全问题 171

11.2一个难解问题 176

习题 179

第十二章 P类的里面 180

12.1若干例子 180

12.2对数空间变换 183

12.3 NL类 185

12.4 P完全问题 189

习题 192

第十三章 随机算法与随机复杂性类 193

13.1随机算法 193

13.2随机复杂性类 200

习题 207

附录 208

附录A 记号 208

附录B 中英文名词索引 213

参考文献 221