计算理论导引

出版时间：2006-1  出版社：机械工业出版社  作者：塞普瑟  页数：437  
Tag标签：无  

内容概要

　　《计算理论导引（英文版）（第2版）（新版）》由计算机理论领域的知名权威Michaael Sipser所撰写。他以独特的视角，系统地介绍了计算机理论的三个主要内容：自动机与语言、可计算性理论和计算复杂性理论。约大部分内容是基本的，同时对可计算性和计算复杂性理论中的某些高级内容进行了重点介绍。作者以清新的笔触、生动的语言给出了宽泛的数学原理，而没有拘泥于某些低层次的细节。在证明之前，均有“证明思路”，帮助读者理解数学形式下涵的概念。同样，对于算法描述，均以直观的文字而非伪代码给出，从而将注意力集中于算法本身，而不是某些模型。新版根据多年来使用本书的教师和学生的建议进行了改进，并对课堂测试题进行了全面的更新，每章末均有样例解答。　　《计算理论导引（英文版）（第2版）（新版）》可作为计算机专业高年级本科生和研究生的教材，也可作为教师和研究人员的参考书。

作者简介

作者：(美)塞普瑟Michaael Sipser：麻省理工学院应用数学系教授，计算机科学和人工智能实验室（CSAIL）成员。他从事理论计算机科学与其他数学课程的教学工作25年，目前为数学系主任。他痴迷于复杂性理论，喜欢复杂性理论的教学工作。

书籍目录

Preface to the First Edition      To the student      To the educator      The first edition      Feedback to the author      AcknowledgmentsPreface to the Sceond Edition（International）  0  Introduction    0.1  Automata,CompUTABILITY,and Complexity      Complexity theory      Computability theory    0.2  Mathematical Notions and Terminology      Sets      Sequemces and tuples      Functions and relations      Graphs      Strings and languges      Boolean logic      Summary of mathematical terms    0.3  Definitions,Theorems,and Proofs      Finding proofs    0.4  Types of Proof      Proof by construction      Proof by construction      Proof by induction    Exercises,Problims,and SolutionsPart One:Automata and Languages  1  Regular Languages    1.1  Finite Automata      Formal definition of afinite automaton      Examples of finite automata      Formal definition of computation      Designign finite automata      The regular operations    1.2  Nondeteriminism      Formal definition of a nondeterministic finite automaton      Equivalence of NFAs and DFAs      Closure under the regular operations    1.3  Regular Expressions      Formal definition of a regular expression      Equivalence with finite automata    1.4  Nonregular Languages      The pumping lemma for regulan languages      Exercises,Problems,and Solutions  2  Context-Free Languages    2.1  Conetxt-free Grammars      Formal definition of a context-free grammar      Examples of context-free grammars      Designing context-free grammars      Ambiguity      Chomaky mormal form    2.2  Pushdown Automata      Formal definition of a pushdown automaton      Examples of pushdown autonata      Equivalence wish context-free grammars    2.3  Non-context-free Languages      The pumping lemma for context-free languages    Exercises,Problems,and SolutionsPart Two:Computability TheoryPart Three:Computability TheorySelected BibliographyIndex

用户评论 (总计45条)

