计算理论导引 原书第3版PDF电子书下载
- 电子书积分:11 积分如何计算积分?
- 作 者:(美)迈克尔·西普塞(MichaelSipser)著;段磊,唐常杰等译
- 出 版 社:北京:机械工业出版社
- 出版年份:2015
- ISBN:9787111499718
- 页数:298 页
第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序列和多元组 4
0.2.3函数和关系 4
0.2.4图 6
0.2.5字符串和语言 8
0.2.6布尔逻辑 9
0.2.7数学名词汇总 10
0.3定义、定理和证明 11
0.4证明的类型 13
0.4.1构造性证明 13
0.4.2反证法 14
0.4.3归纳法 15
练习 16
问题 17
习题选解 18
第一部分 自动机与语言 20
第1章 正则语言 20
1.1有穷自动机 20
1.1.1有穷自动机的形式化定义 22
1.1.2有穷自动机举例 23
1.1.3计算的形式化定义 25
1.1.4设计有穷自动机 25
1.1.5正则运算 27
1.2非确定性 29
1.2.1非确定型有穷自动机的形式化定义 32
1.2.2 NFA与DFA的等价性 33
1.2.3在正则运算下的封闭性 36
1.3正则表达式 38
1.3.1正则表达式的形式化定义 38
1.3.2与有穷自动机的等价性 40
1.4非正则语言 46
练习 50
问题 54
习题选解 58
第2章 上下文无关文法 62
2.1上下文无关文法概述 62
2.1.1上下文无关文法的形式化定义 63
2.1.2上下文无关文法举例 64
2.1.3设计上下文无关文法 65
2.1.4歧义性 66
2.1.5乔姆斯基范式 67
2.2下推自动机 68
2.2.1下推自动机的形式化定义 69
2.2.2下推自动机举例 70
2.2.3与上下文无关文法的等价性 72
2.3非上下文无关语言 77
2.4确定型上下文无关语言 79
2.4.1 DCFL的性质 82
2.4.2确定型上下文无关文法 83
2.4.3 DPDA和DCFG的关系 91
2.4.4语法分析和LR(k)文法 94
练习 96
问题 98
习题选解 100
第二部分 可计算性理论 104
第3章 丘奇-图灵论题 104
3.1图灵机 104
3.1.1图灵机的形式化定义 105
3.1.2图灵机的例子 107
3.2图灵机的变形 110
3.2.1多带图灵机 111
3.2.2非确定型图灵机 112
3.2.3枚举器 113
3.2.4与其他模型的等价性 114
3.3算法的定义 114
3.3.1希尔伯特问题 115
3.3.2描述图灵机的术语 116
练习 118
问题 119
习题选解 120
第4章 可判定性 122
4.1可判定语言 122
4.1.1与正则语言相关的可判定性问题 122
4.1.2与上下文无关语言相关的可判定性问题 124
4.2不可判定性 126
4.2.1对角化方法 127
4.2.2不可判定语言 130
4.2.3一个图灵不可识别语言 131
练习 132
问题 133
习题选解 134
第5章 可归约性 136
5.1语言理论中的不可判定问题 136
5.2一个简单的不可判定问题 143
5.3映射可归约性 148
5.3.1可计算函数 148
5.3.2映射可归约性的形式化定义 148
练习 151
问题 151
习题选解 153
第6章 可计算性理论的高级专题 155
6.1递归定理 155
6.1.1自引用 155
6.1.2递归定理的术语 157
6.1.3应用 158
6.2逻辑理论的可判定性 159
6.2.1一个可判定的理论 161
6.2.2一个不可判定的理论 163
6.3图灵可归约性 164
6.4信息的定义 165
6.4.1极小长度的描述 166
6.4.2定义的优化 168
6.4.3不可压缩的串和随机性 168
练习 170
问题 170
习题选解 171
第三部分 复杂性理论 174
第7章 时间复杂性 174
7.1度量复杂性 174
7.1.1大O和小o记法 174
7.1.2分析算法 176
7.1.3模型间的复杂性关系 178
7.2 P类 180
7.2.1多项式时间 180
7.2.2 P中的问题举例 181
7.3 NP类 184
7.3.1 NP中的问题举例 187
7.3.2 P与NP问题 188
7.4 NP完全性 188
7.4.1多项式时间可归约性 189
7.4.2 NP完全性的定义 191
7.4.3库克-列文定理 192
7.5几个NP完全问题 196
7.5.1顶点覆盖问题 196
7.5.2哈密顿路径问题 198
7.5.3子集和问题 201
练习 202
问题 203
习题选解 207
第8章 空间复杂性 208
8.1萨维奇定理 209
8.2 PSPACE类 210
8.3 PSPACE完全性 211
8.3.1 TQBF问题 212
8.3.2博弈的必胜策略 214
8.3.3广义地理学 215
8.4 L类和NL类 219
8.5 N L完全性 220
8.6 NL等于coNL 222
练习 224
问题 224
习题选解 226
第9章 难解性 228
9.1层次定理 228
9.2相对化 236
9.3电路复杂性 238
练习 244
问题 245
习题选解 245
第10章 复杂性理论高级专题 247
10.1近似算法 247
10.2概率算法 248
10.2.1 BPP类 249
10.2.2素数性 250
10.2.3只读一次的分支程序 254
10.3交错式 257
10.3.1交错式时间与交错式空间 257
10.3.2多项式时间层次 260
10.4交互式证明系统 260
10.4.1图的非同构 261
10.4.2模型的定义 261
10.4.3 IP= PSPACE 263
10.5并行计算 270
10.5.1一致布尔电路 270
10.5.2 NC类 272
10.5.3 P完全性 273
10.6密码学 273
10.6.1密钥 274
10.6.2公钥密码系统 275
10.6.3单向函数 275
10.6.4天窗函数 277
练习 277
问题 278
习题选解 278
参考文献 280
索引 284
- 《SQL与关系数据库理论》(美)戴特(C.J.Date) 2019
- 《计算机网络与通信基础》谢雨飞,田启川编著 2019
- 《大学计算机实验指导及习题解答》曹成志,宋长龙 2019
- 《联吡啶基钌光敏染料的结构与性能的理论研究》李明霞 2019
- 《情报学 服务国家安全与发展的现代情报理论》赵冰峰著 2018
- 《英汉翻译理论的多维阐释及应用剖析》常瑞娟著 2019
- 《新课标背景下英语教学理论与教学活动研究》应丽君 2018
- 《党员干部理论学习培训教材 理论热点问题党员干部学习辅导》(中国)胡磊 2018
- 《虚拟流域环境理论技术研究与应用》冶运涛蒋云钟梁犁丽曹引等编著 2019
- 《当代翻译美学的理论诠释与应用解读》宁建庚著 2019
- 《SQL与关系数据库理论》(美)戴特(C.J.Date) 2019
- 《魔法销售台词》(美)埃尔默·惠勒著 2019
- 《看漫画学钢琴 技巧 3》高宁译;(日)川崎美雪 2019
- 《优势谈判 15周年经典版》(美)罗杰·道森 2018
- 《社会学与人类生活 社会问题解析 第11版》(美)James M. Henslin(詹姆斯·M. 汉斯林) 2019
- 《海明威书信集:1917-1961 下》(美)海明威(Ernest Hemingway)著;潘小松译 2019
- 《迁徙 默温自选诗集 上》(美)W.S.默温著;伽禾译 2020
- 《上帝的孤独者 下 托马斯·沃尔夫短篇小说集》(美)托马斯·沃尔夫著;刘积源译 2017
- 《巴黎永远没个完》(美)海明威著 2017
- 《剑桥国际英语写作教程 段落写作》(美)吉尔·辛格尔顿(Jill Shingleton)编著 2019
- 《指向核心素养 北京十一学校名师教学设计 英语 七年级 上 配人教版》周志英总主编 2019
- 《北京生态环境保护》《北京环境保护丛书》编委会编著 2018
- 《高等教育双机械基础课程系列教材 高等学校教材 机械设计课程设计手册 第5版》吴宗泽,罗圣国,高志,李威 2018
- 《指向核心素养 北京十一学校名师教学设计 英语 九年级 上 配人教版》周志英总主编 2019
- 《高等院校旅游专业系列教材 旅游企业岗位培训系列教材 新编北京导游英语》杨昆,鄢莉,谭明华 2019
- 《中国十大出版家》王震,贺越明著 1991
- 《近代民营出版机构的英语函授教育 以“商务、中华、开明”函授学校为个案 1915年-1946年版》丁伟 2017
- 《新工业时代 世界级工业家张毓强和他的“新石头记”》秦朔 2019
- 《智能制造高技能人才培养规划丛书 ABB工业机器人虚拟仿真教程》(中国)工控帮教研组 2019
- 《AutoCAD机械设计实例精解 2019中文版》北京兆迪科技有限公司编著 2019