图书介绍
可计算性与计算复杂性导引PDF|Epub|txt|kindle电子书版本网盘下载
- 张立昂编著 著
- 出版社： 北京市：北京大学出版社
- ISBN：9787301177686
- 出版时间：2011
- 标注页数：256页
- 文件大小：10MB
- 文件页数：266页
- 主题词：电子计算机－可计算性－高等学校－教材；电子计算机－计算复杂性－高等学校－教材
PDF下载
下载说明
可计算性与计算复杂性导引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与NP148
10.2 多项式时间变换和NP完全性152
10.3 Cook定理154
10.4 若干NP完全问题158
10.5 coNP169
习题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