收藏
Introduction to the Theory of Computation - Michael Sipser

Introduction to the Theory of Computation

Michael Sipser

出版社

Cengage Learning

出版时间

2012-06-27

ISBN

9781133187790

评分

★★★★★

标签

计算理论计算机计算机科学CS

书籍介绍
这不是一本教你写代码的书，而是一场关于'计算究竟是什么'的思辨。它从最简单的有穷自动机起步，带你一步步走到图灵机、可计算性、复杂度，乃至Kolmogorov复杂度和交互式证明系统——这些多数教材刻意回避的边界地带。Sipser最被读者称道之处，在于他能把抽象到极点的证明讲得'如此明白'，在细节与全局之间取得罕见平衡：既让你信服'图灵机足以捕捉所有算法'，又让你看清'我们真正关注的早已是算法本身'。它适合那些不满足于'怎么用'、而想追问'为什么可能、为什么不可能'的读者；也提醒自学者：它写法精简、偏重理论，当作系统复习或建立框架的工具，远比当作入门自学手册更称职。
精彩摘录
  • "Ignoring the trees to see the forest doesn't mean that one is more important than the other--it just gives a different perspective."
  • "We have come to a turning point in the study of the theory of computation. We continue to speak of Turing machines, but our real focus from now on is on algorithms. That is, the Turing machine merely serves as a precise model for the definition of algorithm. We skip over the extensive theory of Turi"
用户评论
看了前9章，讲得真的很详细，很易懂，用词等也很规范，可以让人初步养成良好的思维模式，是一本非常好的入门书籍。
formal language三本参考教材之一。主要读了计算理论的部分。这本书写法精简，不适合自学，作为复习材料尚可。内容集中在讲解理论，应用涉及的少。
或许是最好的计算理论教材，从最基础的有穷自动机讲起，直至将Kolmogorov complexity和交互式证明系统这样的概念以自然的方式呈现在读者眼前。Sipser属于那种教学经验丰富、深谙把复杂证明讲得深入浅出之道的作者。这一版还增加了对确定型下推自动机以及LR(k)文法的讨论，对于关心自动机应用的读者来说，几乎可以和编译龙书无缝衔接。
很好的计算理论教材（自动机图灵机复杂度）。 阅读感受贼好，先why/example后definition，先intuition/special case后formal proof。 而且还很薄，读起来压力小。。
在 details 和 big picture 之间做的平衡非常好。
入门的，太入门的
非常基础的教科书，课件参考书。
花了一个学期四个学分学了这么一个“没用”的课，对找工作没用，对找（非复杂度理论）research没用。就像吴荻老师在美术鉴赏课第一节课说的，我这个课就是没用，然后他讲了庄子那个故事。谢谢Sinclair教授用他纯正的英音带我们在zoom上探索（引用长评第一）计算的模型，计算的限制，计算的代价。这课就像吴荻老师的课一样，给你最大的“用处”是让你切实地感受到美。讲到图灵机为何可以model目前一切计算；讲到为何一切NP都可以归约到3SAT；讲到山外有山，从NL到PSPACE；就像吴老师讲富春山居图，八大山人，北京的胡同：可能没什么用，但你闭上眼，回味无穷，从心底赞叹一声，真美啊，就足够了。
时常希望所有科目都像这样只有一本逻辑清楚知道自己要说什么的公认教科书 可惜这样的事很少发生 @2018-04-04 13:14:17
Cengage Learning的其他书籍查看全部

下载
收藏