科技>计算机>计算机科学
算法分析导论(第2版)

算法分析导论(第2版)"

作者:常青,左飞
ISBN:9787121353680
定价:¥128.0
字数:581千字
页数:424
出版时间:2018-11
开本:16开
版次:01-01
装帧:
出版社:电子工业出版社
简介

本书全面介绍了算法的数学分析所涉及的主要技术。涵盖的内容来自经典的数学课题(包括离散 数学、初等实分析、组合数学),以及经典的计算机科学课题(包括算法和数据结构)。本书的重点是“平均情况”或“概率性”分析,书中也论述了“最差情况”或“复杂性”分析所需的基本数学工具。本书第1 版为行业代表性著作,第2 版不仅对书中图片和代码进行了更新,还补充了新章节。全书共9 章,第1 章是导论;第2~5 章介绍数学方法;第6~9 章介绍组合结构及其在算法分析中的应用。除每章包含的大量习题以及参考文献外,本书特设配套免费学习网站,为读者提供了很多关于算法分析的补充材料,包括课件和相关网站的链接,帮助读者提高学习兴趣,完成更深入的学习。

前言

译者序 公元 2014年的冬天,一部讲述计算机科学之父艾伦·图灵( Alan Turing)传奇人生的传记电影在美国上映,这部影片就是《模仿游戏》。次年,该片荣获第 87届奥斯卡金像奖最佳改编剧本奖,以及包括最佳影片、最佳导演、最佳男主角、最佳女配角在内的 7项提名,一时风光无限。 图灵一生最重要的三大贡献包括图灵机、图灵测试,以及破译 Enigma密码机,其中的每一项都值得全世界感谢和纪念他。在提出图灵测试的论文中,图灵石破天惊地预言了创造出具有真正智能的机器的可能性,这也是后来人工智能研究的源头。事实上,《模仿游戏》这个名字正是图灵那篇著名论文第 1章的标题。后人为了纪念图灵对计算机科学所做出的巨大贡献,也将该领域的最高奖命名为“图灵奖”。另一方面,破译 Enigma密码更是直接帮助盟军在战场上取得先机,甚至拯救了无数人的性命并最终导致第二次世界大战反法西斯阵营的全面胜利。 尽管前面提到的两大贡献已是功若丘山,但笔者这里将从图灵的另外一个贡献— —“图灵机”谈起,因为这与本书所要讨论的话题息息相关。不过,为此我们还得把时间再往前推。1900年,德国数学家大卫·希尔伯特( David Hilbert)在巴黎举行的国际数学家大会上做了题为《数学问题》的演讲。在这篇重要的演讲中,他提出了著名的希尔伯特之 23个问题。尽管此后的数学发展远远超过了希尔伯特的预料,但他所提出的 23个问题仍然对 20世纪的数学发展起到了重要的推动作用。 希尔伯特的第 10个问题是要设计一个算法来测试多项式是否有整数根。他没有使用“算法”这个术语,而是采用了下面这种表述:“通过有限多次运算就可以决定的过程。”有意思的是,从希尔伯特对这个问题的陈述中可以看出,他明确地要求设计一个算法。因此,他显然是假设这样的算法存在,人们所要做的只是找到它。现在我们知道,这个任务是无法完成的,即它是算法上不可解的。但对那个时期的数学家来说,以他们对算法的直观认 算法分析导论(第 2版) 识,得出这样的结论是不可能的。非形式地说,算法是为实现某个任务而构造的简单指令集。用日常用语来说,算法又被称为过程或者方法。算法在数学中也起着非常重要的作用。古代数学文献中就包含执行各种各样计算任务的算法描述。例如,我国古代数学经典《九章算术》中就记述了包括求最大公约数、最小公倍数、开平方根、开立方根等在内的诸多算法。虽然算法在数学中已有很长的历史,但在 20世纪之前,算法本身一直没有精确的定义。数学家们面对希尔伯特的第 10个问题显得束手无策。由于缺乏对算法本身的精确定义,所以要证明某个特定任务不存在算法就更不可能了。要想破解希尔伯特的第 10个问题,人们不得不等待算法的精确定义的出现。直到 1936年,曙光似乎出现了。图灵向伦敦的权威数学杂志递交了一篇题为《论数字计算在决断难题中之应用》的论文。该文最终于 1937年正式发表,并立即引起了广泛关注。在论文中,图灵描述了一种可以辅助数学研究的机器,也就是后来被称为“图灵机”的抽象系统。与此同时,另外一位数学家阿隆佐·丘奇( Alonzo Church)也独立地提出了另外一套系统,即所谓的 Lambda演算。图灵采用他的图灵机来定义算法,而丘奇则采用 Lambda演算来定义算法,后来图灵证明这两个定义是等价的。由此,人们在算法的非形式概念和精确定义之间建立了联系,即算法的直觉概念等价于图灵机,这就是所谓的“丘奇-图灵”论题。“丘奇-图灵”论题提出的算法定义是解决希尔伯特第 10个问题所需的。而第 10个问题的真正解决则要等到 1970年,借助于丘奇与图灵的杰出贡献,马提亚塞维齐( Yuri Matiyasevich)在戴维斯(Martin Davis)、普特纳姆(Hilary Putnam)和罗宾逊(Julia Robinson)等人工作的基础上,最终证明检查多项式是否有整数根的算法是不存在的。上述四人的名字也紧紧地同希尔伯特的第 10个问题联系在了一起。破解希尔伯特的第 10个问题的过程更像一场声势浩大又旷日持久的国际协作和学术接力。每个人的工作都必不可少,而且大家都感觉已经相当接近问题的最终答案。后来的历史见证了马提亚塞维齐敏锐地接过最后一棒并完成终点冲刺的伟大一幕。更有意思的是,彼时正值美苏冷战最为紧张的时期,两个超级大国之间的正常学术交流几乎完全中断。但这或许就是科学无国界的一个重要体现,尽管国家层面上双方剑拔弩张,而科学家在私下仍然以一种惺惺相惜的默契方式彼此神交。特别是在得知苏联数学家完成了最终的证明时,美国同行都表现得相当振奋和由衷的喜悦,这不得不说是学术界的一段佳话。回顾建立算法形式化定义和破解希尔伯特之第 10个问题的那段风起云涌的历史,我们不得不由衷地感叹:算法对于我们的世界是多么重要。可以这样说,自计算机科学诞生之日起,关于算法的研究就一直是一个核心话题。现代计算机科学中充满了各种各样的算法, 译者序 V 许多图灵奖得主也正是因提出的各种经典算法而闻名于世。例如,提出单源最短路径算法的迪可斯特朗( Edsger Dijkstra)①、提出字符串匹配算法的高德纳( Donald Knuth)②、提出多源最短路径算法的弗洛伊德( Robert Floyd)③,以及提出快速排序算法的霍尔( Antony Hoare)④等。其中,高德纳是最年轻的图灵奖得主这一纪录的保持者(获奖时年仅 36岁),并以计算机算法设计与分析领域的经典巨著《计算机程序设计艺术》而广为人知。 作为导师,高德纳一生共指导过 28位博士生,而本书作者之一的罗伯特·塞奇威克(Robert Sedgewick)便是其中之一。塞奇威克曾经是普林斯顿大学计算机科学系的创立者暨 首任系主任,他同时还是著名的 Adobe公司的董事。作为一位世界知名的计算机科学家, 塞奇威克于 1997年当选 ACM(Association for Computing Machinery,国际计算机学会)院 士,并因从“对称二叉树”中导出了红黑树而享誉计算机界。 塞奇威克与费利佩·弗拉若莱( Philippe Flajolet)曾合作撰写过数本算法分析领域的著作,本书即为其中一部在全世界范围内广泛流传的经典之作。弗拉若莱是一名法国计算机科学家,法国科学院院士,同时也被称为“分析组合学之父”。他与合作者共同提出的 Flajolet-Martin算法更是当今互联网与大数据时代背景下,网站分析统计的重要基石。 然而,天妒英才, 2011年 3月,休假期间的塞奇威克惊悉多年的老友弗拉若莱突然离世。悲痛万分的塞奇威克怀着对逝者的无限缅怀写了感人至深的悼词:“弗拉若莱的离世意味着很多秘密再也无法揭开。但他给世人留下了很多追随他脚步的继承者,他们可再续他的数学梦想。”在这样的背景下,塞奇威克以极大的热情投入工作,历经数百个日夜,终于在 2012年 10月将本书的第 2版付梓。塞奇威克坚信弗拉若莱的精神会在后来人的工作中得到永生,进而希冀本书读者能够循着弗拉若莱的脚步,继续追求他的数学梦想。 本书全面系统地介绍了算法分析中需要使用的基本技术,所涉及的内容既来自包括离散数学、组合数学、概率论等在内的经典数学问题,也有来自算法及数据结构等计算机科学问题。像递归、母函数、树形结构、字符串、映射以及散列等算法分析话题均有讨论。可以说本书是一本研究算法分析的权威之作。 作为译者,我们希望自图灵以来的算法研究能够在更宽阔的范围内,被更光大地发扬,尤其希望中国的计算机科研人员能够从本书中找到启迪研究工作的智慧。同时,也希望通过本书向神交已久的两位大师——弗拉若莱和塞奇威克送上最崇高的敬意。 ① 1972年图灵奖得主。 ② 1974年图灵奖得主。 ③ 1978年图灵奖得主。 ④ 1980年图灵奖得主。 算法分析导论(第 2版) 最后,本书翻译工作的完成有赖于数位合作者的倾心付出,其中常青翻译了本书的第 1至 6章、左飞翻译了第 8、9章、于佳平翻译了第 7章。其他参与本书翻译和校对工作的人员还有李振坡、邵臣、叶剑、赵冰冰、贾啸天、钱文秀、丁星芸、李晓华、黄帅。自知论道须思量,几度无眠一文章。因时间和水平有限,纰漏与不足之处在所难免,译者恳切地期望广大同行及读者朋友不吝批评斧正。 序 分析算法可以给人带来两方面的快乐。其一,人们可以尽享优雅计算过程中所蕴含的让人沉醉的数学模式;其二,我们所学到的理论知识可以让自己更好更快地完成工作,这无疑是最实际的好处。 尽管数学模型只是对真实世界的一种理想化近似,但它对所有的科学活动而言都可谓是一剂灵丹妙药。在计算机科学中,数学模型往往可以精确地描述计算机程序所创造的世界,数学模型的重要性也因此大大增加了。我想,这也是为什么我在读研究生时会沉迷于算法分析,以至于这成为我迄今为止的主要工作。 但直到今天,算法分析在很大程度上还是局限在相关专业的研究生和科研人员的圈子里。算法分析的概念既不晦涩也不复杂,但确实比较新,所以相关概念的学习和使用都还需要一些时间才能成熟。 现在,经过 40余年的发展,算法分析已经非常成熟,足以成为计算机专业标准课程中的一部分。 Sedgewick和 Flajolet写的这本众人翘首以盼的教科书也因此备受欢迎。本书的作者不仅仅是这个领域的世界级专家,同时也是算法分析的布道大师。我坚信,这本书会让每一位细细品读的计算机研究人员从中获益。 D. E. Knuth 前言 本书的主要目的是介绍算法的数学分析中涉及的主要技术。涵盖的内容都来自经典的数学和计算科学领域,包括来自数学领域的离散数学、实分析基础和组合数学,来自计算机领域的算法和数据结构等。本书的重点是“平均情况”或是“概率性”的分析,对“最差情况”或“复杂度”分析所需的基本数学工具也有所涉及。 我们假设读者对计算机科学和实分析的基本概念是比较熟悉的。简单来说,读者要能够编写程序和证明定理。除此之外,本书对读者没有其他要求。 本书主要是用作高阶算法分析课程的教科书。书中涵盖了计算机专业学生所需离散数学的基本技术、组合学和重要离散结构的基本属性,因此也可以用在计算机专业的离散数学课程中。通常此类课程所涵盖的内容都比较广泛,很多教师都用自己的方法来选取其中的一部分内容教给学生,因此本书还可以用于给数学和应用数学专业的学生介绍计算机科学中与算法和数据结构有关的基本原理。 关于算法的数学分析的论文非常多,但这个领域的学生和研究人员却很难学习到该领域中广泛使用的方法和模型。本书的目标就是解决这个问题,一方面要让读者知道这个领域所面临的挑战,另一方面要让读者有足够的背景支持来学习为应对这些挑战而正在开发的工具。我们列出了相关的参考文献,因此本书可以作为研究生算法分析入门课程的基础教材,也可以用作想学习该领域中相关文献的数学或计算机领域研究人员的参考资料。 准备工作 如读者有大学一二年级或与之同等的数学基础,学习过组合学和离散数学,以及实分析、数值方法和基本数论方面的课程,将有助于理解本书中的内容(有些内容跟本书是交叉的)。本书将涉及这些领域,但我们在这里只会对必要的内容做介绍。我们会列出参考文献供想进一步学习的读者参考。 前言 IX 读者需要一到两个学期大学水平的编程经验,包括了解基本数据结构。我们不会涉及编程和具体实现的问题,但算法和数据结构是我们的核心。同数学方面的基础知识一样,在本书中我们会简要介绍基本的信息,同时列出标准教材和知识来源供读者参考。 相关书籍 与本书有关的书籍包括 D. E. Knuth写的 The Art of Computer Programming(《计算机程序设计艺术》),Sedgewick和 Wayne写的 Algorithms, Fourth Edition(《算法》,第 4版), Cormen、Leiserson、Rivest和 Stein写的 Introduction to Algorithms(《算法导论》),以及我们自己写的 Analytic Combinatorics(《分析组合论》)。本书可以作为这些书的补充材料。 从基本思路上来说,本书与 D. E. Knuth的书是最相似的。但本书的重点是算法分析中的数学技术,而 D. E. Knuth的那些书是内容更丰富的百科全书,其中算法的各种性质是主角,算法分析方法只是配角。本书可以作为学习 D. E. Knuth书中进阶内容的基础。本书还涵盖了 D. E. Knuth的书诞生之后在算法分析领域出现的新方法和新成果。 本书尽可能地涵盖各种重要、有趣的基础算法,例如, Sedgewick的《算法》(现在是第 4版了,跟 K. Wayne合著的)中所介绍的那些算法。《算法》一书涵盖了经典的排序、搜索和用于处理图和字符串的算法,本书的重点是介绍用于预测算法性能和比较算法性能优劣的数学知识。 Cormen、Leiserson、Rivest和 Stein合著的《算法导论》是算法方面的标准教材,其中 提供了关于算法设计的各种文献。《算法导论》一书(及相关的文献)关注的是算法设计和 理论,大部分是基于最差性能边界的。而本书关注的则是算法分析,尤其是各种科学研究(而不是理论研究)所需的技术。第 1章就是为此做铺垫的。本书还会介绍分析组合学,它可以让读者开阔视野,也有助于开发用于新研究的高级方法和模型,而且不局限于算法分析,它还可以用于组合学和更广泛的科学应用。那一部分对读者的数学水平要求要高一些,差不多需要本科高年级学生或研究生一年级的水平。当然,仔细阅读本书也有助于读者学习相关的数学知识。我的目标是尽可能让读者感兴趣,有动力进行更深入的学习。 如何使用这本书 本书读者在数学和计算机科学方面的知识储备肯定是不一样的。所以,读者要注意本书的结构:全书共 9章,第 1章是导论,第 2~5章介绍数学方法,最后的 4章是组合结构及其在算法分析中的应用,具体如下: 算法分析导论(第 2版) 导论 第 1章算法分析 离散数学方法 第 2章递归关系 第 3章母函数 第 4章渐近逼近 第 5章分析组合 算法与组合结构 第 6章树 第 7章排列 第 8章字符串与字典树 第 9章单词与映射 第 1章会介绍全书的主要内容,帮助读者理解本书的基本目标以及其余各章的目的。第 2~4章涵盖了离散数学中的方法,重点是基本概念和技术。第 5章是一个转折点,其中涵盖了分析组合学。计算机和计算模型的出现带来了很多新问题,这些问题往往涉及大型的离散结构。分析组合学的内容就是研究这些离散结构以解决新出现的问题的。第 6~9章则回到了计算机科学,涵盖各种组合结构的属性,它们与基本算法的关系,以及分析结果。 我们试图让本书是自包含的,本书的组织结构可以让老师很方便地根据学生和老师自己的背景及经验选取要重点讲解的部分。一种比较偏数学的教学方案是重点讲解本书第一部分的理论和证明,然后过渡到第 6~9章的相关应用。另一个比较偏计算机科学的方案是简要介绍第 2~5章的数学工具,重点放在本书第二部分与算法有关的内容。但我们的根本目标还是要让绝大部分的学生能通过本书学习到数学和计算机科学的新知识。 本书还罗列了很多参考资料以及数百个练习,鼓励读者去研究原始材料,以便更深入地研究本书中的内容。根据我们的教学经验,教师可以通过计算实验室和家庭作业,灵活地组织授课和阅读材料。本书的内容为学生深入学习诸如 Mathematica、Maple或 Sage之类的符号计算系统提供了一个很好的框架。更重要的是,对学生而言,通过比较数学研究结果和实际测试结果得出的结论是有重要价值的,不可忽略。 配套网站 本书的一个重要特点就是拥有配套的网站 aofa.cs.princeton.edu。这个网站是免费的,提 前言 XI 供了很多关于算法分析的补充材料,包括课件和相关网站的链接,其中有一些关于算法和分析组合学的网站。这些材料对讲授这些内容的教师和自学者都很有帮助。 致谢 我们非常感谢普林斯顿大学的 INRIA和 NSF(国家科学基金),它们是我们这本书的主要资助者。其他的资助来自布朗大学、欧共体( Alcom项目)、国防分析研究院、法国研究与技术部、斯坦福大学、布鲁塞尔自由大学和施乐帕克研究中心。本书历时多年才得以付梓,在此不可能一一列出诸多为本书提供支持和帮助的人和机构,我们对此深表歉意。 正如书中所说, D. E. Knuth对本书有重要的影响。过去几年,在普林斯顿、巴黎和普罗维登斯听过我讲课的学生们为本书提供了宝贵的反馈意见。全世界各地的学生和教师也为本书的第 1版提出了很多好建议。我们在此特别感谢 Philippe Dumas、Mordecai Golin、Helmut Prodinger、Michele Soria、Mark Daniel Ward和 Mark Wilson的帮助。 Ph. F.和 R. S. 1995年 9月于科孚岛 R. S. 2012年 12月于巴黎 第 2版声明 2011年 3月,我和我的妻子 Linda去了一个美丽而遥远的地方旅行,因此有几天没上网。当我找到机会处理邮件时,却得到一个让人震惊的消息:我的挚友和同事 Philippe突然去世了。由于无法及时赶到巴黎参加葬礼, Linda和我为我们的好朋友写了悼词,在此分享给本书的读者,让我们一起缅怀我们的这位朋友。 悲痛万分,我在一个遥远的地方缅怀我长期以来的好友和同事 Philippe Flajolet。很遗憾不能亲自参加葬礼,但我坚信,将来一定有很多机会来缅怀 Philippe,希望到时我能参与。 Philippe才华横溢、匠心独运、求知若渴、不知疲倦,同时慷慨大方、乐善好施,他的生活方式深深地感染了我。他改变了很多人的生活,包括我自己的。随着我们的诸多研究论文变成综述,进而发展成若干篇章,第一本书,第二本书,最终写书成为我们一生的工作——在跟 Philippe携手同行时,我与全世界很多学生和合作者都感受到了 Philippe的真诚和友好。我们曾在全世界各个地方的咖啡馆、酒吧、午餐室或客厅里一起工作。无论何处, Philippe的工作方式始终不变。我们会先聊聊某个朋友的趣事,然后开始工作。一个眼神的交流,真诚的笑声,抽两根烟,喝两口啤酒,咬两口牛排,吃点薯条,然后听到一声“好……”,我们就这样解决一个又一个问题,证明一条又一条定理。对很多与他合作过的人而言,这些时刻都铭记心中。 这个世界又少了一个聪明高效的数学家。 Philippe的离世意味着很多秘密再也无法揭开。但他给世人留下了很多追随他脚步的继承者,继续追寻他的数学梦想。我们会在会议上为他举杯,我们会以他的研究成果为基础继续前进,我们的论文会加上一句铭文“谨以此纪念 Philippe Flajolet”,我们会将此一代代传承下去。亲爱的朋友,我们非常想念你,我坚信,你的精神会在我们的工作中得到永生。 我们合著的《算法分析导论》一书的第 2版就是这样完成的。谨以此书纪念 Philippe Flajolet,也希望更多的人通过这本书继续追寻 Philippe的数学梦想。 R. S. 2012年 10月于罗得岛州詹姆斯敦

