计算理论导引: 原书第3版

封面\n书名\n版权\n前言\n目录\n第0章  绪论\n0.1自动机、可计算性与复杂性\n0.1.1计算复杂性理论\n0.1.2可计算性理论\n0.1.3自动机理论\n0.2数学概念和术语\n0.2.1集合\n0.2.2序列和多元组\n0.2.3函数和关系\n0.2.4图\n0.2.5字符串和语言\n0.2.6布尔逻辑\n0.2.7数学名词汇总\n0.3定义、定理和证明\n0.4证明的类型\n0.4.1构造性证明\n0.4.2反证法\n0.4.3归纳法\n练习\n问题\n习题选解\n第一部分  自动机与语言\n第1章  正则语言\n1.1有穷自动机\n1.1.1有穷自动机的形式化定义\n1.1.2有穷自动机举例\n1.1.3计算的形式化定义\n1.1.4设计有穷自动机\n1.1.5正则运算\n1.2非确定性\n1.2.1非确定型有穷自动机的形式化定义\n1.2.2  NFA与DFA的等价性\n1.2.3在正则运算下的封闭性\n1.3正则表达式\n1.3.1正则表达式的形式化定义\n1.3.2与有穷自动机的等价性\n1.4非正则语言\n练习\n问题\n习题选解\n第2章  上下文无关文法\n2.1上下文无关文法概述\n2.1.1上下文无关文法的形式化定义\n2.1.2上下文无关文法举例\n2.1.3设计上下文无关文法\n2.1.4歧义性\n2.1.5乔姆斯基范式\n2.2下推自动机\n2.2.1下推自动机的形式化定义\n2.2.2下推自动机举例\n2.2.3与上下文无关文法的等价性\n2.3非上下文无关语言\n2.4确定型上下文无关语言\n2.4.1  DCFL的性质\n2.4.2确定型上下文无关文法\n2.4.3  DPDA和DCFG的关系\n2.4.4语法分析和LR（k）文法\n练习\n问题\n习题选解\n第二部分  可计算性理论\n第3章  丘奇-图灵论题\n3.1图灵机\n3.1.1图灵机的形式化定义\n3.1.2图灵机的例子\n3.2图灵机的变形\n3.2.1多带图灵机\n3.2.2非确定型图灵机\n3.2.3枚举器\n3.2.4与其他模型的等价性\n3.3算法的定义\n3.3.1希尔伯特问题\n3.3.2描述图灵机的术语\n练习\n问题\n习题选解\n第4章  可判定性\n4.1可判定语言\n4.1.1与正则语言相关的可判定性问题\n4.1.2与上下文无关语言相关的可判定性问题\n4.2不可判定性\n4.2.1对角化方法\n4.2.2不可判定语言\n4.2.3一个图灵不可识别语言\n练习\n问题\n习题选解\n第5章  可归约性\n5.1语言理论中的不可判定问题\n5.2一个简单的不可判定问题\n5.3映射可归约性\n5.3.1可计算函数\n5.3.2映射可归约性的形式化定义\n练习\n问题\n习题选解\n第6章  可计算性理论的高级专题\n6.1递归定理\n6.1.1自引用\n6.1.2递归定理的术语\n6.1.3应用\n6.2逻辑理论的可判定性\n6.2.1一个可判定的理论\n6.2.2一个不可判定的理论\n6.3图灵可归约性\n6.4信息的定义\n6.4.1极小长度的描述\n6.4.2定义的优化\n6.4.3不可压缩的串和随机性\n练习\n问题\n习题选解\n第三部分  复杂性理论\n第7章  时间复杂性\n7.1度量复杂性\n7.1.1大O和小o记法\n7.1.2分析算法\n7.1.3模型间的复杂性关系\n7.2  P类\n7.2.1多项式时间\n7.2.2  P中的问题举例\n7.3  NP类\n7.3.1  NP中的问题举例\n7.3.2  P与NP问题\n7.4  NP完全性\n7.4.1多项式时间可归约性\n7.4.2  NP完全性的定义\n7.4.3库克-列文定理\n7.5几个NP完全问题\n7.5.1顶点覆盖问题\n7.5.2哈密顿路径问题\n7.5.3子集和问题\n练习\n问题\n习题选解\n第8章  空间复杂性\n8.1萨维奇定理\n8.2  PSPACE类\n8.3  PSPACE完全性\n8.3.1  TQBF问题\n8.3.2博弈的必胜策略\n8.3.3广义地理学\n8.4  L类和NL类\n8.5  N L完全性\n8.6 NL等于coNL\n练习\n问题\n习题选解\n第9章  难解性\n9.1层次定理\n9.2相对化\n9.3电路复杂性\n练习\n问题\n习题选解\n第10章  复杂性理论高级专题\n10.1近似算法\n10.2概率算法\n10.2.1  BPP类\n10.2.2素数性\n10.2.3只读一次的分支程序\n10.3交错式\n10.3.1交错式时间与交错式空间\n10.3.2多项式时间层次\n10.4交互式证明系统\n10.4.1图的非同构\n10.4.2模型的定义\n10.4.3  IP= PSPACE\n10.5并行计算\n10.5.1一致布尔电路\n10.5.2  NC类\n10.5.3  P完全性\n10.6密码学\n10.6.1密钥\n10.6.2公钥密码系统\n10.6.3单向函数\n10.6.4天窗函数\n练习\n问题\n习题选解\n参考文献\n索引