•   这本书挺好的，对英语也有帮助
•   Hardcover: 480 pagesPublisher: Course Technology; 3 edition (June 27, 2012)Language: EnglishISBN-10: 113318779XISBN-13: 978-1133187790
•   纯英文版的，对于形式化语言的学习有帮助
•   内容就不用讲了 纸张也不错
•   英文原版，喜欢的人可以试试
•   内容还是不错的，英文原版经典，纸张一般。
•   刚开始读的时候还有些疑惑，怎么mit的教材如此简单，后来才在封面上发现这是国际版，而且前言里说国际版不能代替标准版，看来还得看别的书才能在这方面入门。ps：真想看看美国版的是啥样。
•   书是正品，帮助很大，很喜欢~
•   书是没有一点问题，很喜欢。但是金书网发货实在是太慢了，说是拍后的1-2天内发货，他们非要等到第2天的晚上才发货，这也太坑爹了吧？并且，刚好我拍下的时候是凌晨1点左右，我等了足足有3天，金书网才发货，发货后物流速度也真是不敢恭维，整整4天才到，淘宝上发货加上物流速度3天之内就到了，这也太慢了吧？这是我买书以来等时间最长的一次，再晚几天，课都上完了估计。。。
•   university of colorado at colorado springs的教材，帮国外的哥们买的，刚好有人捎过去，买国内这个授权影印版要比在国外买便宜多了。指定教材，质量水平有保证。亚马逊送货及时，书本本身外面还有透明塑封保护。
•   书有点破损，印刷质量有点偏差
•   不错的书，比《计算理论基础》要系统和全面，更生动
•   　　看了好几家都是没货，机械工业2006出版的这本绝版了？？啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
•   　　RT，英语真心一般啊，想看看有木有翻译版本的，Introduction to the Theory of Computation，第二版，请各位大神指导一下，请告知翻译版本的书名，出版社等信息
  　　RT，英语真心一般啊，想看看有木有翻译版本的，Introduction to the Theory of Computation，第二版，请各位大神指导一下，请告知翻译版本的书名，出版社等信息
  　　RT，英语真心一般啊，想看看有木有翻译版本的，Introduction to the Theory of Computation，第二版，请各位大神指导一下，请告知翻译版本的书名，出版社等信息
  　　
  　　导师推荐的书，肯定是经典的书
•   　　如果你周围的人在说P， NP之类，而你还不知道这些概念，请捧起这本书！
  　　
  　　之后，如果你还想去解决它们，寻求解决思路可以参考这本Metaheuristics For Hard Optimization
  　　
  　　
•   　　我觉得作者很可爱，他同很多人一样很喜欢把一个复杂的问题说的很简单很通俗。　　对于这本书来说，看了第一章，就应当一成的收获。计算机中重要的数学概念被解构的如此清楚，非常的难得。　　另外，要说一下，翻译的问题。翻译的很不错（话说本来英文版就很上口），但是却是看原版会体会更深刻的意义。例如 “有限状态自动机及其对照物马尔可夫链...” 一句，显然就不如 “finite automata and their probabilistic counterpart markov chains...”
•   　　让人了解计算机的本质，它的能力与它的局限性。
  　　
  　　计算理论课的教材，上课上的很累，但很有收获。我觉得没读过这本书的不好意思说自己是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?"
  　　他很认真的试图从几个方面说服学生，计算理论是“有用”的，但我总觉得这些说服很徒劳：书中的三个部分，对于搞研究的人来说，前两个领域已经或走到头了或不再是主流研究趣味了，只有复杂度尚活跃，但也只是个理论方向之一；而对于那些有志于业界工作的学生，后两个部分几乎永远不会在工作中用到，而只有第一部分的自动机，可能会用到一点点正则表达式。
  　　
  　　看来，从“有用”这个方向去为计算理论辩护，难免会遭遇尴尬和勉强。
  　　
  　　我能想到的理由就只剩两个：
  　　（一）这些是计算机科学的根本，没有它们计算机科学不能算作是个正经学问，因此，一个自称计算机科学专业的人，应当知道这些。
  　　（二）这些是美好的，值得在短暂的人生中去经历去见识。
  　　
  　　我觉得这已是足够的理由了。
  　　
