本书由计算理论领域的知名权威Michael Sipser所撰写。他以独特的视角,系统地介绍了计算理论的三个主要内容:自动机与语言、可计算性理论和计算复杂性理论。绝大部分内容是基本的,同时对可计算性和计算复杂性理论中的某些高级内容进行了重点介绍。作者以清新的笔触、生动的语言给出了宽泛的数学原理,而没有拘泥于某些低层次的细节。在证明之前,均有“证明思路”,帮助读者理解数学形式下蕴涵的概念。同样,对于算法描述,均以直观的文字而非伪代码给出,从而将注意力集中于算法本身,而不是某些模型。新版根据多年来使用本书的教师和学生的建议进行了改进,并对课堂测试题进行了全面的更新,每章末均有样例解答。
本书还配有双语电子教案,需要者可登录机工新阅读网站。
无
第1版前言
写给学生
欢迎使用本书!
将要开始学习的是重要而又引人入胜的课题:计算理论。它包括计算机硬件、软件以及某些应用的基本数学特性。这一课程试图回答什么是不能计算的,什么是能计算的,可以算多快,要用多少存储,以及采用什么计算模型等。这些问题与工程实践有着紧密的联系,也具有纯理论的一面。
许多同学主动盼望学习这门课程,有些同学可能只是为了完成计算机科学或者计算机工程的学位必需的理论课程学分——他们也许认为理论比较神秘、难学且用处不大。
通过学习,读者会发现理论既不神秘、也不讨厌,是好理解、甚至是有趣的。理论计算机科学有许多迷人而重要的思想,同时它也有许多细小的、有时甚至是乏味的细节,这些细节可能令人感到厌倦。学习任何一门新的课程都是一件艰苦的工作。但是,如果能把它适当地表述出来,学习就会变得容易和更愉快些。本书的一个基本目标是让读者接触到计算理论中真正令人激动的方面,而不陷入单调乏味之中。当然,对理论感兴趣的唯一途径是努力去学习并掌握它。
理论与实践是密切联系的,计算理论为实际工作者提供了在计算机工程中使用的理性工具。要为具体的应用设计一个新的程序设计语言吗?本课程中关于语法的内容迟早是会有用的。要进行字符串搜索和模式匹配吗?不要忘了有穷自动机和正则表达式。遇到了一个看来需要比你能够提供的计算机时间还要多的问题吗?想一想你学过的有关NP完全性的内容。各种应用领域,如现代密码协议,都依赖于在这里将要学习的理论原则。
理论是有意义的,它向读者展示了计算机新的、简单的、更加优美的一面,而通常我们把计算机看作一台复杂的机器。最好的计算机设计和应用出自完美的构思。一门理论课程可以提高审美意识,帮助读者建立更加优秀的系统。
理论是实践的指南,学习理论能够扩展你的思维。计算机技术更新很快,专门的技术知识虽然今天有用,但是仅仅在几年内就会变成过时的东西。而能力具有持久的价值,课程应该注重培养思考能力、清楚准确的表达能力、解决问题的能力以及知道问题什么时候还没有解决的能力,理论能够训练这些能力。
除了实际的考虑,几乎每一位使用计算机的人都想了解这个神奇的创造,它的能力,以及它的局限性。为了解答某些基本问题,在过去的30年里,一个全新的数学分支已经确立。这里还有一个重大问题没有解决:如果给定大的自然数,例如有500位,能够在合理的时间内把它分解成素数的乘积吗?即使使用一台超级计算机,现今还没人知道怎样才能在宇宙毁灭之前做完这件事!因子分解问题与现代密码系统中的某些密码有关。去寻找一个快速的因子分解方法吧,也许,读者会因此而一举成名!
写给教师
本书是计算机学科高年级本科生或研究生的计算理论入门教材。它涉及计算理论的数学论述,包括叙述和证明定理的基本技能。作者努力使本书适用于那些缺乏定理证明的基本训练的学生,当然,有较多这种经验的学生会学习得更轻松。
强调清楚和生动是本书叙述的一个特色,本课程对某些低层次的细节强调了直觉和“大的轮廓”。例如,虽然在第0章介绍了证明的归纳法以及其他的数学预备知识,但在后面部分它并不是重点。关于自动机的各种构造方法的正确性,一般不用归纳证明。只要叙述清楚,这些构造方法已经是令人信服的,不需进一步论证。归纳证明反而可能把学生搞糊涂而不是给人以启迪。归纳法是比较复杂的技术,可能还有些神秘。对十分明显的事情用归纳法作反复的说明可能会化简为繁、违反初衷,使学生认为数学证明是一种形式化手法,而不是教给他们懂得什么是有说服力的证据,什么不是有说服力的证据。
本书第二部分和第三部分没有采用伪码描述算法,而用了自然语言描述。书中没有花很多时间去设计图灵机(或任何其他形式模型)的程序。现在的学生都有程序设计的经历,觉得丘奇图灵论题是不言自明的。因此我不去用很长的篇幅叙述用一个模型模拟另一个模型来说明它们的等价性。
除增加直观性和压缩某些细节外,本书内容组织符合计算理论中的典型标准。理论工作者将发现,素材的选取、术语以及内容的前后顺序都与其他广泛使用的教材一致。只在少数地方,当我发现标准的术语十分模糊或会引起混淆时,才引进了新的术语。例如,引进名词映射可归约性代替多一可归约性。
习题是学习与数学相关的科学必不可少的环节。书中的习题分成两大类,练习用来复习定义和概念。问题需要多动些脑筋。带星号的问题更难一些。本书努力使练习和问题令人感兴趣,并有挑战性。
反馈给作者
互联网为作者与读者之间的交流提供了新的机会。我收到很多电子邮件,对本书的初版提出了建议、赞许和批评,或者指出错误。请继续来函。只要有时间,我尽量亲自给每一个人回信。与本书有关的电子邮箱是
sipserbook@math.mit.edu
另外,还有一个Web站点,包括一张勘误表。可能还有一些其他材料也要加入这个站点用来帮助教师和学生。请告诉我你希望在这里看到什么。这个站点的地址是
http://www.math.mit.edu/~sipser/book.html
致谢
如果没有众多朋友、同事以及家人的帮助,我将无法完成这本书。
我要感谢帮助我形成科学观和教育风格的各位老师,其中有五位非常突出。尤其是我的论文指导导师 Manuel Blum,他以独有的方式激励学生,充分展现了他的激情和关怀。他是我和许多人的楷模。感谢Richard Karp将我领入复杂性理论的大门;John Addison为我讲授逻辑并布置了那些精彩的家庭作业;Juris Hartmanis使我了解了计算理论;还有我的父亲,他告诉了我什么是数学、计算机以及教学艺术。
本书源自我在麻省理工学院讲授了15年的一门课程的教案和笔记。班上的学生们通过我的讲解做了课程笔记,希望他们原谅我不能将所有人一一列出。我多年的助教 Avrim Blum、Thang Bui、Andrew Chou、Benny Chor、Stavros Cosmadakis、Aditi Dhagat、Wayne Goddard、Parry Husbands、Dina Kravets、Jakov Kucˇan、Brian O’Neill、Ioana Popescu 以及 Alex Russell帮助我编辑和充实了这些笔记,并提供了部分家庭作业问题。
大约三年前,Tom Leighton 建议我写一本关于计算理论的教科书。我也曾多次有过这个念头,但正是Tom的建议才使我付诸行动。我非常感激和珍视他对于本书写作和其他许多事情的慷慨建议。
我还想感谢Eric Bach、Peter Beebee、Cris Calude、Marek Chrobak、Anna Chefter、GuangIen Cheng、Elias Dahlhaus、Michael Fischer、Steve Fisk、Lance Fortnow、Henry JFriedman、Jack Fu、Seymour Ginsburg、Oded Goldreich、Brian Grossman、David Harel、Micha Hofri、Dung THuynh、Neil Jones、HChad Lane、Kevin Lin、Michael Loui、Silvio Micali、Tadao Murata、Christos Papadimitriou、Vaughan Pratt、Daniel Rosenband、Brian Scassellati、Ashish Sharma、Nir Shavit、Alexander Shen、Ilya Shlyakhter、Matt Stallmann、Perry Susskind、YCTay、Joseph Traub、Osamu Watanabe、Peter Widmayer、David Williamson、Derick Wood以及Charles Yang 所提供的意见和建议,以及他们在本书写作过程中提供的帮助。
下述各位为本书的改进提供了意见:Isam MAbdelhameed、Eric Allender、Shay Artzi、Michelle Atherton、Rolfe Blodgett、AI Briggs、Brian EBrooks、Jonathan Buss、Jin Yi Cai、Steve Chapel、David Chow、Michael Ehrlich、Yaakov Eisenberg、Farzan Fallah、Shaun Flisakowski、Hjalmtyr Hafsteinsson、CRHale、Maurice Herlihy、Vegard Holmedahl、Sandy Irani、Kevin Jiang、Rhys Price Jones、James MJowdy、David MMartin Jr、Manrique MataMontero、Ryota Matsuura、Thomas Minka、Farooq Mohammed、Tadao Murata、Jason Murray、Hideo Nagahashi、Kazuo Ohta、Constantine Papageorgiou、Joseph Raj、Rick Regan、Rhonda AReumann、Michael Rintzler、Arnold LRosenberg、Larry Roske、Max Rozenoer、Walter LRuzzo、Sanatan Sahgal、Leonard Schulman、Steve Seiden、Joel Seiferas、Ambuj Singh、David JStucki、Jayram SThathachar、HVenkateswaran、Tom Whaley、Christopher Van Wyk、Kyle Young以及Kyoung Hwan Yun。
Robert Sloan在他执教的一个班上使用了本书手稿的早期版本,并通过使用经验向我提供了宝贵的意见和想法。Mark Herschberg、Kazuo Ohta和Latanya Sweeney通读了手稿的各部分并提供了广泛的改进建议。Shafi Goldwasser为我提供了第10章的素材。
我得到了William Baxter专业的技术支持,他编写了实现内部设计的宏语言包LATEX。麻省理工学院数学系的Larry Nolan保证了所有事务的正常进行。
同PWS出版社的人们一起工作创作最终作品是一件很愉快的事。我在此感谢Michael Sugarman、David Dietz、Elise Kaiser、Monique Calello、Susan Garland和Tanja Brull,因为我和他们的接触最为频繁,但我知道还有许多人也为此付出了努力。感谢Jerry Moore的审稿、Diane Levy的封面设计以及Catherine Hawkes的版式设计。
感谢美国国家科学基金项目CCR9503322给予的支持。
我的父亲Kenneth Sipser和姐姐Laura Sipser将书中的图表转换成了电子格式。我的另一位姐姐 Karen Fisch为我们解决了许多使用电脑的紧急问题,我的母亲Justine Sipser用她那慈母的建议帮助我。感谢他们在疯狂的截止时间、糟糕的软件等困难环境下的付出。
最后,是我所爱的妻子Ina和我的女儿Rachel,感谢她们对所有这一切的理解和容忍。
Michael Sipser
马萨诸塞州,剑桥
1996年10月
第2版前言
大量读者来的电子邮件反映,第1版没有习题解答是一个缺陷。这一版弥补了这一缺陷。每一章现在都增加了“习题选解”小节,给出了该章的练习和问题中有代表性题目的答案。给出了答案的问题就不能再作为有趣的有挑战性的家庭作业,为弥补这一损失,又添加了若干新问题。教师可以和wwwcoursecom上所指定的相应地区的销售代表联系,索取一份教师手册,其中包含了附加的答案。
第2版的国际版是针对国外读者的。尽管涵盖了同样的主题,它和标准第2版还是有所不同,并且不是用来替代标准第2版的。
许多读者更喜欢学习更多的“标准”主题,比如MyhillNerode定理和Rice定理。通过将这些主题展示在给出答案的问题中,我部分地采纳了这些读者的意见。没有将MyhillNerode定理放到书本主体中是因为我认为,这门课程的目标是初步介绍而非深入研究有穷自动机。有穷自动机在这里的角色是使学生通过研究计算的简单形式模型,从而为了解复杂模型奠定基础,同时为后续的主题提供方便的例子。当然,一些人希望有更全面的内容,同时另一些人觉得应该略去所有对有穷自动机的引用(或者至少是依赖)。尽管Rice定理对于不可判定性的证明是一个有用的“工具”,第2版还是没有将它放到书本主体中,因为一些学生可能只是机械地使用它而没有真正理解其作用。换用归约来证明不可判定性,可以为学习复杂性理论中出现的归约做更好的准备。
我很感谢我的助教Ilya Baran、Sergi Elizalde、Rui Fan、Jonathan Feldman、Venkatesan Guruswami、Prahladh Harsha、Christos Kapoutsis、Julia Khodor、Adam Klivans、Kevin Matulef、Ioana Popescu、April Rasala、Sofya Raskhodnikova和Iuliu Vasilescu,他们帮助我草拟了若干新问题及其答案。Ching Law、Edmond Kayi Lee和Zulfikar Ramzan也为给出答案付出了努力。感谢Victor Shoup提出了一个简洁的方法,用于修整在第1版中出现在概率原始算法分析中的缺陷。
感谢Course Technology出版社的编辑们的努力,尤其是Alyssa Pratt和Aimee Poirier。多谢Gerald Eisman、Weizhen Mao、Rupak Majumdar、Chris Umans和Christopher Wilson所做的审校。感谢Jerry Moore在编辑上的出色工作,还有ByteGraphics的Laura Segel (lauras@bytegraphicscom) 精彩而又精确的图表再现。
我所收到的电子邮件数量超乎预料。收到来自这么多地方的这么多人的来信绝对是一种快乐。我会尽量回复并向我未曾回复者表示歉意。我在此列出对本书第2版做出了有益的建议的人,同时对所有给我来信的人表示感谢。
Luca Aceto,Arash Afkanpour,Rostom Aghanian,Eric Allender,Karun Bakshi,Brad Ballinger,Ray Bartkus,Louis Barton,Arnold Beckmann,Mihir Bellare,Kevin Trent Bergeson,Matthew Berman,Rajesh Bhatt,Somenath Biswas,Lenore Blum,Mauro ABonatti,Paul Bondin,Nicholas Bone,Ian Bratt,Gene Browder,Doug Burke,Sam Buss,Vladimir Bychkovsky,Bruce Carneal,Soma Chaudhuri,RongJaye Chen,Samir Chopra,Benny Chor,John Clausen,Allison Coates,Anne Condon,Jeffrey Considine,John JCrashell,Claude Crepeau,Shaun Cutts,Susheel MDaswani,Geoff Davis,Scott Dexter,Peter Drake,Jeff Edmonds,Yaakov Eisenberg,Kurtcebe Eroglu,Georg Essl,Alexander TFader,Farzan Fallah,Faith Fich,Joseph EFitzgerald,Perry Fizzano,David Ford,Jeannie Fromer,Kevin Fu,Atsushi Fujioka,Michel Galley,KGanesan,Simson Garfinkel,Travis Gebhardt,Peymann Gohari,Ganesh Gopalakrishnan,Steven Greenberg,Larry Griffith,Jerry Grossman,Rudolf de Haan,Michael Halper,Nick Harvey,Mack Hendricks,Laurie Hiyakumoto,Steve Hockema,Michael Hoehle,Shahadat Hossain,Dave Isecke,Ghaith Issa,Raj DIyer,Christian Jacobi,Thomas Janzen,Mike DJones,Max Kanovitch,Aaron Kaufman,Roger Khazan,Sarfraz Khurshid,Kevin Killourhy,Seungjoo Kim,Victor Kuncak,Kanata Kuroda,Suk YLee,Edward DLegenski,LiWei Lehman,Kong Lei,Zsolt Lengvarszky,Jeffrey Levetin,Baekjun Lim,Karen Livescu,Thomas Lasko,Stephen Louie,TzerHung Low,Wolfgang Maass,Arash Madani,Michael Manapat,Wojciech Marchewka,David MMartin Jr,Anders Martinson,Lyle McGeoch,Alberto Medina,Kurt Mehlhorn,Nihar Mehta,Albert RMeyer,Thomas Minka,Mariya Minkova,Daichi Mizuguchi,GAllen Morris Ⅲ,Damon MoskAoyama,Xiaolong Mou,Paul Muir,German Muller,Donald Nelson,Gabriel Nivasch,Mary Obelnicki,Kazuo Ohta,Thomas MOleson,Jr,Curtis Oliver,Owen Ozier,Rene Peralta,Alexander Perlis,Holger Petersen,Detlef Plump,Robert Prince,David Pritchard,Bina Reed,Nicholas Riley,Ronald Rivest,Robert Robinson,Christi Rockwell,Phil Rogaway,Max Rozenoer,John Rupf,Teodor Rus,Larry Ruzzo,Brian Sanders,Cem Say,Kim Schioett,Joel Seiferas,Joao Carlos Setubal,Geoff Lee Seyon,Mark Skandera,Bob Sloan,Geoff Smith,Marc LSmith,Stephen Smith,Alex CSnoeren,Guy StDenis,Larry Stockmeyer,Radu Stoleru,David Stucki,Hisham MSueyllam,Kenneth Tam,Elizabeth Thompson,Michel Toulouse,Eric Tria,Chittaranjan Tripathy,Dan Trubow,Hiroki Ueda,Giora Unger,Kurt LVan Etten,Jesir Vargas,Bienvenido VelezRivera,Kobus Vos,Alex Vrenios,Sven Waibel,Marc Waldman,Tom Whaley,Anthony Widjaja,Sean Williams,Joseph NWilson,Chris Van Wyk,Guangming Xing,Vee Voon Yee,Cheng Yongxi,Neal Young,Timothy Yuen,Kyle Yung,Jinghua Zhang,Lilla Zollei。
当我夜以继日地坐在我的电脑屏幕前时,尤其要感谢我的家人Ina、Rachel和Aaron的耐心、理解和爱。
Michael Sipser
马萨诸塞州,剑桥
2004年12月
本书由计算理论领域的知名权威Michael Sipser所撰写。他以独特的视角,系统地介绍了计算理论的三个主要内容:自动机与语言、可计算性理论和计算复杂性理论。绝大部分内容是基本的,同时对可计算性和计算复杂性理论中的某些高级内容进行了重点介绍。作者以清新的笔触、生动的语言给出了宽泛的数学原理,而没有拘泥于某些低层次的细节。在证明之前,均有“证明思路”,帮助读者理解数学形式下蕴涵的概念。同样,对于算法描述,均以直观的文字而非伪代码给出,从而将注意力集中于算法本身,而不是某些模型。新版根据多年来使用本书的教师和学生的建议进行了改进,并对课堂测试题进行了全面的更新,每章末均有样例解答。 本书还配有双语电子教案,需要者可登录华章网站。
唐常杰 陈鹏 向勇 刘齐宏:唐常杰: 1981年在四川大学数学系获硕士学位,1983~1986在美国南加利福尼亚大学师从Seymour Ginsburg,现为四川大学教授,博士生导师。目前主要研究方向包括数据库、数据挖掘和基因表达式编程。出版专著四部、教科书五本,发表研究论文两百余篇,被SCI、EI检索50余篇。承担过国家自然科学基金和教育部基金项目共10项。曾获四川省科技进步二等奖两项,光华科技奖励基金二等奖和全国优秀科技图书二等奖。担任多个国际会议的程序委员会委员或主席,是中国计算机学会数据库专业委员会副主任,第六届网络时代信息管理(WAIM 2005)大会主席,四川省学术和技术带头人。主页:http://csscueducn/~tangchangjie
陈鹏: 四川大学讲师。曾获2005年中国青年实用软件设计大赛铜奖。主要研究方向为数据库与知识工程、图形图像。
向勇: 四川大学计算机软件与理论硕士,现为成都电子机械高等专科学校计算机工程系讲师。主要研究方向包括数据库与知识工程和基因表达式编程。
刘齐宏: 刘齐宏副教授。曾承担10余项省、市科技应用项目,在两项国家自然科学基金项目作主研,曾获四川省“科学技术进步人文社会科学科研成果奖”三等奖一项。现主要研究方向为数据库、数据挖掘、基因表达式编程、机器学习和专家系统。
五年前为计算理论课程选择教材时,海外友人介绍了眼前这本由麻省理工学院的名师Michael Sipser编写的名著。五年教学实践表明,此书前三章可供高年级本科生选修,后七章足够研究生钻研,是同类教材中我教得最愉悦、学生学起来最有兴趣的一本教科书。
计算理论是一门理论修养课,很难断言某章某节能够立竿见影地用于读者的某项科研。我的学生(攻读数据库、数据挖掘和知识工程方向)学习此课一两年后,以过来人身份发出感慨,这门课使他们思路开阔、思维严密、观点提高、点子增多,从而终身受益。在他们的工程性论文中,也不时出现关于可计算性和复杂度方面的亮点,提高了论文的深度和质量。
26年前初入此门时,读过JDUllman和JEHopcroft的书以及SEilenberg的名著《语言、自动机和机器》,在SGinsburg门下研究数据库理论时,学过他的大师之作《前后文无关语言理论》,教学中也用过HRLewis的《计算理论基础》。上述书籍都是好书,但对于非纯理论方向的初学者,还是觉得Michael Sipser的这本书更为合适。
本书以注重思路、深入引导为特色。全书勾画了理论计算机科学的知识框架,囊括了形式语言、自动机、可计算性和计算复杂度等重要主题,试图为读者的计算机生涯奠定一个宽广坚实的理论基础。作者强调思想方法,难点均以思路先行;介绍背景如远山淡抹,化繁为简似近水浓描;释难以例,不拘泥于技术细节,铺垫伏笔,常迸发在数章之后。这些亮点表现了作者对问题的深刻理解和娴熟的教学艺术。每一主题的后部都给出精彩结果以作启发,展示待解问题以设悬念,引导读者向此领域中的高层次问题攀登。全书文笔流畅,读来亲切,开卷读之概念易懂,合书思之脉络不忘。
在同类书被采用的列表中,本书已名列前茅。2005年12月,在Google中以作者名和书名搜索到相关项目8420项。在http://wwwamazoncom/gp/product/customerreviews 中有许多读者评论此书“best”、“one of the best”,也有人批评此书第1版无习题解答。所幸,第2版已弥补这一不足。新版修正了若干印刷错误,字句更加流畅,增加了部分内容、部分启发性习题、部分难题解答和教学辅助材料。一些重要内容,如MyhillNerode 定理和Rice 定理放到了专门的小节。在译文中,新概念首次出现时,大都标注了英文原文,另根据作者在网上发布的勘误表,对原文的个别错误做了校正;翻译过程中发现了少量尚未勘误的错误,翻译团队仔细讨论后,做了校正;按字母顺序列出了中英文对照原书索引术语。
翻译过程采用了团队模式。在初译后,进行了几次工作量更大的轮换修改和校正,全书由唐常杰统校。团队每位成员的工作都涉及了一半以上章节。本书由唐常杰、陈鹏、向勇、刘齐宏主译,刘胤田、朱明放、曾涛、段磊和李川都付出了艰辛的劳动。翻译团队成员在几年前读过由北京大学张立昂教授、王捍贫教授和黄雄老师合作翻译的第1版,翻译中不可避免地受到他们准确的词汇、流畅的文风的影响。在此意义上,新版译者不过是接过了先行者的接力棒,再把接力赛推进了一程。借此机会,对三位先行者表示衷心的感谢。
在五年的教学实践中,译者积累了800多页的PPT双语电子教案,一直放在出版社和个人网页上供自由下载,奉献给我国的读者。(参见机械工业出版社华章分社主页http://wwwhzbookcom或http://211831202/~tangchangjie/teach/tang_techinghtm。)
译者序译者序由于水平所限,译文难免有错误和不妥之处,恳请读者批评指正。
唐常杰
2006年1月于四川大学 竹林村
第0章绪论
01自动机、可计算性与复杂性
011计算复杂性理论
012可计算性理论
013自动机理论
02数学概念和术语
021集合
022序列和多元组
023函数和关系
024图
025字符串和语言
026布尔逻辑
027数学名词汇总
03定义、定理和证明
04证明的类型
041构造性证明
042反证法
043归纳法
练习
问题
习题选解
第一部分 自动机与语言
第1章正则语言
11有穷自动机
111有穷自动机的形式化定义
112有穷自动机举例
113计算的形式化定义
114设计有穷自动机
115正则运算
12非确定性
121非确定型有穷自动机的形式化定义
122NFA与DFA的等价性
123在正则运算下的封闭性
13正则表达式
131正则表达式的形式化定义
132与有穷自动机的等价性
14非正则语言
练习
问题
习题选解
第2章上下文无关文法
21上下文无关文法概述
211上下文无关文法的形式化定义
212上下文无关文法举例
213设计上下文无关文法
214歧义性
215乔姆斯基范式
22下推自动机
221下推自动机的形式化定义
222下推自动机举例
223与上下文无关文法的等价性
23非上下文无关语言
练习
问题
习题选解
第二部分可计算性理论
第3章丘奇图灵论题
31图灵机
311图灵机的形式化定义
312图灵机的例子
32图灵机的变形
321多带图灵机
322非确定型图灵机
323枚举器
324与其他模型的等价性
33算法的定义
331希尔伯特问题
332描述图灵机的术语
练习
问题
习题选解
第4章可判定性
41可判定语言
411与正则语言相关的可判定性问题
412与上下文无关语言相关的可判定性问题
42停机问题
421对角化方法
422停机问题是不可判定的
423一个图灵不可识别语言
练习
问题
习题选解
第5章可归约性
51语言理论中的不可判定问题
52一个简单的不可判定问题
53映射可归约性
531可计算函数
532映射可归约性的形式定义
练习
问题
习题选解
第6章可计算性理论的高级专题
61递归定理
611自引用
612递归定理的术语
613应用
62逻辑理论的可判定性
621一个可判定的理论
622一个不可判定的理论
63图灵可归约性
64信息的定义
641极小长度的描述
642定义的优化
643不可压缩的串和随机性
练习
问题
习题选解
第三部分复杂性理论
第7章时间复杂性
71度量复杂性
711大O和小o记法
712分析算法
713模型间的复杂性关系
72P类
721多项式时间
722P中的问题举例
73NP类
731NP中的问题举例
732P与NP问题
74NP完全性
741多项式时间可归约性
742NP完全性的定义
743库克列文定理
75几个NP完全问题
751顶点覆盖问题
752哈密顿路径问题
753子集和问题
练习
问题
习题选解
第8章空间复杂性
81萨维奇定理
82PSPACE类
83PSPACE完全性
831TQBF问题
832博弈的必胜策略
833广义地理学
84L类和NL类
85NL完全性
86NL等于coNL
练习
问题
习题选解
第9章难解性
91层次定理
92相对化
93电路复杂性
练习
问题
习题选解
第10章复杂性理论高级专题
101近似算法
102概率算法
1021BPP类
1022素数性
1023只读一次的分支程序
103交错式
1031交错式时间与交错式空间
1032多项式时间层次
104交互式证明系统
1041图的非同构
1042模型的定义
1043IP=PSPACE
105并行计算
1051一致布尔电路
1052NC类
1053P完全性
106密码学
1061密钥
1062公钥密码系统
1063单向函数
1064天窗函数
练习
问题
习题选解
参考文献
索引