计算理论导论
出版社:机械工业出版社
出版日期:2002-8
ISBN:9787111108405
作者:塞普斯
页数:396页
书籍目录
Preface
To the student
To the educator
The current edition
Feedback to the author
Acknowledgments
0 Introduction
0. l Automata, Computability, and Complexity
Complexity theory
Computability
作者简介
This book——by a noted authority and educator in the field——presents computer
science theory from a uniquely intuitive,“big picture”perspective.The author grounds his clear and interesting study on broad mathematical princi-ples,not low-level technical details:proofs are presented with a “proof idea”component that re-
veals the concetp underlying the mathematical formalism.Similarly,algorithms are pr-esented using prose rather than pseudocode to focus attention on the algorithms the-
mselves,rather than on specific models.Formerly published in a Preliminary Edition,
this First Edition features additional chapters on space complexity (Chapter 8),pro-vable intractability (Chapter 9)and advanced topics in computability theory(Chapter
10).For further information,see the World Wide Web site for the book at:
math.mit.edu/sipser/book.html
发布书评
精彩书评 (总计2条)
-
让人了解计算机的本质，它的能力与它的局限性。计算理论课的教材，上课上的很累，但很有收获。我觉得没读过这本书的不好意思说自己是Computer Science专业毕业的。 -
在所有我看过的计算理论、可计算性、计算复杂度的教材中，Sipser的这本Introduction to the Theory of Computation是最适合入门的。把计算理论这么个艰深的学问讲解得清晰简洁，直观易懂。而且涵盖了计算理论的各个经典内容。作为一本introduction，真是再好不过了。计算理论这门学问，顾名思义，就是把“计算”(computation)这个抽象的现象作为我们的研究对象，用数学工具来分析和刻画，并为此而建立的理论体系。全书分为三部分：自动机；可计算性；复杂度。这刚好是计算的三个不同的方面：计算的模型；计算的界限；计算的代价。自动机理论抽象的描述了什么叫“问题”，什么叫“解”，计算的机制可以有什么样的形式。可计算性关注的是计算的“行不行”的一面。而复杂度关注的是“好不好”的一面、也即问题的“难”和“易”。什么是计算机？什么可以被计算？什么样的问题是难的、什么样的问题是容易的？这些计算机科学最自然最根本的问题，是计算理论这门学问的主题，也是这本书的主题。这本书最美妙之处，并不在于它描述的那些艰深的问题和结果，而是它全面展示了计算理论中那些最引人入胜的深刻想法(idea)：抽象问题(problems)的形式语言(formal languages)描述，确定性(deterministic)和非确定性(nondeterministic)的引入，对角化(diagonalization)和停机(halting)问题，归约(reduction)的思想，完全性(completeness)，relativization，alternation。这些都是计算理论中最具创造性的划时代的思想。这些不仅仅是单纯的研究结果，这些idea的出现更是影响了人类今天对计算这个现象的根本认识。唯一的小缺憾就是，应该在最后一章advanced topics里面，去掉parallel computation，加上communication complexity和著名的PCP (probabilistically checkable proofs)。很高兴能有这么一本书，收集了这些璀璨珍珠，清楚的呈现给我们。然而，尽管我对这本书和这门学问都很推崇，我对于学习计算理论的必要性却并不坚定。我自己喜欢这些，可我该如何向别人解释学习它是必要的？Sipser在前言中也试图说明这个问题:"After all, isn't theory arcane, boring, and worst of all, irrelevant?"他很认真的试图从几个方面说服学生，计算理论是“有用”的，但我总觉得这些说服很徒劳：书中的三个部分，对于搞研究的人来说，前两个领域已经或走到头了或不再是主流研究趣味了，只有复杂度尚活跃，但也只是个理论方向之一；而对于那些有志于业界工作的学生，后两个部分几乎永远不会在工作中用到，而只有第一部分的自动机，可能会用到一点点正则表达式。看来，从“有用”这个方向去为计算理论辩护，难免会遭遇尴尬和勉强。我能想到的理由就只剩两个：（一）这些是计算机科学的根本，没有它们计算机科学不能算作是个正经学问，因此，一个自称计算机科学专业的人，应当知道这些。（二）这些是美好的，值得在短暂的人生中去经历去见识。我觉得这已是足够的理由了。
精彩短评 (总计6条)
-
教材，上的很累，但很有收获。我觉得没读过这本书的不好意思说自己是Computer Science专业毕业的。 -
曾经复旦计算机系《计算理论》课的教材，一德国老师全英文授课，勉强看懂过前3章 -
这本才是人看得书啊 我看的那本《自动机理论、语言和计算导论》不是人看的 简直对那本无语了 -
内容有点老了 但是extremely well written -
很适合自学 -
虽然没有全部读完，不过作者注重原理性讲解的方式还是不错的。