可计算性与计算复杂性导引 第2版2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

可计算性与计算复杂性导引 第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与NP147

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

10.3 Cook定理153

10.4若干NP完全问题157

10.5 coNP168

习题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