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