目录

目录 第 1章算法分析 ............... 1 1.1 为什么要做算法分析 ..........................................................1 1.2 算法理论 ..................3 1.3 算法分析概述 ..........8 1.4 平均情况分析 ........10 1.5 实例:快速排序算法的分析 ............................................12 1.6 渐近近似 ................ 18 1.7 分布 ........................ 20 1.8 随机算法 ................ 22 参考文献 ......................... 25 第 2章递归关系 ............. 28 2.1 基本性质 ................ 29 2.2 一阶递归 ................ 33 2.3 一阶非线性递归 ....35 2.4 高阶递归 ................ 38 2.5 求解递归的方法 ....42 2.6 二分分治递归和二进制数 ................................................49 2.7 一般的分治递归 ....57 参考文献 ......................... 62 第 3章母函数 .................. 64 3.1 普通型母函数 ........65 算法分析导论(第 2版) 3.2 指数型母函数 .........69 3.3 利用母函数求解递归 ........................................................72 3.4 母函数的展开 .........79 3.5 利用母函数进行变换 ........................................................82 3.6 关于母函数的函数方程 ....................................................84 3.7 利用 OGF求解三项中值 Quicksort递归.........................87 3.8 利用母函数计数 .....89 3.9 概率母函数 .............93 3.10 双变量母函数 .......96 3.11特殊函数.............101 参考文献........................107 第 4章渐近逼近 ........... 109 4.1 渐近逼近的概念 ...111 4.2 渐近展开式 ...........116 4.3 处理渐近展开式 ...123 4.4 有限和的渐近逼近 ..........................................................129 4.5 欧拉-麦克劳林求和 ........................................................131 4.6 二元渐近...............137 4.7 拉普拉斯方法 .......149 4.8 算法分析中的“正态”举例 ..........................................152 4.9 算法分析中的“泊松”举例 ..........................................155 参考文献........................159 第 5章分析组合 ........... 161 5.1 正式的基础 ...........162 5.2 无标记类的符号方法 ......................................................163 5.3 有标记类的符号方法 ......................................................169 5.4 参数的符号方法 ...177 5.5 母函数系数逼近 ...182 参考文献........................188 第 6章树........................ 189 6.1 二叉树...................190 目录 XV 6.2 森林和树 .............. 192 6.3 树和二叉树的组合等价 ..................................................194 6.4 树的性质 .............. 200 6.5 树算法的例子 ......204 6.6 二叉搜索树 .......... 207 6.7 随机 Catalan树 .... 211 6.8 二叉搜索树中的路径长度 .............................................. 216 6.9 随机树的附加参数 .........................................................219 6.10 高度 .................... 223 6.11树属性在平均情况下的结果总结 ................................229 6.12 拉格朗日反演 ....230 6.13 无序树 ................ 233 6.14 标记树 ................ 242 6.15 其他类型的树 ....245 参考文献 ....................... 253 第 7章排列 ....................256 7.1 排列的基本性质 .. 257 7.2 排列算法 .............. 263 7.3 排列的表示法 ......266 7.4 计数问题 .............. 271 7.5 通过 CGF分析排列的性质............................................275 7.6 逆序和插入排序 .. 285 7.7 从左到右最小值和选择排序 ..........................................291 7.8 环与原地排列 ......297 7.9 极值参数 .............. 300 参考文献 ....................... 304 第 8章字符串与字典树 .........................................................306 8.1 字符串搜索 .......... 307 8.2 位串的组合性质 .. 310 8.3 正则表达式 .......... 320 8.4 有穷状态自动机和 KMP算法 .......................................323 8.5 上下文无关的语法 .........................................................326 算法分析导论(第 2版) 8.6 字典树...................332 8.7 字典树算法 ...........336 8.8 字典树的组合性质 ..........................................................340 8.9 更大的字符表 .......345 参考文献........................347 第 9章单词与映射 ...... 350 9.1 使用分离链接的散列 ......................................................351 9.2 球与瓮的模型和单词的性质 ..........................................353 9.3 生日悖论与优惠券收集者问题 ......................................360 9.4 占据限制与极值参数 ......................................................367 9.5 占据分布...............372 9.6 开放寻址散列法 ...379 9.7 映射.......................386 9.8 整数因子分解与映射 ......................................................396 参考文献........................401

作者简介

编辑推荐

作者寄语

电子资料

www.luweidong.cn

下一个