计算理论基础（第2版）

　　计算理论是计算机科学的理论基础。本书介绍了计算理论最核心、最基本的内容，包括形式语言与自动机、可计算性和计算复杂性三大部分。全书共分7章，分别为：集合、关系和语言；有穷自动机；上下文无关语言；turing机；不可判定性；计算复杂性；np完全性。本书突出了算法，从而使计算机专业的学生更易于接受，也更有收益。.
　　 本书适合作为计算机专业及数学专业本科生或研究生的教材，也可供从事计算机科学的教学与研究人员参考。...

第1章 集合、关系和语言
1．1 集合.
1．2 关系与函数
1．3 特殊类型的二元关系
1．4 有穷集合与无穷集合
1．5 三个基本的证明技术
1．6 闭包与算法
1．7 字母表与语言
1．8 语言的有穷表示
参考文献
第2章 有穷自动机
2．1 确定型有穷自动机
2．2 非确定型有穷自动机
2．3 有穷自动机与正则表达式
2．4 正则语言与非正则语言
2．5 状态最小化
2．6 关于有穷自动机的算法
参考文献
第3章 上下文无关语言
3．1 上下文无关文法

　　看看你的周围，计算无处不在，无时不在，每一个人都计算，计算影响着所有的人。所以能够如此，是因为在过去的几十年中计算机科学家发现了很复杂的方法用来管理计算机资源，实现通讯，翻译程序，设计芯片和数据库，创造更快、更廉价、更容易使用、更安全的计算机和程序。.
　　和所有的主要学科一样，计算机科学的成功实践建立在优美和坚实的基础之上。自然科学有一些基本问题，如物质的本质是什么?有机体生命的基础和起源是什么?计算机科学同样有它自己的基本问题：什么是算法?什么是能计算的?什么是不能计算的?什么时候可以认为一个算法是实际可行的?60多年来(甚至从电子计算机出现之前就开始了)计算机科学家一直在考虑这些问题并且给出充满智慧的回答，这一切对计算机科学产生了深刻的影响。
　　本书的目的是介绍渗透在计算机科学中的这些基本思想、模型和结果，它们都是该领域的基本范例，它们有很多理由是值得学习的。首先，现代计算机科学中的很多东西直接或间接地以它们为基础——而其余的应该……。其次，这些思想和模型是漂亮、有力的，是数学建模的杰出例子，是有长久价值的。此外，它们更是历史的一部分，是我们这个领域的“共同潜意识”。不首先了解它们，是很难理解计算机科学的。
　　这些思想和模型在本质上是数学的，这大概不会让人感到奇怪。虽然计算机肯定是一个物理实体，但是同样肯定的是关于它的物理方面，如它的分子和它的形状，能够值得说的很少；对计算机最有用的抽象显然是数学的，论证这些抽象所必需的手段也一定同样是数学的。此外，实际的计算工作需要只有数学才能提供的铁的保证(希望我们的编译程序正确地翻译，应用程序最终停机，等等)。但是，在计算理论中使用的数学与其他应用学科中使用的数学有很大的区别，它一般是离散的，在这里不强调实数和连续变量，而强调有穷集合和序列。它以很少几个基本的概念为基础，通过小心、耐心、仔细、一层一层地处理这些概念，勾画出它的能力和深奥之处——这很像计算机，在第1章将使你回想这些基本的概念和方法(其中有集合、关系和归纳法)，介绍在计算理论中使用它们的风格。
　　第2章和第3章描述某些受限制的计算模型。它们能够完成一些非常特殊的字符串处理工作，例如回答一个给定的字符串是否出现在给定的正文中，如字punk是否出现在莎士比亚文集中，或者检查一个给定的括号字符串是否正好平衡——像()和(())()，而不是)()的样子。这些受限制的计算模型(分别叫做有穷自动机和下推自动机)竟然作为像电路和编译程序之类很普通的系统的非常有用和高度完善的部分出现在现实生活中。在这里它们为我们探索算法的一般的形式定义提供极好的热身练习。此外，看到由于增加或删除各种特性这些装置的能力如何增强和减弱(或者，更经常地是，保持不变)是有教益的。其中最值得注意的特性是非确定性，计算的这个迷惑人的特性既是重要的，又是(相当荒谬地)非现实的。..在第4章，我们研究算法的一般模型，其中最基本的模型是Turing机。Turing机是第2章和第3章中字符串处理装置的相当简单的推广，结果令人吃惊地成为描述任意算法的一般框架。为了证明这一点，即通常所说的Church-Turing论题，我们引入越来越复杂的计算模型(Turing机更强的变种，还有随机存取Turing机和递归定义的数值函数)，并且证明它们在能力上全都完全等价于基本的Turing机模型。
　　再下一章处理不可判定性。某些自然的明确的计算任务具有这种出人意料的性质，可以证明它们超出了算法能够解决的范围。例如，问你是否能用给定的若干种形状的砖铺整个平面。如果这些形状中包括一个正方形，或者甚至一个三角形，则答案显然是“能够”。但是，如果是几种稀奇古怪的形状，或者规定几种形状必须至少使用一次，那会怎样?这肯定是很复杂的问题，你想用机器给出回答。在第5章我们使用Turing机的形式表示证明这个问题和许多其他问题是根本不可能用计算机解决的。
　　即使当一项计算任务能够用某个算法解决的时候，也可能不存在解决它的适当快的、实际可行的算法。在本书的最后两章，我们说明怎么用它们的复杂性对现实生活中的计算问题进行分类：某些问题能够在合理的，即多项式的时间界限内解决，而另一些问题似乎需要以天文速度，即指数地增长的时间。在第7章我们定义一个叫做NP完全的问题类，它们是一些普通的、实际的、但难得出名的问题(旅行商问题仅是它们中的一个)。我们证明所有这些问题在下述意义下是等价的：如果它们中的一个有有效的算法，则它们每一个都有有效的算法。普遍地相信所有NP完全问题具有固有的指数复杂度；这个猜想是否实际上为真是著名的P≠NP问题，它是当代数学家和计算机科学家面临的最重要和最深刻的问题之一。
　　本书有很多篇幅是有关算法及其形式基础的。然而，大概你也意识到了，在今天的计算机科学教学计划中，算法课程，包括算法的分析和设计，相当地脱离计算理论的课程。在本书的现行版本中，我们试图恢复这门课程的某种统一性。结果是，本书对算法也提供了相当不错的介绍，只是有些专门和非传统。在第1章形式地介绍算法及其分析，并且在第2章和第3章研究受限制的计算模型和由它们产生的自然的计算问题的时候一再重新提起。这样一来，在后面探索算法的一般模型的时候，读者处在较好的位置，能正确评价这种探索的目标并且断定是能成功的。在讲解复杂性时算法同样担任主角。因为鉴别复杂问题的最好方法是把它与另一个经得起有效算法考验的问题进行比较。最后一章用一节叙述对付NP完全性作为结束，给出在遇到NP完全问题时已经成功地使用过的算法技术(近似算法、穷举算法、启发式局部搜索等)。
　　计算是必不可少的、有力的、优美的、具有挑战性和不断发展的——它的理论也是如此。本书仅讲了一个激动人心的故事的开头，它是对从计算理论宝库中精选出的少量基本论题的朴素介绍。我们希望它将激发读者去作进一步的探索，每一章最后的参考文献指出了好的出发点。...
　　

