计算理论导引（第2版）

　　本书是计算理论领域的经典著作，被国外多所大学选用为教材。本书以注重思路、深入引导为特色，系统地介绍计算理论的三大主要内容：自动机与语言、可计算性理论和计算复杂性理论。同时，对可计算性和计算复杂性理论中的某些高级内容作了重点讲解。全书通过启发性的问题、精彩的结果和待解决问题来引导读者挑战此领域中的高层次问题。新版的一大亮点是增加了更多习题、教辅资料和部分习题解答，更加有利于教学。.全书叙述由浅人深、详略得当，重点突出，不拘泥于技术细节。可作为计算机专业高年级本科生和研究生的教材，也可作为相关专业教师和研究人员的参考书。..本书由计算理论领域的知名权威Michael Sipser所撰写。他以独特的视角，系统地介绍了计算理论的三个主要内容：自动机与语言、可计算性理论和计算复杂性理论。绝大部分内容是基本的，同时对可计算性和计算复杂性理论中的某些高级内容进行了重点介绍。作者以清新的笔触、生动的语言给出了宽泛的数学原理，而没有拘泥于某些低层次的细节。在证明之前，均有“证明思路”，帮助读者理解数学形式下蕴涵的概念。同样，对于算法描述，均以直观的文字而非伪代码给出，从而将注意力集中于算法本身，而不是某些模型。新版根据多年来使用本书的教师和学生的建议进行了改进，并对课堂测试题进行了全面的更新，每章末均有样例解答。...

　　作者：Michael SipserMichael Sipser麻省理工学院应用数学系教授，计算机科学和人工智能实验室（CSAIL）成员。他从事理论计算机科学与其他数学课程的教学工作25年，目前为数学系主任。他痴迷于复杂性理论，喜欢复杂性理论的教学工作。.

出版者的话
专家指导委员会
译者序
译者简介
第1版前言
第2版前言
第0章 绪论
0.1    自动机、可计算性与复杂性
0.2    数学概念和术语
0.3    定义、定理和证明
0.4    证明的类型
练习
问题
习题选解
第一部分 自动机与语言
第1章 正则语言
1.1    有穷自动机
1.2    非确定性
1.3    正则表达式
1.4    非正则语言
练习
问题
习题选解
第2章 上下文无关文法
2.1    上下文无关文法概述
2.2    下推自动机
2.3    非上下文无关语言
练习
问题
习题选解
第二部分 可计算性理论
第3章 丘奇-图灵论题
3.1    图灵机
3.2    图灵机的变形
3.3    算法的定义
练习
问题
习题选解
第4章 可判定性
4.1    可判定语言
4.2    停机问题
练习
问题
习题选解
第5章 可归约性
5.1    语言理论中的不可判定问题
5.2    一个简单的不可判定问题
5.3    映射可归约性
练习
问题
习题选解
第6章 可计算性理论的高级专题
6.1    递归定理
6.2    逻辑理论的可判定性
6.3    图灵可归约性
6.4    信息的定义
练习
问题
习题选解
第三部分 复杂性理论
第7章 时间复杂性
7.1    度量复杂性
7.2    P类
7.3    NP类
7.4    NP完全性
7.5    几个NP完全问题
练习
问题
习题选解
第8章 空间复杂性
8.1    萨维奇定理
8.2    PSPACE类
8.3    PSPACE完全性
8.4    L类和NL类
8.5    NL完全性
8.6    NL等于coNL
练习
问题
习题选解
第9章 难解性
9.1    层次定理
9.2    相对化
9.3    电路复杂性
练习
问题
习题选解
第10章 复杂性理论高级专题
10.1    近似算法
10.2    概率算法
10.3    交错式
10.4    交互式证明系统
10.5    并行计算
10.6    密码学
练习
问题
习题选解
参考文献
索引