•   　　本书的作者是著名的计算理论方面专家，麻省理工学院应用数学系主任 M. Sipser。全书分为11章，并附有部分习题解答。全书思路清晰，由浅入深，内容详细，是一本零起点学习计算理论的理想教材。我是出于研究需要阅读此书的。其中第零章简要介绍了所需要的基本数学知识。第一到三章介绍了三种计算模型，正则语言类-有限自动机，上下文无关语言类-下推自动机，图灵可识别语言类-图灵机。之后，在四到六章，介绍了可计算理论。七到十章介绍了复杂性理论。由于个人需要，我详细阅读了本书的0、1、2、3、4、5、7章节，并作了相应的习题。这些章节应该对非计算理论方向研究人员搞清计算理论的基础以及时间复杂性方面的初步问题已经足够。我简要阅读了6、9、10章中的部分内容，其中第六章是可计算理论中的高级专题，本章趣味性和难度都比较强，由于对我个人研究帮助不大，我并没有详细阅读此章。第九章部分需要第八章作为基础。而第十章前两节是极其有用的，分别介绍近似算法以及概率算法，但是此处是一个大概的介绍，具体应参照另外两本专门介绍此内容的书籍。第8章空间复杂度由于在应用当中并没有多少人关注，所以我并没有阅读。总体来讲本书应该是有志从事计算机科研方面的必备教材，我对此书的阅读至此告一段落，也许以后对于某些概念的精确定义我还会重新翻开此书。
  　　12/29 2007
•   是否需要很好的基础？
•   我觉得不需要什么特别的基础，我当时是为了“反问题”那门课看的。之前也只是本科学的那点数学底子。
•   谢谢。:)
•   counterpart这个词确实不好翻译
•   目测，学长被廖士忠虐过。
•   en 想当初我考的可是很高的
•   同样也是计算理论的两本参考书之一。另一本是Elements of the Theory of Computation
•   感觉有趣算不算一个理由？当然，也许并非所有人都会觉得有趣，我只是说，也许很多人会觉得TCS有趣。显然，能感觉出美来，那是更深层次的收获。
•   同意楼上的，我以后可能不会搞计算理论，但看一看这方面的问题是一种快乐，这对我来说是最好的理由
•   宋公说：学习TCS是为了体会美和伟大
•   计算理论确实很有趣，喜欢数学的人应该都会喜欢的
•   （二）这些是美好的，值得在短暂的人生中去经历去见识。
  同意！
  这个世界上有很多美丽的东西，然而很多时候这些美丽需要一定的基础去理解。难得这生做与计算机科学有关的事情，过宝山而不入就太遗憾了（这个比喻可能不恰当，原谅我的词汇贫乏）.
•   悲剧的是只有寥寥几人评分
•   只能说lz对计算理论的理解还是比较深刻的
•   做了大量计算机的应用后,不了解根的人很多很多.想了解,才发现时这么的难找资料.得找数学系的人.聊聊才行.
•   正在学这门课程，感觉挺没意思的。不知道是自己不重视，还是老师讲的不怎麽样。。。
•   　　这个世界上有很多美丽的东西，然而很多时候这些美丽需要一定的基础去理解。难得这生做与计算机科学有关的事情，过宝山而不入就太遗憾了（这个比喻可能不恰当，原谅我的词汇贫乏）.
  =======================
  讲的太好了
•   这个课大家都知道很重要 但是上课就是听不懂 真郁闷
•   楼主书评写得不错
•   书评很棒，其实只要是理论方面，都是很美的，都值得去见识
•   除了纸张不好，内容非常不错的。
  然而，机工的影印版是国际版，个人认为可以作为兴趣读物和导论教材。若要深入了解计算理论或应付考试，还是推荐Hopcroft的自动机。
•   我的想法和LZ一样，觉得这些知识是“有必要”了解的，至于为什么有必要？它就是有必要……
  看书的时候对照着唐常杰教授的PPT看，感觉作者和译者都是乐之者，另外这本书思路先行的写法真的是very nice，多么复杂神奇的证明都是娓娓道来
•   理解是最大的快乐。
•   “研究走到头”不说明不要去了解去学习。九九乘法口诀也走到头了，但小学生照样要学，因为这是基础。这个是计算机的基本理论，一定要去“研究”没有必要，但作为一门专业课程去“学习”还是很有必要的。
•   2009-04-14 13:45:45 azalea
  计算理论确实很有趣，喜欢数学的人应该都会喜欢的
  2010-10-14 13:48:22 hello
  正在学这门课程，感觉挺没意思的。不知道是自己不重视，还是老师讲的不怎麽样。。。
  ===================
  只能说人和人差异很大。