计算理论基础(第2版)

编辑:吞吐网互动百科 时间:2020-06-04 23:13:47
编辑 锁定
《计算理论基础(第2版)》是2006年清华大学出版社出版的图书,作者是张立昂。
书    名
计算理论基础(第2版)
作    者
张立昂
ISBN
9787302132882
定    价
29.00
出版时间
2006年11月28日
装    帧
平装

计算理论基础(第2版)图书简介

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

计算理论基础(第2版)前言

编辑
半年前我先后接到清华大学出版社第四编辑室室主任薛慧同志和机械工业出版社华章图文信息有限公司总编辑傅豫波同志的电话,前者请我翻译这本书,后者请我翻译Sipser的Introduction to the Theory of Computation (Second edition),我都欣然接受,并且邀请王捍贫、刘田和黄雄三位博士共同翻译。其实,翻译教材并不是一件美差,对我来说,更谈不上是“好事”,由于眼疾,看书时间一长,心里总犯怵。现在总算完成了任务,两本书都即将出版(尽管中间眼睛还是又犯了一次病)。我之所以愿意翻译这两本书,一是因为它们确实是两本关于计算理论的优秀教材;二是因为国内太缺乏这样的书了,尽管计算机类书刊极其繁多,可是计算理论的书却难觅踪影。清华大学出版社和华章图文信息有限公司购买这两本书的版权翻译出版,此乃善举!我怎好推却。
计算理论在计算机科学技术专业的教学计划中的地位是有争议的。国内计算机专业本科几乎没有开计算理论课的,研究生学这门课的好像也不多,倒是那些想去美国读书的学生为了应付GRE Subject测试,自己在找有关计算理论的书看。我希望这两本书的出版能有利于提高计算机教育界对计算理论的重视,特别希望立志致力于计算机科学技术事业的青年学生都来认真地学一点计算理论,那将可能是终身受益的。
本书包括形式语言与自动机、可计算性和计算复杂性三大部分,这是计算理论最核心、最基本的内容。本书的一大特色是突出了算法,从语法分析到NP难问题的实用算法,算法贯穿全书。这些内容不仅透彻生动地提供了算法设计与分析的基本理论,而且使读者清楚地看到,计算理论不是没有用,也不是离实际很远的。恰恰相反,不仅当今的许多计算机技术可以在计算理论中找到它的思想渊源,而且在许多实际问题中充满着计算理论。
我们按照作者在第二版序言中提供的电子邮件地址得到本书的勘误。在翻译过程中我们又发现了一些错误,也都予以更正。这些错误基本上都是非实质性的,因此没有在书中一一指明。我们已用电子邮件把发现的错误发给作者。
第一版序言
本书在大学本科水平上介绍经典的和当代的计算理论。粗略地说,内容包括自动机理论与形式语言、Turing(图灵)机的可计算性与递归函数、不可计算性、计算复杂性以及数理逻辑,采用数学的处理方法和计算机科学的观点。于是,在关于上下文无关语言的一章中包含语法分析的讨论,在关于逻辑的几章中给出定理归结证明的有效性和完备性。
在本科教学计划中,这门课通常安排在后面和算法设计与分析课同时上。我们的看法是学计算机科学的学生应该早一点接触这些材料,比如,在二年级或三年级。这是因为,其一,对这些材料的深入研究形成计算机科学中的一些专题;其二,它有助于提供必要的数学示范。但是,我们发现由于一些更高级的教科书要求学生具有较好的数学基础,教这门严格的大学生课是一项困难的任务。我们写这本书的目的是用数学的语言、但不要求有专门的数学经验使得这门课的实质易于被大学生们理解。
全书提供一学年的课程。我们都讲过一个学期的课程,包括第1章到第6章的大部分内容,根据情况删去了关于语法分析、递归函数及具体的不可解判定问题的部分内容,其他的选择是可能的。例如,强调可计算性和机械逻辑基础的课程可以很快地跳过第1章到第3章,集中力量讲第4、6、8和9章。不管怎样使用它,我们都强烈地希望本书对下一代计算机科学家的智力发展有所贡献,在他们受教育的早期阶段向他们介绍关于计算问题的新鲜的和有条理的思想。
我们借这个机会感谢所有让我们从他们那儿学到东西的人,包括教师和学生。特别感谢Larry Denenberg和Aaron Temin校对早期的草稿,Michael Kahl 和 Oded Shmueli 作为助教对我们的帮助和建议。1980年春季,Albert Meyer 在MIT(麻省理工学院)用这本书的草稿讲课,提出很好的批评和修改意见,对此我们表示衷心的感谢。当然,遗留下任何错误都应该由我们负责。Renate D’Arcangelo 以她特有的、非凡的完美和迅速打手稿和画图。
第二版序言
自《计算理论基础》问世以来,在这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——他们都非常有耐心而且乐于助人。
导言
看看你的周围,计算无处不在,无时不在,每一个人都计算,计算影响着所有的人。所以能够如此,是因为在过去的几十年中计算机科学家发现了很复杂的方法用来管理计算机资源,实现通讯,翻译程序,设计芯片和数据库,创造更快、更廉价、更容易使用、更安全的计算机和程序。
和所有的主要学科一样,计算机科学的成功实践建立在优美和坚实的基础之上。自然科学有一些基本问题,如物质的本质是什么?有机体生命的基础和起源是什么?计算机科学同样有它自己的基本问题:什么是算法?什么是能计算的?什么是不能计算的?什么时候可以认为一个算法是实际可行的?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章中字符串处理装置的相当简单的推广,结果令人吃惊地成为描述任意算法的一般框架。为了证明这一点,即通常所说的ChurchTuring论题,我们引入越来越复杂的计算模型(Turing机更强的变种,还有随机存取Turing机和递归定义的数值函数),并且证明它们在能力上全都完全等价于基本的Turing机模型。
再下一章处理不可判定性。某些自然的明确的计算任务具有这种出人意料的性质,可以证明它们超出了算法能够解决的范围。例如,问你是否能用给定的若干种形状的砖铺整个平面。如果这些形状中包括一个正方形,或者甚至一个三角形,则答案显然是“能够”。但是,如果是几种稀奇古怪的形状,或者规定几种形状必须至少使用一次,那会怎样?这肯定是很复杂的问题,你想用机器给出回答。在第5章我们使用Turing机的形式表示证明这个问题和许多其他问题是根本不可能用计算机解决的。
即使当一项计算任务能够用某个算法解决的时候,也可能不存在解决它的适当快的、实际可行的算法。在本书的最后两章,我们说明怎么用它们的复杂性对现实生活中的计算问题进行分类:某些问题能够在合理的,即多项式的时间界限内解决,而另一些问题似乎需要以天文速度,即指数地增长的时间。在第7章我们定义一个叫做NP完全的问题类,它们是一些普通的、实际的、但难得出名的问题(旅行商问题仅是它们中的一个)。我们证明所有这些问题在下述意义下是等价的:如果它们中的一个有有效的算法,则它们每一个都有有效的算法。普遍地相信所有NP完全问题具有固有的指数复杂度;这个猜想是否实际上为真是著名的P≠NP问题,它是当代数学家和计算机科学家面临的最重要和最深刻的问题之一。
本书有很多篇幅是有关算法及其形式基础的。然而,大概你也意识到了,在今天的计算机科学教学计划中,算法课程,包括算法的分析和设计,相当地脱离计算理论的课程。在本书的现行版本中,我们试图恢复这门课程的某种统一性。结果是,本书对算法也提供了相当不错的介绍,只是有些专门和非传统。在第1章形式地介绍算法及其分析,并且在第2章和第3章研究受限制的计算模型和由它们产生的自然的计算问题的时候一再重新提起。这样一来,在后面探索算法的一般模型的时候,读者处在较好的位置,能正确评价这种探索的目标并且断定是能成功的。在讲解复杂性时算法同样担任主角。因为鉴别复杂问题的最好方法是把它与另一个经得起有效算法考验的问题进行比较。最后一章用一节叙述对付NP完全性作为结束,给出在遇到NP完全问题时已经成功地使用过的算法技术(近似算法、穷举算法、启发式局部搜索等)。
计算是必不可少的、有力的、优美的、具有挑战性和不断发展的——它的理论也是如此。本书仅讲了一个激动人心的故事的开头,它是对从计算理论宝库中精选出的少量基本论题的朴素介绍。我们希望它将激发读者去作进一步的探索,每一章最后的参考文献指出了好的出发点。

