计算理论基础

书名：计算理论基础
作者：HarryR.Lewis/ChristosH.Papadimitriou/哈瑞·刘易斯
译者：
ISBN：9787302132882
出版社：清华大学出版社
出版时间：2006-7
格式：epub/mobi/azw3/pdf
页数：244
豆瓣评分： 8.7

书籍简介：

计算理论是计算机科学的理论基础。《计算理论基础》(第2版)介绍了计算理论最核心、最基本的内容，包括形式语言与自动机、可计算性和计算复杂性三大部分。全书共分七章，分别为：集合、关系和语言；有穷自动机；上下文无关语言； Turing机；不可判定性；计算复杂性；NP完全性。《计算理论基础》(第2版)突出了算法，从而使计算机专业的学生更易接受，也更有收益。

作者简介：

书友短评：

@ firefly ＃ 计算理论基础【2-4】我们用“自动机”的概念来理解什么是计算。本书依次考虑了受限制模型“有穷自动机和下推自动机”和一般模型“图灵机”，进而得到算法的形式化定义（邱奇-图灵论题）。【5-7】至此我们的焦点从机器转向算法。我们将忽略机器的底层实现，选用抽象程度更高的描述（乃至日常语言）。我们将看到存在着不能为算法所解决的问题，从而理解可计算与不可计算的界限是什么。我们还将看到如何刻画可解问题的复杂度，以及如何针对难解问题提出实际可行的算法。“…与其他应用学科中使用的数学有很大的区别，它一般是离散的，在这里不强调实数和连续变量，而强调有穷集合和序列。”“在今天的计算机科学教学计划中，算法课程，包含算法的分析和设计，相当地脱离计算理论的课程…我们试图恢复这门课程的某种统一性。” @ symmetry城 很难读 读完也很懵 需要看好几遍的书 @ DomingoInBCE 据教授所说其他讲述计算理论的书都大同小异，重点还是在于书中传达的思想，但思想并不是作者所作，其他计算理论的书并没有读过，所以这打分是给创造出本书思想的前辈打的。满分五分可能都少了。 @ 自由小号 这是一门神课，纪念一下大学 @ 田粒 邱奇图灵论题：算法对应于图灵机。

　　世界著名计算机教材精选(共129册)，这套丛书还有《Java面向对象程序设计》《面向工程与科学的C++程序设计》《计算智能导论》《图像处理、分析与机器视觉》《算法设计》等。

添加微信公众号:好书天下获取