计算理论导引 第2版PDF电子书下载
- 电子书积分:11 积分如何计算积分?
- 作 者:(美)塞普瑟(Sipser,M.)著;唐常杰等译
- 出 版 社:北京:机械工业出版社
- 出版年份:2006
- ISBN:7111190289
- 页数:269 页
第0章 绪论 1
0.1 自动机、可计算性与复杂性 1
0.1.1 计算复杂性理论 1
0.1.2 可计算性理论 2
0.1.3 自动机理论 2
0.2 数学概念和术语 2
0.2.1 集合 2
0.2.2 序列和多元组 3
0.2.3 函数和关系 4
0.2.4 图 6
0.2.5 字符串和语言 7
0.2.6 布尔逻辑 8
0.2.7 数学名词汇总 9
0.3 定义、定理和证明 10
0.4 证明的类型 12
0.4.1 构造性证明 12
0.4.2 反证法 13
0.4.3 归纳法 13
练习 15
问题 16
习题选解 17
第一部分 自动机与语言 19
第1章 正则语言 19
1.1 有穷自动机 19
1.1.1 有穷自动机的形式化定义 21
1.1.2 有穷自动机举例 22
1.1.3 计算的形式化定义 24
1.1.4 设计有穷自动机 24
1.1.5 正则运算 26
1.2 非确定性 28
1.2.1 非确定型有穷自动机的形式化定义 31
1.2.2 NFA与DFA的等价性 32
1.2.3 在正则运算下的封闭性 35
1.3 正则表达式 37
1.3.1 正则表达式的形式化定义 38
1.3.2 与有穷自动机的等价性 39
1.4 非正则语言 46
练习 50
问题 54
习题选解 58
第2章 上下文无关文法 63
2.1 上下文无关文法概述 63
2.1.1 上下文无关文法的形式化定义 64
2.1.2 上下文无关文法举例 65
2.1.3 设计上下文无关文法 65
2.1.4 歧义性 66
2.1.5 乔姆斯基范式 67
2.2 下推自动机 69
2.2.1 下推自动机的形式化定义 70
2.2.2 下推自动机举例 70
2.2.3 与上下文无关文法的等价性 72
2.3 非上下文无关语言 76
练习 79
问题 81
习题选解 83
第二部分 可计算性理论 87
第3章 丘奇-图灵论题 87
3.1 图灵机 87
3.1.1 图灵机的形式化定义 88
3.1.2 图灵机的例子 89
3.2 图灵机的变形 93
3.2.1 多带图灵机 93
3.2.2 非确定型图灵机 94
3.2.3 枚举器 95
3.2.4 与其他模型的等价性 96
3.3 算法的定义 97
3.3.1 希尔伯特问题 97
3.3.2 描述图灵机的术语 98
练习 100
问题 101
习题选解 102
第4章 可判定性 104
4.1 可判定语言 104
4.1.1 与正则语言相关的可判定性问题 104
4.1.2 与上下文无关语言相关的可判定性问题 106
4.2 停机问题 108
4.2.1 对角化方法 109
4.2.2 停机问题是不可判定的 111
4.2.3 一个图灵不可识别语言 113
练习 114
问题 115
习题选解 116
第5章 可归约性 118
5.1 语言理论中的不可判定问题 118
5.2 一个简单的不可判定问题 124
5.3 映射可归约性 129
5.3.1 可计算函数 129
5.3.2 映射可归约性的形式定义 129
练习 132
问题 132
习题选解 134
第6章 可计算性理论的高级专题 136
6.1 递归定理 136
6.1.1 自引用 136
6.1.2 递归定理的术语 138
6.1.3 应用 139
6.2 逻辑理论的可判定性 140
6.2.1 一个可判定的理论 141
6.2.2 一个不可判定的理论 143
6.3 图灵可归约性 145
6.4 信息的定义 146
6.4.1 极小长度的描述 146
6.4.2 定义的优化 148
6.4.3 不可压缩的串和随机性 148
练习 150
问题 150
习题选解 151
第三部分 复杂性理论 153
第7章 时间复杂性 153
7.1 度量复杂性 153
7.1.1 大O和小o记法 153
7.1.2 分析算法 155
7.1.3 模型间的复杂性关系 157
7.2 P类 158
7.2.1 多项式时间 158
7.2.2 P中的问题举例 159
7.3 NP类 163
7.3.1 NP中的问题举例 165
7.3.2 P与NP问题 166
7.4 NP完全性 166
7.4.1 多项式时间可归约性 167
7.4.2 NP完全性的定义 169
7.4.3 库克-列文定理 169
7.5 几个NP完全问题 173
7.5.1 顶点覆盖问题 174
7.5.2 哈密顿路径问题 175
7.5.3 子集和问题 178
练习 180
问题 181
习题选解 185
第8章 空间复杂性 187
8.1 萨维奇定理 188
8.2 PSPACE类 189
8.3 PSPACE完全性 190
8.3.1 TQBF问题 190
8.3.2 博弈的必胜策略 193
8.3.3 广义地理学 194
8.4 L类和NL类 197
8.5 NL完全性 198
8.6 NL等于coNL 200
练习 202
问题 202
习题选解 204
第9章 难解性 206
9.1 层次定理 206
9.2 相对化 213
9.3 电路复杂性 215
练习 220
问题 221
习题选解 222
第10章 复杂性理论高级专题 223
10.1 近似算法 223
10.2 概率算法 224
10.2.1 BPP类 224
10.2.2 素数性 226
10.2.3 只读一次的分支程序 229
10.3 交错式 232
10.3.1 交错式时间与交错式空间 233
10.3.2 多项式时间层次 235
10.4 交互式证明系统 236
10.4.1 图的非同构 236
10.4.2 模型的定义 237
10.4.3 IP=PSPACE 238
10.5 并行计算 244
10.5.1 一致布尔电路 245
10.5.2 NC类 246
10.5.3 P完全性 247
10.6 密码学 247
10.6.1 密钥 248
10.6.2 公钥密码系统 249
10.6.3 单向函数 249
10.6.4 天窗函数 250
练习 251
问题 251
习题选解 252
参考文献 254
索引 259
- 《SQL与关系数据库理论》(美)戴特(C.J.Date) 2019
- 《计算机网络与通信基础》谢雨飞,田启川编著 2019
- 《大学计算机实验指导及习题解答》曹成志,宋长龙 2019
- 《联吡啶基钌光敏染料的结构与性能的理论研究》李明霞 2019
- 《情报学 服务国家安全与发展的现代情报理论》赵冰峰著 2018
- 《英汉翻译理论的多维阐释及应用剖析》常瑞娟著 2019
- 《新课标背景下英语教学理论与教学活动研究》应丽君 2018
- 《党员干部理论学习培训教材 理论热点问题党员干部学习辅导》(中国)胡磊 2018
- 《虚拟流域环境理论技术研究与应用》冶运涛蒋云钟梁犁丽曹引等编著 2019
- 《当代翻译美学的理论诠释与应用解读》宁建庚著 2019
- 《指向核心素养 北京十一学校名师教学设计 英语 七年级 上 配人教版》周志英总主编 2019
- 《北京生态环境保护》《北京环境保护丛书》编委会编著 2018
- 《高等教育双机械基础课程系列教材 高等学校教材 机械设计课程设计手册 第5版》吴宗泽,罗圣国,高志,李威 2018
- 《指向核心素养 北京十一学校名师教学设计 英语 九年级 上 配人教版》周志英总主编 2019
- 《高等院校旅游专业系列教材 旅游企业岗位培训系列教材 新编北京导游英语》杨昆,鄢莉,谭明华 2019
- 《中国十大出版家》王震,贺越明著 1991
- 《近代民营出版机构的英语函授教育 以“商务、中华、开明”函授学校为个案 1915年-1946年版》丁伟 2017
- 《新工业时代 世界级工业家张毓强和他的“新石头记”》秦朔 2019
- 《智能制造高技能人才培养规划丛书 ABB工业机器人虚拟仿真教程》(中国)工控帮教研组 2019
- 《AutoCAD机械设计实例精解 2019中文版》北京兆迪科技有限公司编著 2019