计算理论基础

《计算理论基础(世界有名计算机教材精选)》由辛格编著，本书讨论了计算机科学中的纯粹、引人注目并且普遍存在的基本内容，介绍构成基本计算范例的基本概念、模型、技巧、结果，阐述当今计算机科学家用于建模、讨论和预测算法与计算的思想概念与数学知识。全书共分10章，内容包括数学基础、正则语言、上下文无关语言、可计算枚举语言、非可计算枚举语言、算法可解性、计算复杂性等内容。每章都给出了大量习题，并且在附录提供了部分习题的答案与提示。
《计算理论基础(世界有名计算机教材精选)》可以作为计算机科学、计算机工程和数学等专业的本科核心课程教材，适用于计算理论、自动化理论、形式语言和计算模型等方面的课程。

第1章 数学基础
1．1 引言
1．2 集合
1．3 关系与图
1．4 函数与计数
1．5 证明技巧
1．6 本章总结与习题
本章习题
第2章 正则语言
2．1 引言
2．2 语言基础
本节习题
2．3 正则表达式
本节习题
2．4 正则语法
本节习题
2．5 确定性有限自动机(DFA)
本节习题
2．6 非确定性有限自动机(NFA)
本节习题
2．7 本章总结与附加思考题
附加思考题
第3章 等价
3．1 引言
3．2 NFA到DFA
本节习题
3．3 有限自动机与正则语法
本节习题
3．4 正则表达式到NFA
本节习题
3．5 NFA到正则表达式
本节习题
3．6 本章总结与附加思考题
附加思考题
第4章 正则语言的结构
4．1 引言
4．2 闭包性质
本节习题
4．3 非正则语言
本节习题
4．4 米歇尔一尼罗德定理
本节习题
4．5 状态最小化
本节习题
4．6 本章总结与附加思考题
附加思考题
第5章 上下文无关语言
5．1 引言
5．2 上下文无关语法
本节习题
5．3 分析树
本节习题
5．4 歧义
本节习题
5．5 消除／删除不良生成式
本节习题
5．6 范式
本节习题
5．7 本章总结与附加思考题
附加思考题
第6章 上下文无关语言的结构
6．1 引言
6．2 叠加自动机
本节习题
6．3 上下文无关语法与叠加自动机
本节习题
6．4 泵作用引理
本节习题
6．5 上下文无关语言的闭包性质
本节习题
6．6 确定型叠加自动机
本节习题
6．7 本章总结与附加思考题
附加思考题
第7章 可计算枚举语言
7．1 引言
7．2 非限制性语法
本节习题
7．3 图灵机
本节习题
7．4 接受与拒绝
本节习题
7．5 使用旧自动机
本节习题
7．6 多带图灵机
本节习题
7．7 非确定性图灵机和语法
本节习题
7．8 本章总结与附加思考题
附加思考题
第8章 非可计算枚举语言
8．1 引言
8．2 作为计算器的图灵机
本节习题
8．3 作为语言判定的图灵机
本节习题
8．4 存在多少图灵机
本节习题
8．5 接受问题
本节习题
8．6 乔姆斯基层次结构
本节习题
8．7 总结和附加问题
本节习题
第9章 算法可解性
9．1 引言
9．2 问题归约
本节习题
9．3 赖斯定理
本节习题
9．4 关于有限自动机
本节习题
9．5 关于叠加自动机
本节习题
9．6 关于波斯特对应问题
本节习题
9．7 关于逻辑理论
本节习题
9．8 其他有趣的问题
本节习题
9．9 总结和附加问题
本节习题
第10章 计算复杂性
10．1 引言
10．2 函数增长率
本节习题
10．3 复杂性类别
本节习题
10．4 空间复杂性
本节习题
10．5 时间复杂性
本节习题
10．6 NP类
本节习题
10．7 NP完整性
本节习题
10．8 某些NP完整问题
本节习题
10．9 解决NP完整问题
本节习题
10．10 本章总结与附加思考题
附加思考题
部分习题答案与提示
参考文献