计算理论导引（英文版·第2版） pdf 电子书 免费 下载地址

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

本书可作为计算机专业高年级本科生和研究生的教材，也可作为教师和研究人员的参考书。

Preface to the First Edition

To the student

To the educator

The first edition

Feedback to the author

Acknowledgments

Preface 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 Solutions

Part 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 Solutions

Part Two:Computability Theory

Part Three:Computability Theory

Selected Bibliography

Index

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

暂无出版社相关信息，正在全力查找中！

暂无相关书籍摘录，正在全力查找中！

在线阅读地址：计算理论导引（英文版·第2版）在线阅读

在线听书地址：计算理论导引（英文版·第2版）在线收听

在线购买地址：计算理论导引（英文版·第2版）在线购买

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 Turing machines themselves and do not spend much time on the low-level programming of Turing machines. We need only to be comfortable enough with Turing machines to believe that they capture all algorithms.

Similar to a finite automaton but with an unlimited and unrestricted memory, a Turing machine is a much more accurate model of a general purpose computer. A Turing machine can do everything that a real computer can do. Nonetheless, even a Turing machine cannot solve certain problems. In a very real sense, these problems are beyond the theoretical limits of computation.

书籍介绍

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

本书可作为计算机专业高年级本科生和研究生的教材，也可作为教师和研究人员的参考书。

• 作者： 么晓得 发布时间：2010-03-31 11:55:04

  销魂到死...

• 作者： iLRainyday 发布时间：2015-07-19 23:33:35

  只读了需要用到的PART1

• 作者： xiaohanyu 发布时间：2010-11-02 19:34:50

  言简意赅，计算理论之美

• 作者： 恪彥 发布时间：2011-04-25 18:42:46

  乌七八糟.

• 作者： M. Tong 发布时间：2010-02-17 14:36:01

  去年去中科院软件所面试的时候恶补了一下，还是国外的教科书靠谱，深入浅出。这本书给我最深的印象是直觉与逻辑推理并重，作者在每个具体的证明之前都会给出直觉上产生这种思路的原因。

• 作者： 宇宙 发布时间：2011-01-03 17:04:42

  偶得，很不错的书！

• 我们为什么要学习计算理论

  作者：etone 发布时间：2008-03-08 04:38:47

  在所有我看过的计算理论、可计算性、计算复杂度的教材中，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?"

  他很认真的试图从几个方面说服学生，计算理论是“有用”的，但我总觉得这些说服很徒劳：书中的三个部分，对于搞研究的人来说，前两个领域已经或走到头了或不再是主流研究趣味了，只有复杂度尚活跃，但也只是个理论方向之一；而对于那些有志于业界工作的学生，后两个部分几乎永远不会在工作中用到，而只有第一部分的自动机，可能会用到一点点正则表达式。

  看来，从“有用”这个方向去为计算理论辩护，难免会遭遇尴尬和勉强。

  我能想到的理由就只剩两个：

  （一）这些是计算机科学的根本，没有它们计算机科学不能算作是个正经学问，因此，一个自称计算机科学专业的人，应当知道这些。

  （二）这些是美好的，值得在短暂的人生中去经历去见识。

  我觉得这已是足够的理由了。

• 很不错的关于计算理论的介绍

  作者：平凡的老鱼 发布时间：2009-03-09 15:19:17

  事知其然而后知其所以然。

  现代计算机体系的构建，图灵机的数学模型的实现，正是指出了这道创世纪的光。

  现在书里面的内容已经忘记的差不多了，只是记得不断的证明，一步步的证明，充满了智慧的光芒。

  总之，是一本好的数学书。