计算理论导引-原书第3版_PDF下载[105MB-百度云]西普塞

本书特色

[

本书由计算理论领域的知名权威michaelsipser所撰写。他以独特的视角，系统地介绍了计算理论的三个主要内容：自动机与语言、可计算性理论和计算复杂性理论。作者以清新的笔触、生动的语言给出了宽泛的数学原理，而没有拘泥于某些低层次的细节。在证明之前，均有“证明思路”，帮助读者理解数学形式下蕴涵的概念。本书可作为计算机专业高年级本科生和研究生的教材，也可作为教师和研究人员的参考书。

]

introduction to the theory of computation,3e出版者的话译者序第3版前言第2版前言第1版前言第0章绪论0 1自动机、可计算性与复杂性0 1 1计算复杂性理论0 1 2可计算性理论0 1 3自动机理论0 2数学概念和术语0 2 1集合0 2 2序列和多元组0 2 3函数和关系0 2 4图0 2 5字符串和语言0 2 6布尔逻辑0 2 7数学名词汇总0 3定义、定理和证明0 4证明的类型0 4 1构造性证明0 4 2反证法0 4 3归纳法练习问题习题选解 **部分自动机与语言第1章正则语言1 1有穷自动机1 1 1有穷自动机的形式化定义1 1 2有穷自动机举例1 1 3计算的形式化定义1 1 4设计有穷自动机1 1 5正则运算1 2非确定性1 2 1非确定型有穷自动机的形式化定义1 2 2nfa与dfa的等价性1 2 3在正则运算下的封闭性1 3正则表达式1 3 1正则表达式的形式化定义1 3 2与有穷自动机的等价性1 4非正则语言练习问题习题选解第2章上下文无关文法2 1上下文无关文法概述2 1 1上下文无关文法的形式化定义2 1 2上下文无关文法举例2 1 3设计上下文无关文法2 1 4歧义性2 1 5乔姆斯基范式2 2下推自动机2 2 1下推自动机的形式化定义2 2 2下推自动机举例2 2 3与上下文无关文法的等价性2 3非上下文无关语言2 4确定型上下文无关语言2 4 1dcfl的性质2 4 2确定型上下文无关文法2 4 3dpda和dcfg的关系2 4 4语法分析和lr(k)文法练习问题习题选解第二部分可计算性理论第3章丘奇图灵论题3 1图灵机3 1 1图灵机的形式化定义3 1 2图灵机的例子3 2图灵机的变形3 2 1多带图灵机3 2 2非确定型图灵机3 2 3枚举器3 2 4与其他模型的等价性3 3算法的定义3 3 1希尔伯特问题3 3 2描述图灵机的术语练习问题习题选解第4章可判定性4 1可判定语言4 1 1与正则语言相关的可判定性问题4 1 2与上下文无关语言相关的可判定性问题4 2不可判定性4 2 1对角化方法4 2 2不可判定语言4 2 3一个图灵不可识别语言练习问题习题选解第5章可归约性5 1语言理论中的不可判定问题5 2一个简单的不可判定问题5 3映射可归约性5 3 1可计算函数5 3 2映射可归约性的形式化定义练习问题习题选解第6章可计算性理论的高级专题6 1递归定理6 1 1自引用6 1 2递归定理的术语6 1 3应用6 2逻辑理论的可判定性6 2 1一个可判定的理论6 2 2一个不可判定的理论6 3图灵可归约性6 4信息的定义6 4 1极小长度的描述6 4 2定义的优化6 4 3不可压缩的串和随机性练习问题习题选解第三部分复杂性理论第7章时间复杂性7 1度量复杂性7 1 1大o和小o记法7 1 2分析算法7 1 3模型间的复杂性关系7 2p类7 2 1多项式时间7 2 2p中的问题举例7 3np类7 3 1np中的问题举例7 3 2p与np问题7 4np完全性7 4 1多项式时间可归约性7 4 2np完全性的定义7 4 3库克列文定理7 5几个np完全问题7 5 1顶点覆盖问题7 5 2哈密顿路径问题7 5 3子集和问题练习问题习题选解第8章空间复杂性8 1萨维奇定理8 2pspace类8 3pspace完全性8 3 1tqbf问题8 3 2博弈的必胜策略8 3 3广义地理学8 4l类和nl类8 5nl完全性8 6nl等于conl练习问题习题选解第9章难解性9 1层次定理9 2相对化9 3电路复杂性练习问题习题选解第10章复杂性理论高级专题10 1近似算法10 2概率算法10 2 1bpp类10 2 2素数性10 2 3只读一次的分支程序10 3交错式10 3 1交错式时间与交错式空间10 3 2多项式时间层次10 4交互式证明系统10 4 1图的非同构10 4 2模型的定义10 4 3ip=pspace10 5并行计算10 5 1一致布尔电路10 5 2nc类10 5 3p完全性10 6密码学10 6 1密钥10 6 2公钥密码系统10 6 3单向函数10 6 4天窗函数练习问题习题选解参考文献索引