图书介绍
计算理论导引pdf电子书版本下载
- （美）西普塞（Michael Sipser）著；张立昂等译 著
- 出版社： 北京：机械工业出版社
- ISBN：7111075749
- 出版时间：2000
- 标注页数：273页
- 文件大小：14MB
- 文件页数：283页
- 主题词：
PDF下载
下载说明
计算理论导引PDF格式电子书版下载
下载的文件为RAR压缩包。需要使用解压软件进行解压得到PDF格式图书。建议使用BT下载工具Free Download Manager进行下载,简称FDM(免费,没有广告,支持多平台）。本站资源全部打包为BT种子。所以需要使用专业的BT下载软件进行下载。如 BitComet qBittorrent uTorrent等BT下载工具。迅雷目前由于本站不是热门资源。不推荐使用！后期资源热门了。安装了迅雷也可以迅雷进行下载！
（文件页数 要大于 标注页数，上中下等多册电子书除外）
注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具
图书目录
译者序 1
前言 1
第1章 导引 1
1.1 自动机、可计算与复杂性 1
1.1.1 计算复杂性理论 1
1.1.2 可计算性理论 2
1.1.3 自动机理论 2
1.2 数学概念和术语 2
1.2.1 集合 2
1.2.2 序列和多元组 3
1.2.3 函数和关系 4
1.2.4 图 6
1.2.5 字符串和语言 8
1.2.6 布尔逻辑 8
1.2.7 数学名词汇总 9
1.3 定义、定理和证明 10
1.4 证明和类型 13
1.4.1 构造性证明 13
1.4.2 反证法 13
1.4.3 归纳法 14
练习 16
问题 17
第一部分 自动机与语言 19
第2章 正则语言 19
2.1 有穷自动机 19
2.1.1 有穷自动机的形式定义 21
2.1.2 有穷自动机举例 22
2.1.3 计算的形式定义 24
2.1.4 设计有穷自动机 24
2.1.5 正则运算 26
2.2 非确定性 28
2.2.1 非确定型有穷自动机的形式定义 32
2.2.2 NFA与DFA的等价性 33
2.2.3 在正则运算下的封闭性 35
2.3 正则表达式 38
2.3.1 正则表达式的形式定义 39
2.3.2 与有穷自动机的等价性 40
2.4 非正则语言 47
练习 51
问题 55
3.1 上下文无关文法 59
第3章 上下文无关语言 59
3.1.1 上下文无关文法的形式定义 61
3.1.2 上下文无关文法举例 61
3.1.3 设计上下文无关文法 62
3.1.4 歧义性 63
3.1.5 乔姆斯基范式 64
3.2 下推自动机 66
3.2.1 下推自动机的形式定义 67
3.2.2 下推自动机举例 67
3.2.3 与上下文无关文法的等价性 69
3.3 非上下文无关语言 74
练习 77
问题 79
第二部分 可计算性理论 81
第4章 丘奇--图灵论题 81
4.1 图灵机 81
4.1.1 图灵机的形式定义 82
4.1.2 图灵机的例子 84
4.2 图灵机的变形 88
4.2.1 多带图灵机 88
4.2.2 非确定型图灵机 89
4.2.3 枚举器 91
4.3 算法的定义 92
4.3.1 希尔伯特问题 92
4.2.4 与其他模型的等价性 92
4.3.2 描述图灵机的术语 94
练习 96
问题 97
第5章 可判定性 99
5.1 可判定语言 99
5.1.1 与正则语言相关的可判定性问题 99
5.1.2 与上下文无关语言相关的可判定问题 101
5.2.1 对角化方法 104
5.2 停机问题 104
5.2.2 停机问题是不可判定的 107
5.2.3 一个图灵不可识别语言 109
练习 110
问题 111
第6章 可归约性 112
6.1 语言理论中的不可判定问题 112
6.2 一个简单的不可判定问题 119
6.3 映射可归约性 123
6.3.2 映射可归约性的形式定义 124
6.3.1 可计算函数 124
练习 127
问题 127
第7章 可计算性理论的高级专题 129
7.1 递归定理 129
7.1.1 自引用 129
7.1.2 应用递归定理的术语 131
7.1.3 应用 132
7.2 逻辑理论的可判定性 133
7.2.1 一个可判定的理论 135
7.2.2 一个不可判定的理论 137
7.3 图灵可归约性 138
7.4 信息的定义 139
7.4.1 极小长度的描述 140
7.4.2 定义的优化 142
7.4.3 不可压缩的串和随机性 142
练习 144
问题 144
8.1 度量复杂性 147
8.1.1 大O和小o记法 147
第8章 时间复杂性 147
第三部分 复杂性理论 147
8.1.2 分析算法 149
8.1.3 模型间的复杂性关系 151
8.2 P类 153
8.2.1 多项式时间 153
8.2.2 P中的问题举例 154
8.3 NP类 157
8.3.1 NP中的问题举例 160
8.4 NP完全性 161
8.3.2 P与NP问题 161
8.4.1 多项式时间可归约性 162
8.4.2 NP完全性的定义 164
8.4.3 库克--列文定理 165
8.5 几个NP完全问题 169
8.5.1 顶点覆盖问题 169
8.5.2 哈密顿路径问题 170
8.5.3 子集和问题 174
练习 176
问题 177
第9章 空间复杂性 181
9.1 萨维奇定理 182
9.2 PSPACE类 183
9.3 PSPACE完全性 184
9.3.1 问题TQBF 185
9.3.2 博奕的必胜策略 187
9.3.3 广义地理学 188
9.4 L类和NL类 192
9.5 NL完全性 193
9.6 NL等于coNL 195
练习 197
问题 197
10.1 层次定理 200
第10章 难解性 200
10.2 相对化 208
10.3 电路复杂性 211
练习 216
问题 217
第11章 复杂性理论中的高级专题 219
11.1 近似算法 219
11.2 概率算法 220
11.2.1 BPP类 220
11.2.2 素数性 223
11.2.3 只读一次的分支程序 226
11.3 交错式 229
11.3.1 交错式时间与交错式空间 229
11.3.2 多项式时间层次 232
11.4 交互式证明系统 232
11.4.1 图的非同构 233
11.4.2 模型的定义 233
11.4.3 IP=PSPACE 234
11.5 并行计算 242
11.5.1 一致布尔电路 242
11.5.2 NC类 243
11.5.3 P完全性 245
11.6 密码学 245
11.6.1 密钥 245
11.6.2 公钥密码系统 247
11.6.3 单向函数 247
11.6.4 天窗函数 248
练习 249
问题 249
参考文献 251
索引 255