计算理论基础(第2版)图书目录

编辑
第一版序言(Ⅴ)
第二版序言(Ⅶ)
导言(Ⅸ)
第1章集合、关系和语言(1)
11集合(1)
12关系与函数(4)
13特殊类型的二元关系(7)
14有穷集合与无穷集合(11)
15三个基本的证明技术(13)
16闭包与算法(17)
17字母表与语言(25)
18语言的有穷表示(29)
参考文献(33)
第2章有穷自动机(34)
21确定型有穷自动机(34)
22非确定型有穷自动机(39)
23有穷自动机与正则表达式(47)
24正则语言与非正则语言(54)
25状态最小化(58)
26关于有穷自动机的算法(65)
参考文献(70)
第3章上下文无关语言(72)
31上下文无关文法(72)
32语法分析树(79)
33下推自动机(83)
34下推自动机与上下文无关文法(87)
35上下文无关语言与非上下文无关语言(92)
36关于上下文无关文法的算法(97)
37确定性与语法分析(102)
参考文献(115)
第4章Turing机(117)
41Turing机的定义(117)
42用Turing机计算(125)
43Turing机的扩充(130)
44随机存取Turing机(136)
45非确定型Turing机(144)
46文法(148)
47数值函数(151)
参考文献(158)
第5章不可判定性(160)
51ChurchTuring论题(160)
52通用Turing机(161)
53停机问题(163)
54与Turing机有关的不可判定问题(166)
55与文法有关的不可解问题(168)
56不可解的铺砖问题(172)
57递归语言的性质(174)
参考文献(178)
第6章计算复杂性(179)
61P类(179)
62若干问题(181)
63布尔可满足性(187)
64NP类(190)
参考文献(194)
第7章NP完全性(196)
71多项式时间归约(196)
72Cook定理(202)
73其他的NP完全问题(207)
74对付NP完全性(218)
参考文献(229)
中英对照名词索引(231)[1] 
参考资料
  • 1.    目录  .清华大学出版社[引用日期2015-08-29]
词条标签:
文化 出版物