一本不错的教材

Charles Tang 对计算理论基础的书评发表时间：2008-01-15 16:01:11

第一章集合关系语言
讲了很多集合论的基础内容

第二章有穷自动机
关于有穷自动机的各个方面都有介绍，DFA，NFA，两者的等价性，包括和正则语言的等价性，包括各个等价性的证明，复杂度，都有描述。

第三章上下文无关文法
以增强处理能力为线索，给出了更强的计算模型PDA，然后介绍了CFG，CFL，并且证明了CFG和PDA的等价性。

第四章图灵机
当然，又是为了提高计算能力而提出的更强的模型，但是感觉衔接的不如前面两章好。介绍了标准图灵机，和各种“增强型”图灵机。最后是数值函数，原始递归函数，递归函数等概念。

第五章不可判定性
主要介绍了可判定，不可判定的定义。著名的停机问题，以及由此引出的一系列不可判定问题。提出了递归语言类，递归可枚举语言类等等概念及其性质。

第六章计算复杂性
在更小的范围内给出了“可计算”的问题。罗列了一些P类问题和NP类的问题。

第七章 NP完全性
多项式时间归约的概念。很多的NP完全问题，及其互相之间的多项式归约。

整本书都细细研读了一遍，当然，是为了考试。但是考试结果仍旧不尽如人意就是了。但是感觉还是有收获的。另外，此书第二版的英文版已经绝版了，并且，那本影印的书错误百出。中文版的这本值得称道的就是把很多错误修正了，但是当然，还是有很多错误，但是比英文版的那本好多了。

翻译质量尚可。

对很多问题的介绍的详尽程度一般。
比如递归可枚举语言的补集是什么东西，有什么性质。对递归语言，递归可枚举语言，非递归可枚举语言，这些语言之间的关系介绍不详尽。最最恶心的一点是没有习题答案。

希望能对大家有帮助。