　　自《计算理论基础》问世以来，在这15年中许多东西变了，也有许多东西没有变。计算机科学现在是一门成熟得多的公认的学科，在这个计算无处不在、信息全球化和复杂性迅速增长的世界上扮演越来越重要的角色，因此有更多的理由关心它的基础。《计算理论基础》的作者们自己现在更加成熟和忙碌——这是何以这么久才出第二版的原因。我们写第二版，是因为我们感觉到有几处可以说得更好些，有几处可以简单些，还有一些可以删掉。更重要的是，我们希望本书反映计算理论和学它的学生在这些年的进步。虽然就绝对而言现在教计算理论的比过去多了，但是它在计算机科学教学计划中的相对地位，例如与算法课程相比，没有得到加强。实际上，算法设计与分析领域现在已经很成熟，有理由认为它的基本原理是关于计算理论的基础课程的一部分。此外，今天的大学生有广泛的和早期的计算经验，清楚地知道自动机在编译程序中的应用。但是，例如在讲像Turing(图灵)机这样的简单模型，用它们作为一般的计算机模型时，他们的疑问更多。总之，对这些问题的处理需要作某些修改。.
　　具体地说，与第一版的主要区别有：
　　·早在第1章就形式地介绍算法设计与分析的入门(与闭包有关)，并且算法问题的讨论贯穿全书。在第2、3章有几节讨论与有穷自动机和上下文无关文法有关的算法问题(包括状态最小化和上下文无关识别)。有关于NP完全问题的易解变形的算法，还有一节考察“对付NP完全性”的算法技术(特殊情况的算法、近似算法、回溯与分支定界、局部改进以及模拟退火算法)。
　　·第4章对Turing机的处理更形式化，模拟论证更加简单和更加定量。引入随机存取Turing机，以帮助跨越Turing机的笨拙与计算机和程序设计语言能力之间的鸿沟。
　　·第5章介绍不可判定性，包括某些递归函数论内容(到Rice定理为止)。介绍文法和递归数值函数，证明它们等价于Turing机，证明更加简单。与上下文无关文法有关问题不可判定性的证明采用简单的直接论证，而不求助Post对应问题。保留铺砖问题，这个问题在NP完全性一章还要见到。..
　　·处理复杂性的方式相当的新颖：在第6章，除多项式时间界限之外没有定义其他时间界限——于是，P是接触到的第一个复杂性类和概念。然后，用对角化方法证明存在不在P中的指数问题。同时介绍现实生活中的问题与它们的语言表示(两者的区别被故意地弄模糊了)，广泛地考察它们的算法问题。
　　·NP完全性是单独的一章。在这一章中，有一组新的、广泛的、我们认为有助于教学的NP完全性归约，最后一个是正则表达式的等价问题——回到本书的第一个问题。正如上面所说，本书的最后一节是关于“对付NP完全性”的算法技术。
　　·在这个新版中删去关于逻辑的几章。这是一个困难的决定。作出这样的决定有两个原因：种种迹象表明，这几章是本书过去读得最少和教得最少的几章；现在有几本更好的论述这个题目的书。但是，在第6章将详细地论述布尔逻辑和它的可满足性问题。
　　总的说来，证明和讲解被简化了，并且在一些关键的地方更加形式化。有几处，如在上下文无关语言与下推自动机的等价性的证明中，把长篇技术性归纳陈述的证明改作习题。每一节的后面有几个习题。
　　经过这些改动之后，现在有不只一种的方式讲授本书的材料(还有在第一版中提出的方式以及使用中形成的方式)。以讲授计算理论和算法的基础为目标的一学期长的课程可以以从第2章到第7章中选取的材料为基础。
　　我们衷心地感谢在这15年中所有向我们提供反馈、想法、错误和更正的我们的学生和同事——不可能在这里把他们全部列出来。特别感谢Martha Sideri帮助修订第3章。还要十分感谢本书的编辑Alan Apt和Prentice Hall的朋友们——Barbara Kraemer，Sondra Chavez和Bayani de Leon——他们都非常有耐心而且乐于助人。
　　最后，我们乐于收到指出错误的报告和其他评论，最好是通过电子邮件，地址是：elements@cs．berkeley．edu．有关本书的错误、更正和其他信息也可以通过这个地址得到。...