计算理论基础

赤苏之森 2013-01-18 0

= =终于考完了。纪念一下

Charles Tang 2008-01-15 0

全部看过一遍了，并且考试也考了，不知道是否还需要再看一遍~~

卉 2010-11-05 0

计算机专业必修课:)

Lilian_Ye 2013-05-21 0

计算理论课的教材，学的时候听的云里雾里，复习的时候才略为窥见一斑。是很不错的书，值得一看。

MGhostSoft 2008-11-14 0

计算理论领域的经典著作

xiaohanyu 2010-11-02 0

译者不够严谨，有些小下子。还是计算理论导引更好。

赤苏之森 2013-01-18 0

= =终于考完了。纪念一下

Charles Tang 2008-01-15 0

全部看过一遍了，并且考试也考了，不知道是否还需要再看一遍~~

卉 2010-11-05 0

计算机专业必修课:)

Lilian_Ye 2013-05-21 0

计算理论课的教材，学的时候听的云里雾里，复习的时候才略为窥见一斑。是很不错的书，值得一看。

MGhostSoft 2008-11-14 0

计算理论领域的经典著作

xiaohanyu 2010-11-02 0

译者不够严谨，有些小下子。还是计算理论导引更好。

我想说两句

还不错的一本计算理论书籍

sosowo 2010-05-16 1赞

中文翻译版，翻译的还行

书籍说明

计算理论课程使用的书籍

作者同样是大牛，书写的不错，应该算是经典教材

学习计算理论的话，可以作为入门参考

阅读建议

计算理论入门学习书籍

开始学习计算理论的时候可以考虑学习

非常奇妙的一本书

卉 2010-11-05 3赞

    如果是计算机专业的，我觉得越早看越好。
    这本书描述的是非常奇妙的事情，把一个简单的有穷机，下推自动机，图灵机和正则表达式，上下无关文法，无限制文法统一在一起，将一些以前看是若隐若现，似是而非的东西，用理论的科学的方法研究，居然还可以推导。在不停地推导，构造中，又能解决实际中的一些看似无法表达的东西。在这个锻炼的过程中，慢慢知道了计算机的能力，能做什么，不能做什么，怎样做是比较可行的。这是发现和认识世界的一个过程，也是在现实中的一个妥协。图灵机真伟大。
    不过看本书会比较累，都是离散的东西，不停定义构造证明应用，特别是证明的过程，有时候觉得和以前学的证明相差太大，差不多都是构造的方法，好像都不是证明。
    唯一遗憾，就是这本书的习题答案好像没有，网上没有找到。
    书中的NP问题可以结合图论的相关章节和《算法导论》的最后2章一起看，NP在神经网络，人工智能里面都反复提到，也可以结合一起看。

一本不错的教材

Charles Tang 2008-01-15 5赞

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

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

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

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

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

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

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

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

翻译质量尚可。

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

希望能对大家有帮助。

一本不错的教材

Charles Tang 2008-01-15 5

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

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

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

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

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

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

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

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

翻译质量尚可。

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

希望能对大家有帮助。

非常奇妙的一本书

卉 2010-11-05 3

    如果是计算机专业的，我觉得越早看越好。
    这本书描述的是非常奇妙的事情，把一个简单的有穷机，下推自动机，图灵机和正则表达式，上下无关文法，无限制文法统一在一起，将一些以前看是若隐若现，似是而非的东西，用理论的科学的方法研究，居然还可以推导。在不停地推导，构造中，又能解决实际中的一些看似无法表达的东西。在这个锻炼的过程中，慢慢知道了计算机的能力，能做什么，不能做什么，怎样做是比较可行的。这是发现和认识世界的一个过程，也是在现实中的一个妥协。图灵机真伟大。
    不过看本书会比较累，都是离散的东西，不停定义构造证明应用，特别是证明的过程，有时候觉得和以前学的证明相差太大，差不多都是构造的方法，好像都不是证明。
    唯一遗憾，就是这本书的习题答案好像没有，网上没有找到。
    书中的NP问题可以结合图论的相关章节和《算法导论》的最后2章一起看，NP在神经网络，人工智能里面都反复提到，也可以结合一起看。

还不错的一本计算理论书籍

sosowo 2010-05-16 1

中文翻译版，翻译的还行

书籍说明

计算理论课程使用的书籍

作者同样是大牛，书写的不错，应该算是经典教材

学习计算理论的话，可以作为入门参考

阅读建议

计算理论入门学习书籍

开始学习计算理论的时候可以考虑学习

我要写长评

想读在读读过

标签(多个标签以“，”分开):

保存

计算理论基础

推荐文章

猜你喜欢

附近的人在看

推荐阅读

拓展阅读