可计算性与计算复杂性导引pdf电子书版本下载

点此进入-本书在线PDF格式电子书下载【推荐-云解压-方便快捷】直接下载PDF格式图书。移动端-PC端通用
种子下载[BT下载速度快] 温馨提示：（请使用BT下载软件FDM进行下载）软件下载地址页 直链下载[便捷但速度慢]   [在线试读本书]   [在线获取解压码]

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

下载的文件为RAR压缩包。需要使用解压软件进行解压得到PDF格式图书。

建议使用BT下载工具Free Download Manager进行下载,简称FDM(免费,没有广告,支持多平台）。本站资源全部打包为BT种子。所以需要使用专业的BT下载软件进行下载。如 BitComet qBittorrent uTorrent等BT下载工具。迅雷目前由于本站不是热门资源。不推荐使用！后期资源热门了。安装了迅雷也可以迅雷进行下载！

（文件页数 要大于 标注页数，上中下等多册电子书除外）

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第一章 程序设计语言？和可计算函数 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