新書推薦:
《
万千心理·儿童心理治疗中的心智化:临床实践指导
》
售價:HK$
87.4
《
自我囚禁的人:完美主义的心理成因与自我松绑(破除你对完美主义的迷思,尝试打破自我评价过低与焦虑的恶性循环)
》
售價:HK$
66.1
《
周易
》
售價:HK$
44.6
《
东南亚的传统与发展
》
售價:HK$
67.2
《
乾隆制造
》
售價:HK$
87.4
《
资治通鉴臣光曰辑存 资治通鉴目录(司马光全集)(全二册)
》
售價:HK$
304.4
《
明代社会变迁时期生活质量研究
》
售價:HK$
316.2
《
律令国家与隋唐文明
》
售價:HK$
76.7
編輯推薦:
算法分析是推动现代计算基础技术发展的重要力量,本书囊括众多算法分析的应用实例。
无数人对从数学角度分析算法产生兴趣,但很难学到相关方法和模型,本书完整介绍该领域主要技术和成果。
作者既精通经典数学又熟谙计算机科学,看重用于算法性能预测的数学基础及从性能角度比较算法。
天才般贯通与揭露数学世界的离散数学|分析组合学|实分析与计算机科学领域的算法|数据结构之奥义。
內容簡介:
《算法分析导论(第2版)》全面介绍了算法的数学分析所涉及的主要技术。涵盖的内容来自经典的数学课题(包括离散数学、初等实分析、组合数学),以及经典的计算机科学课题(包括算法和数据结构)。本书的重点是平均情况或概率性分析,书中也论述了*差情况或复杂性分析所需的基本数学工具。
《算法分析导论(第2版)》第 1 版为行业代表性著作,第 2 版不仅对书中图片和代码进行了更新,还补充了新章节。《算法分析导论(第2版)》共 9 章,第 1 章是导论;第 2~5 章介绍数学方法;第 6~9 章介绍组合结构及其在算法分析中的应用。除每章包含的大量习题以及参考文献外,《算法分析导论(第2版)》特设配套免费学习网站,为读者提供了很多关于算法分析的补充材料,包括课件和相关网站的链接,帮助读者提高学习兴趣,完成更深入的学习。
《算法分析导论(第2版)》适合作为高等院校数学、计算机科学以及相关专业的本科生和研究生的教材,也可供相关技术人员和爱好者学习参考。
關於作者:
Robert Sedgewick于1985年开始在普林斯顿大学任教,是该校计算机系的创始人,现任该校计算机科学系教授。他曾任Adobe Systems公司董事会成员,并在Xerox PARC、IDA和INRIA等机构从事研究。他是算法领域入门著作Algorithms(Fourth Edition)的作者。Sedgewick教授在斯坦福大学师从D. E. Knuth院士,获得博士学位。
Philippe Flajolet曾任法国罗克库尔INRIA资深研究总监,创建并领导了ALGO研究组。他因在算法分析领域的开创性研究而声名鹊起,在分析组合学方面梳理并发展出了强大的新方法,解决了很多长期悬而未决的难题,并在世界各地从事算法分析的教学。Flajolet博士是法国科学院院士。
目錄 :
第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
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
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
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
参考文献
內容試閱 :
序
分析算法可以给人带来两方面的快乐。其一,人们可以尽享优雅计算过程中所蕴含的让人沉醉的数学模式;其二,我们所学到的理论知识可以让自己更好更快地完成工作,这无疑是最实际的好处。
尽管数学模型只是对真实世界的一种理想化近似,但它对所有的科学活动而言都可谓是一剂灵丹妙药。在计算机科学中,数学模型往往可以精确地描述计算机程序所创造的世界,数学模型的重要性也因此大大增加了。我想,这也是为什么我在读研究生时会沉迷于算法分析,以至于这成为我迄今为止的主要工作。
但直到今天,算法分析在很大程度上还是局限在相关专业的研究生和科研人员的圈子里。算法分析的概念既不晦涩也不复杂,但确实比较新,所以相关概念的学习和使用都还需要一些时间才能成熟。
现在,经过40余年的发展,算法分析已经非常成熟,足以成为计算机专业标准课程中的一部分。Sedgewick和Flajolet写的这本众人翘首以盼的教科书也因此备受欢迎。本书的作者不仅仅是这个领域的世界级专家,同时也是算法分析的布道大师。我坚信,这本书会让每一位细细品读的计算机研究人员从中获益。
D. E. Knuth
译者序
公元2014年的冬天,一部讲述计算机科学之父艾伦图灵(Alan Turing)传奇人生的传记电影在美国上映,这部影片就是《模仿游戏》。次年,该片荣获第87届奥斯卡金像奖最佳改编剧本奖,以及包括最佳影片、最佳导演、最佳男主角、最佳女配角在内的7项提名,一时风光无限。
图灵一生最重要的三大贡献包括图灵机、图灵测试,以及破译Enigma密码机,其中的每一项都值得全世界感谢和纪念他。在提出图灵测试的论文中,图灵石破天惊地预言了创造出具有真正智能的机器的可能性,这也是后来人工智能研究的源头。事实上,《模仿游戏》这个名字正是图灵那篇著名论文第1章的标题。后人为了纪念图灵对计算机科学所做出的巨大贡献,也将该领域的最高奖命名为图灵奖。另一方面,破译Enigma密码更是直接帮助盟军在战场上取得先机,甚至拯救了无数人的性命并最终导致第二次世界大战反法西斯阵营的全面胜利。
尽管前面提到的两大贡献已是功若丘山,但笔者这里将从图灵的另外一个贡献图灵机谈起,因为这与本书所要讨论的话题息息相关。不过,为此我们还得把时间再往前推。1900年,德国数学家大卫希尔伯特(David Hilbert)在巴黎举行的国际数学家大会上做了题为《数学问题》的演讲。在这篇重要的演讲中,他提出了著名的希尔伯特之23个问题。尽管此后的数学发展远远超过了希尔伯特的预料,但他所提出的23个问题仍然对20世纪的数学发展起到了重要的推动作用。
希尔伯特的第10个问题是要设计一个算法来测试多项式是否有整数根。他没有使用算法这个术语,而是采用了下面这种表述:通过有限多次运算就可以决定的过程。有意思的是,从希尔伯特对这个问题的陈述中可以看出,他明确地要求设计一个算法。因此,他显然是假设这样的算法存在,人们所要做的只是找到它。现在我们知道,这个任务是无法完成的,即它是算法上不可解的。但对那个时期的数学家来说,以他们对算法的直观认识,得出这样的结论是不可能的。
非形式地说,算法是为实现某个任务而构造的简单指令集。用日常用语来说,算法又被称为过程或者方法。算法在数学中也起着非常重要的作用。古代数学文献中就包含执行各种各样计算任务的算法描述。例如,我国古代数学经典《九章算术》中就记述了包括求最大公约数、最小公倍数、开平方根、开立方根等在内的诸多算法。
虽然算法在数学中已有很长的历史,但在20世纪之前,算法本身一直没有精确的定义。数学家们面对希尔伯特的第10个问题显得束手无策。由于缺乏对算法本身的精确定义,所以要证明某个特定任务不存在算法就更不可能了。要想破解希尔伯特的第10个问题,人们不得不等待算法的精确定义的出现。
直到1936年,曙光似乎出现了。图灵向伦敦的权威数学杂志递交了一篇题为《论数字计算在决断难题中之应用》的论文。该文最终于1937年正式发表,并立即引起了广泛关注。在论文中,图灵描述了一种可以辅助数学研究的机器,也就是后来被称为图灵机的抽象系统。与此同时,另外一位数学家阿隆佐丘奇(Alonzo Church)也独立地提出了另外一套系统,即所谓的Lambda演算。图灵采用他的图灵机来定义算法,而丘奇则采用Lambda演算来定义算法,后来图灵证明这两个定义是等价的。由此,人们在算法的非形式概念和精确定义之间建立了联系,即算法的直觉概念等价于图灵机,这就是所谓的丘奇-图灵论题。
丘奇-图灵论题提出的算法定义是解决希尔伯特第10个问题所需的。而第10个问题的真正解决则要等到1970年,借助于丘奇与图灵的杰出贡献,马提亚塞维齐(Yuri Matiyasevich)在戴维斯(Martin Davis)、普特纳姆(Hilary Putnam)和罗宾逊(Julia Robinson)等人工作的基础上,最终证明检查多项式是否有整数根的算法是不存在的。上述四人的名字也紧紧地同希尔伯特的第10个问题联系在了一起。破解希尔伯特的第10个问题的过程更像一场声势浩大又旷日持久的国际协作和学术接力。每个人的工作都必不可少,而且大家都感觉已经相当接近问题的最终答案。后来的历史见证了马提亚塞维齐敏锐地接过最后一棒并完成终点冲刺的伟大一幕。更有意思的是,彼时正值美苏冷战最为紧张的时期,两个超级大国之间的正常学术交流几乎完全中断。但这或许就是科学无国界的一个重要体现,尽管国家层面上双方剑拔弩张,而科学家在私下仍然以一种惺惺相惜的默契方式彼此神交。特别是在得知苏联数学家完成了最终的证明时,美国同行都表现得相当振奋和由衷的喜悦,这不得不说是学术界的一段佳话。
回顾建立算法形式化定义和破解希尔伯特之第10个问题的那段风起云涌的历史,我们不得不由衷地感叹:算法对于我们的世界是多么重要。可以这样说,自计算机科学诞生之日起,关于算法的研究就一直是一个核心话题。现代计算机科学中充满了各种各样的算法,许多图灵奖得主也正是因提出的各种经典算法而闻名于世。例如,提出单源最短路径算法的迪可斯特朗(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版付梓。塞奇威克坚信弗拉若莱的精神会在后来人的工作中得到永生,进而希冀本书读者能够循着弗拉若莱的脚步,继续追求他的数学梦想。
本书全面系统地介绍了算法分析中需要使用的基本技术,所涉及的内容既来自包括离散数学、组合数学、概率论等在内的经典数学问题,也有来自算法及数据结构等计算机科学问题。像递归、母函数、树形结构、字符串、映射以及散列等算法分析话题均有讨论。可以说本书是一本研究算法分析的权威之作。
作为译者,我们希望自图灵以来的算法研究能够在更宽阔的范围内,被更光大地发扬,尤其希望中国的计算机科研人员能够从本书中找到启迪研究工作的智慧。同时,也希望通过本书向神交已久的两位大师弗拉若莱和塞奇威克送上最崇高的敬意。
最后,本书翻译工作的完成有赖于数位合作者的倾心付出,其中常青翻译了本书的第1至6章、左飞翻译了第8、9章、于佳平翻译了第7章。其他参与本书翻译和校对工作的人员还有李振坡、邵臣、叶剑、赵冰冰、贾啸天、钱文秀、丁星芸、李晓华、黄帅。自知论道须思量,几度无眠一文章。因时间和水平有限,纰漏与不足之处在所难免,译者恳切地期望广大同行及读者朋友不吝批评斧正。
前言
本书的主要目的是介绍算法的数学分析中涉及的主要技术。涵盖的内容都来自经典的数学和计算科学领域,包括来自数学领域的离散数学、实分析基础和组合数学,来自计算机领域的算法和数据结构等。本书的重点是平均情况或是概率性的分析,对最差情况或复杂度分析所需的基本数学工具也有所涉及。
我们假设读者对计算机科学和实分析的基本概念是比较熟悉的。简单来说,读者要能够编写程序和证明定理。除此之外,本书对读者没有其他要求。
本书主要是用作高阶算法分析课程的教科书。书中涵盖了计算机专业学生所需离散数学的基本技术、组合学和重要离散结构的基本属性,因此也可以用在计算机专业的离散数学课程中。通常此类课程所涵盖的内容都比较广泛,很多教师都用自己的方法来选取其中的一部分内容教给学生,因此本书还可以用于给数学和应用数学专业的学生介绍计算机科学中与算法和数据结构有关的基本原理。
关于算法的数学分析的论文非常多,但这个领域的学生和研究人员却很难学习到该领域中广泛使用的方法和模型。本书的目标就是解决这个问题,一方面要让读者知道这个领域所面临的挑战,另一方面要让读者有足够的背景支持来学习为应对这些挑战而正在开发的工具。我们列出了相关的参考文献,因此本书可以作为研究生算法分析入门课程的基础教材,也可以用作想学习该领域中相关文献的数学或计算机领域研究人员的参考资料。
准备工作
如读者有大学一二年级或与之同等的数学基础,学习过组合学和离散数学,以及实分析、数值方法和基本数论方面的课程,将有助于理解本书中的内容(有些内容跟本书是交叉的)。本书将涉及这些领域,但我们在这里只会对必要的内容做介绍。我们会列出参考文献供想进一步学习的读者参考。
读者需要一到两个学期大学水平的编程经验,包括了解基本数据结构。我们不会涉及编程和具体实现的问题,但算法和数据结构是我们的核心。同数学方面的基础知识一样,在本书中我们会简要介绍基本的信息,同时列出标准教材和知识来源供读者参考。
相关书籍
与本书有关的书籍包括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章是组合结构及其在算法分析中的应用,具体如下:
导论
第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。这个网站是免费的,提供了很多关于算法分析的补充材料,包括课件和相关网站的链接,其中有一些关于算法和分析组合学的网站。这些材料对讲授这些内容的教师和自学者都很有帮助。
致谢
我们非常感谢普林斯顿大学的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月于巴黎
读者服务
轻松注册成为博文视点社区用户(www.broadview.com.cn),扫码直达本书页面。
? 提交勘误:您对书中内容的修改意见可在 提交勘误 处提交,若被采纳,将获赠博文视点社区积分(在您购买电子书时,积分可用来抵扣相应金额)。
? 交流互动:在页面下方 读者评论 处留下您的疑问或观点,与我们和其他读者一同学习交流。
页面入口:http:www.broadview.com.cn35368