第一章 集合关系语言
讲了很多集合论的基础内容
第二章 有穷自动机
关于有穷自动机的各个方面都有介绍,DFA,NFA,两者的等价性,包括和正则语言的等价性,包括各个等价性的证明,复杂度,都有描述。
第三章 上下文无关文法
以增强处理能力为线索,给出了更强的计算模型PDA,然后介绍了CFG,CFL,并且证明了CFG和PDA的等价性。
第四章 图灵机
当然,又是为了提高计算能力而提出的更强的模型,但是感觉衔接的不如前面两章好。介绍了标准图灵机,和各种“增强型”图灵机。最后是数值函数,原始递归函数,递归函数等概念。
第五章 不可判定性
主要介绍了可判定,不可判定的定义。著名的停机问题,以及由此引出的一系列不可判定问题。提出了递归语言类,递归可枚举语言类等等概念及其性质。
第六章 计算复杂性
在更小的范围内给出了“可计算”的问题。罗列了一些P类问题和NP类的问题。
第七章 NP完全性
多项式时间归约的概念。很多的NP完全问题,及其互相之间的多项式归约。
整本书都细细研读了一遍,当然,是为了考试。但是考试结果仍旧不尽如人意就是了。但是感觉还是有收获的。另外,此书第二版的英文版已经绝版了,并且,那本影印的书错误百出。中文版的这本值得称道的就是把很多错误修正了,但是当然,还是有很多错误,但是比英文版的那本好多了。
翻译质量尚可。
对很多问题的介绍的详尽程度一般。
比如递归可枚举语言的补集是什么东西,有什么性质。对递归语言,递归可枚举语言,非递归可枚举语言,这些语言之间的关系介绍不详尽。最最恶心的一点是没有习题答案。
希望能对大家有帮助。