计算理论基础
2013-1
辛格、曹爱文、叶鹏、 李少帅 清华大学出版社 (2013-01出版)
辛格
《计算理论基础(世界著名计算机教材精选)》由辛格编著，本书讨论了计算机科学中的纯粹、引人注目并且普遍存在的基本内容，介绍构成基本计算范例的基本概念、模型、技巧、结果，阐述当今计算机科学家用于建模、讨论和预测算法与计算的思想概念与数学知识。全书共分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 本章总结与附加思考题 附加思考题部分习题答案与提示参考文献
《计算理论基础(世界著名计算机教材精选)》由辛格编著，本书讨论计算机科学中的纯粹、引人注目并且普遍存在的基本内容，介绍构成基本计算范例的基本概念、模型、技巧、结果，阐述当今计算机科学家用于建模、讨论和预测算法与计算的思想概念与数学。本书中所选话题都是相当长时间内表现出异常持久性，并在当前应用中经常出现的，本书可以作为计算机科学、计算机工程和数学等专业的本科核心课程教材，适用于计算理论、自动化理论、形式语言和计算模型等方面的课程。
这是一本数学书吗?胡乱抄摘一些无关紧要的定理，堆积大量豪无意义的定义，加上几个集合符号改头换面描述一番，数学不象数学，哲学不象哲学，哭笑不得啊！
前几天在图书馆看到的新书,觉得可以,正好最近在研究计算理论,所以就买了,建议入手