可计算性与计算复杂性导引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.6 Ackermann函数 28

2.7 字函数的可计算性 33

习题 36

第三章 通用程序 39

3.1 程序的代码 39

3.2 停机问题 41

3.3 通用程序 42

3.4 递归可枚举集 45

习题 48

第四章 Turing机 50

4.1 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

第七章 正则语言 90

7.1 Chomsky谱系 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.1 Turing机的运行时间和工作空间 138

9.2 计算复杂性类 141

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

习题 147

第十章 NP完全性 148

10.1 P与NP 148

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

10.3 Cook定理 154

10.4 若干NP完全问题 158

10.5 coNP 169

习题 171

第十一章 NP类的外面 172

11.1 PSPACE完全问题 172

11.2 一个难解问题 177

习题 180

第十二章 P类的里面 181

12.1 若干例子 181

12.2 对数空间变换 184

12.3 NL类 185

12.4 P完全问题 189

习题 193

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

13.1 随机算法 194

13.2 随机复杂性类 201

习题 208

习题解答 209

附录 243

附录A 记号 243

附录B 中英文名词索引 248

参考文献 256