Computability and Complexity 短评

  • 1 平凡的老鱼 2014-06-02

    一本很理论论的关于计算理论的书,因为参加相关讨论而读的。由于讨论只涉及到可计算性,后面半本没有读,整本书结构主线突出,讲的东西也不算太难,就是因为好久没有像在学校那样正式推导公式了,所以符号不太好记。里面提到的while语言也就是作为介绍理论用的,实用性不强。如果只是想了解起计算理论的话,可以不用读这本书。

  • 0 ekd123 2020-02-12

    很棒的书!在网上随便搜到了这本书,作为第一本入门书来读了。 这本书的特色是使用编程语言(和递归数据结构)去讲述在可计算性和复杂度理论,比起数理逻辑传统递归论的数论方法显得极为平易近人。书的内容基本是经典的,虽然是第一本读的 TCS 书不过一些结论已经耳濡目染了解到了。更有趣的是书里还涉及到了丢番图方程和希尔伯特第十问题~ 要说有什么缺陷的话,就是内容太多,给的问题例子不够多,所有问题几乎都服务于定理证明了。 书的结构也非常好,每一章不长不短,证明一个定理和多个引理,读起来比较顺畅。习题没怎么做,基本是一些证明过程提出来,所以就不评论了。

  • 第一页
  • 前一页
  • 后一页