本书讲解算法的设计与应用,既包含对各类传统算法的分析,也对其在新兴领域的应用进行了介绍。每章之间相互独立,涵盖伪代码描述和数学分析,并配有大量习题。
这是一本非常棒的著作,既有算法的经典内容,也有现代专题。我期待着在我的算法课程试用此教材。我尤其喜欢内容的广度和问题的难度。
—— Robert Tarjan,普林斯顿大学
本书解释极为清晰。我特别喜欢书中三种类型的练习。
—— Ming-Yang Kao,西北大学
Goodrich和Tamassia编写了一本内容十分广泛而且方法具有创新性的著作。贯穿本书的应用和练习为各个领域学习算法的学生提供了极佳的参考。本书涵盖了超出一学期课程可以讲授的内容,这给教师提供了很大的选择余地,同时也给学生提供了很好的自学材料。
—— Michael Mitzenmacher,哈佛大学
我强烈推荐这种进入算法世界的路线图。作者提供了来自现实世界问题的例子,引导读者设计可行解,并且给出继续深入学习的挑战性练习。
—— Jeffry S. Vitter,堪萨斯大学
作者简介
迈克尔 T. 古德里奇(Michael T. Goodrich) 加州大学欧文分校计算机科学系首席教授,在这之前他是约翰霍普金斯大学的教授。他的研究兴趣包括算法的分析、设计和实现,以及数据安全、云计算、绘图和计算几何。他是AAAS、ACM和IEEE会士,曾荣获IEEE计算机协会技术成就奖和ACM卓越服务奖等。
罗伯托·塔马西亚(Roberto Tamassia) 布朗大学计算机科学系Plastech教授,布朗几何计算中心主任。他的研究兴趣包括数据安全、应用密码学、云计算、算法、绘图,以及计算几何的分析、设计和实现。他是AAAS、ACM和IEEE会士,曾荣获IEEE计算机协会技术成就奖。
本书全面地介绍了计算机算法和数据结构的设计和分析。书中各章相对独立,所以教师和读者可以自由选择感兴趣的章节。此外,本书内容广泛,既包含了经典的算法,也包含了新兴的算法,具体如下:
渐近分析数学,包括平摊和随机化。
通用算法设计技术,包括贪心法、分治法和动态规划。
数据结构,包括列表、树、堆、搜索树、B树、哈希表、跳跃表、并查集结构和多维树。
算法框架,包括NP完全性、近似算法和外存算法。
基本算法,包括排序、图算法、计算几何、数值算法、密码、快速傅里叶变换(FFT)和线性规划。
应用驱动方法
计算机科学已经进入一个令人兴奋的时代。计算机已经从早期的计算引擎发展到现在的信息处理器,其应用遍布各个领域。此外,互联网的扩展推动了计算机在社会和商业中的新范式和新模式。例如,计算机可以用来存储和检索大规模数据,并且用于许多其他的应用领域,如运动、视频游戏、生物、制药、社交网络、工程和科学。因此,我们认为算法的讲授既要强调其数学分析,也要突出其实际应用。
为了达到这个目的,每章开篇都有该章主题应用的一个简短讨论。这些应用有的来自于主题的实际应用,有的是设想该章主题在实践中的可能应用。这些讨论的意图是为读者阅读各章时提供一定的背景和实际应用动机。除了这些应用的动机外,我们还给出算法的详细伪代码描述和完整的数学分析。事实上,我们认为数学的严谨性有其实际的意义。
写给教师
本书的结构便于教师自由地选择和讲授内容。各章节之间的依存度已经降至很低,以便教师可以按照自己喜欢的顺序授课。此外,依据内容的深度,每章的讲授时间在1~3节课。
课程样例
本书可作为多个课程的教材。例如,可用于算法核心课程的教材,即经典CS7。另外,本书也可以用于高年级本科生或者研究生的数据结构课程、算法课程,或者两学期连续教授这两个课程的教材。为了突出这些选择,下面为这些可能的课程给出教学大纲样例。
算法核心课程(CS7)大纲样例
第1章算法分析
(跳读、略读或复习第2~4章的基本数据结构)
这些内容以及第5章和第6章是数据结构课程的基本内容,也是本课程的先行课。
第5章优先队列和堆
第6章散列表
第7章并查集结构
第8章归并排序和快速排序
第9章快速排序和选择(如果时间允许)
第10章贪心法
第11章分治法
第12章动态规划
第13章图及遍历
第14章最短路径
第15章最小生成树
第16章网络流和匹配(如果时间允许)
第17章NP完全性
第18章近似算法
如果时间允许,可从第19~26章中选择内容,包括随机算法、计算几何、字符串算法、密码学、快速傅里叶变换(FFT)和线性规划。
高年级本科生或者研究生的数据结构课程大纲样例
第1章算法分析
第2章基本数据结构
第3章二叉搜索树
第4章平衡二叉搜索树
第5章优先队列和堆
第6章散列表
第7章并查集结构
第8章归并排序和快速排序
第13章图及遍历
第14章最短路径
第15章最小生成树
第20章B树和外部存储器
第21章多维搜索
高年级本科生或者研究生的算法课程大纲样例
(跳读、略读或者复习第1~8章)
第9章快速排序和选择
第10章贪心法
第11章分治法
第12章动态规划
第16章网络流和匹配
第17章NP完全性
第18章近似算法
第19章随机算法
第22章计算几何
第23章字符串算法
第24章密码学
第25章快速傅里叶变换
第26章线性规划
这门课程既可以作为一门独立的课程讲授,也可与上面的高级数据结构课程联合讲授。当然,还有其他的选择,在此不再赘述,将这些内容的创意安排留给教师。
三类练习
本书包含了800多个练习,分为三类:
巩固练习,测试对章节内容的理解。
创新练习,测试能否创造性地利用各章的技术方法。
应用练习,测试能否将各章内容应用于实际问题或者设想的问题。
这些练习的分布大致为巩固练习占35%,创新练习占40%,应用练习占25%。
网络增值学习
本书有一个网站:
http://wwwwileycom/college/goodrich/
这个网站包含了章节内容的附加学习资源,特别为学生提供了以下内容:
本书大部分内容的PDF演示讲义。
某些练习的提示。
对于一些学生来说,有些创新练习和应用练习可能具有挑战性,因此他们会对这些提示感兴趣。
我们也为使用本书作为教材的教师提供了一个教学支持网站,包括下列辅助资源:
关于本书教辅资源,只有使用本书作为教材的教师才可以申请,需要的教师可向约翰·威立出版公司北京代表处申请,电话:010-8418 7869,电子邮件:sliang@wileycom。——编辑注
本书一些练习的解。
本书大部分内容的可编辑PowerPoint演示文稿。
预备知识
本书假定读者具有一定的预备知识。特别是,假定读者有基本的数据结构知识,如数组和链表,并且对高级程序设计语言如C、C++、Java或者Python有一定的理解。因此,所有的算法都是用高级的伪代码描述,略去了一些细节(如错误条件测试),但对于具备一定知识的读者来讲,将算法描述转换为程序代码是容易的。
在数学背景方面,本书假定读者熟悉指数、对数、求和、极限和初等概率。尽管如此,本书第1章仍然复习了这些概念,并在附录A中给出了一些其他常用的数学知识,包括初等概率。
关于作者
Goodrich教授和Tamassia教授是研究算法和数据结构的知名学者,在这个研究领域发表了许多论文,并应用于计算机安全、密码学、网络计算、信息可视化和几何计算。他们是美国国家科学基金会、陆军研究处和国防部高级研究计划局资助的许多项目的主要研究人员,在教育技术研究领域也相当活跃。
Michael Goodrich于1987年在普渡大学计算机科学系获得博士学位。他是加州大学欧文分校计算机科学系首席教授。在这之前他是约翰霍普金斯大学的教授。他的研究兴趣包括算法的分析、设计和实现,以及数据安全、云计算、绘图和计算几何。他是富布赖特学者,美国科学促进会(AAAS)、计算机协会(ACM)以及电气和电子工程师协会(IEEE)的会士。他是IEEE计算机协会技术成就奖、ACM卓越服务奖和Pond本科教学优秀奖的获得者,还是《国际计算几何与应用期刊》(IJCGA)和《图算法与应用期刊》(JGAA)咨询委员会委员。
Roberto Tamassia于1988年在美国伊利诺伊大学厄巴纳-香槟分校电子与计算机工程系获得博士学位。他是布朗大学计算机科学系Plastech教授,目前是布朗几何计算中心主任。他的研究兴趣包括:数据安全,应用密码学,云计算,算法的分析、设计和实现,绘图,计算几何。他是美国科学促进会(AAAS)、计算机协会(ACM)以及电气和电子工程师协会(IEEE)的会士。他也是IEEE计算机协会技术成就奖的获得者。Tamassia是《图算法与应用期刊》(JGAA)和绘图学术会议的共同创始人,现在是JGAA的联合主编。
致谢
我们在算法研究和教育项目中有许多合作者,这些合作者帮助我们改进了本书的设计和内容。尤其要感谢Jeff Achter、 Vesselin Arnaudov、 James Baker、 Ryan Baker、 Benjamin Boer、 John Boreiko、 Devin Borland、 Lubomir Bourdev、 Ulrik Brandes、 Stina Bridgeman、 Bryan Cantrill、 YiJen Chiang、 Robert Cohen、 David Ellis、 David Emory、 Jody Fanto、 Ben Finkel、 Peter Frhlich、 Ashim Garg、 David Ginat、 Natasha Gelfand、 Esha Ghosh、 Michael Goldwasser、 Mark Handy、 Michael Horn、 Greg Howard、 Benot Hudson、 Jovanna Ignatowicz、 James Kelley、 Evgenios Kornaropoulos、 Giuseppe Liotta、 David Mount、 Jeremy Mullendore、 Olga Ohrimenko、 Seth Padowitz、 Bernardo Palazzi、 Charalampos Papamanthou、 James Piechota、 Daniel Polivy、 Seth Proctor、 Susannah Raub、 Haru Sakai、 John Schultz、 Andrew Schwerin、 Michael Shapiro、 Michael Shim、 Michael Shin、 Galina Shubina、 Amy Simpson、 Christian Straub、 Ye Sun、 Nikos Triandopoulos、 Luca Vismara、 Danfeng Yao、 Jason Ye和Eric Zamore。
感谢编辑Beth Golub对本项目的热情支持,Wiley的生产团队也给予我们很大帮助。许多人为本书做出了贡献,包括Jayne Ziemba、 Jennifer Welter、 Debbie Martin、 Chris Ruel、 Julie Kennedy、 Wanqian Ye、 Joyce Poh和Janis Soo。
特别感谢Michael Bannister、 Jenny Lam和Joseph Simons对第26章所做的贡献。感谢Siddhartha Sen和Robert Tarjan关于平衡搜索树富有启发的讨论。
真诚地感谢外部评审人员,特别是Jack Snoeyink,他的详细评论和富有建设性的批评对本书非常有益。感谢其他外部评审人员,包括John Donald、 Hui Yang、 Nicholas Tran、 John Black、 My Thai、 Dana Randall、 MingYang Kao、 Qiang Cheng、 Ravi Janarden、 Fikret Ercal、 Jack Snoeyink、 S Muthukrishnan、 Elliot Anshelevich、 Mukkai Krishnamoorthy、 Roxanne Canosa、 Michael Cutler、 Roger Crawfis、 Glencora Borradaile、 Jennifer Welch。
本书手稿主要用Latex完成文字部分,用微软PowerPoint、Visio和Adobe FrameMaker完成图形部分。
最后,真诚地感谢Isabel Cruz、 Karen Goodrich、 Giuseppe Di Battista、Franco Preparata、Ioannis Tollis和我们的父母在本书编写的各个阶段给予的建议、鼓励和支持。感谢他们在我们写书之余为我们提供了多彩的生活。
Michael T. Goodrich
Roberto Tamassia
计算机\算法
这是一本非常棒的著作,既有算法的经典内容,也有现代专题。我期待着在我的算法课程试用此教材。我尤其喜欢内容的广度和问题的难度。
——Robert Tarjan,普林斯顿大学
本书解释极为清晰。我特别喜欢书中三种类型的练习。
——Ming-Yang Kao, 西北大学
Goodrich和Tamassia编写了一本内容十分广泛而且方法具有创新性的著作。贯穿本书的应用和练习为各个领域学习计算的学生提供了极佳的参考。本书涵盖了超出一学期课程可以讲授的内容,这给教师提供了很大的选择余地,同时也给学生提供了很好的自学材料。
——Michael Mitzenmacher, 哈佛大学
我强烈推荐这种进入算法世界的路线图。作者提供了来自现实世界问题的例子,引导读者设计可行解,并且给出继续深入学习的挑战性练习。
——Jeffry S. Vitter, 堪萨斯大学
[美]迈克尔 T. 古德里奇(Michael T. Goodrich) 罗伯托·塔马西亚(Roberto Tamassia) 著:
Michael Goodrich 加州大学欧文分校计算机科学系首席教授,在这之前他是约翰霍普金斯大学的教授。他的研究兴趣包括算法的分析、设计和实现,以及数据安全、云计算、绘图和计算几何。他是AAAS、ACM和IEEE会士,曾荣获IEEE计算机协会技术成就奖和ACM卓越服务奖等。 Roberto Tamassia 布朗大学计算机科学系Plastech教授,布朗几何计算中心主任。他的研究兴趣包括数据安全、应用密码学、云计算、算法、绘图,以及计算几何的分析、设计和实现。他是AAAS、ACM和IEEE会士,曾荣获IEEE计算机学会技术成就奖。
本书全面系统地介绍数据结构、算法设计、算法分析和算法应用。全书内容丰富,讲解由浅入深,既包含经典数据结构和算法、算法设计方法和分析方法以及算法应用,又包含众多高级主题,包括多维搜索、计算几何、密码算法、傅里叶变换和线性规划等。
本书采用应用驱动的方式组织各章内容。书中算法均给出伪代码描述,附带图文并茂的运行过程例子,以及严谨的复杂度分析。每章都附有大量的练习,并分为巩固练习、创新练习和应用练习三种类型,其中应用练习是将刚刚学习的知识应用到实际生活的具体场景中,能极好地加深读者对知识的理解。这种内容和练习的安排,为读者全面深刻地掌握有关内容提供了很好的素材和途径。
全书分六个部分。第一部分系统地讲解基础数据结构与算法,包括栈、队列、二叉搜索树、平衡二叉搜索树、优先队列和堆、哈希表和并查集结构等。通过学习这些章节,读者能由浅入深地掌握常见的数据结构,并为学习后续内容打下坚实的基础。
第二部分讲解排序和选择,包括归并排序和快速排序算法,以及如何进行快速的排序和选择。排序算法是极为重要的一类算法,本部分首先讲解了基于比较的归并排序和快速排序算法,然后讲解了桶排序和基数排序等算法,还讲解了选择和加权中位数算法。
第三部分讲解算法设计常用的技术,包括贪心法、分治法、动态规划、图的遍历。这些均为算法设计中常用的方法,本书用很多具体的算法和实例来讲解如何运用这些方法来设计算法,使得读者能够举一反三,根据实际问题利用这些方法来设计算法。
第四部分讲解图的算法,包括最短路径算法、最小生成树算法,以及网络流和匹配。通过学习这些章节,读者能掌握多种求解最短路径、最小生成树的算法,通过学习网络流和匹配的相关概念和算法,对图有更深入的理解。
第五部分讲解计算困难问题,包括NP完全问题,以及近似算法。本部分主要讨论NP难的问题,为解决这些计算困难问题,讨论了一些近似算法。
第六部分讲解高级主题,包括随机算法、B树和外部存储器、多维搜索、计算几何、字符串算法、密码学、快速傅里叶变换和线性规划。这一部分覆盖面较广,涉及计算机科学的各个领域,读者可以借此了解更多有趣的主题。
本书作者Michael T Goodrich和Roberto Tamassia均为知名大学教授,算法研究领域知名学者。他们不仅对算法理论和应用有深刻见解,而且对算法教学有实际经验。如作者在前言中所讲,本书涵盖内容丰富,既可作为数据结构和算法核心课程的教材,也可作为高年级本科生和研究生的高级算法课程的教材。
本书在翻译过程中得到了许多同行和编辑的大力支持。特别是,任利明对有关棒球的规则和术语做了说明,黄森中对图题的德文做了翻译。在此一并对给予我们帮助的同行和编辑表示感谢!
另外,为了便于读者的阅读,我们对算法伪代码也做了必要的翻译。限于译者水平,译文中难免出现疏漏和错误,欢迎大家批评指正!
译者
2017年4月于广州大学城
出版者的话
译者序
前言
第1章算法分析
11分析算法
111伪代码
112随机存取机模型
113基本操作数目的计算
114递归算法的分析
115渐近表示法
116渐近表示法的重要性
12相关数学知识复习
121求和
122对数和幂
123简单的证明技术
124概率基础
13算法分析案例
131最大子数组问题的第一个解
132一种改进的求最大子数组算法
133线性时间的最大子数组算法
14平摊分析
141平摊技术
142对一个可扩展数组实现的分析
15练习
本章注记
第一部分数据结构
第2章基本数据结构
21栈和队列
211栈
212队列
22列表
221基于索引的列表
222链表
23树
231树的定义
232树的遍历
233二叉树
234表示树的数据结构
24练习
本章注记
第3章二叉搜索树
31搜索和更新
311二叉搜索树的定义
312二叉搜索树中的搜索
313二叉搜索树中的插入
314二叉搜索树中的删除
315二叉搜索树的性能
32范围查询
33基于索引的搜索
34随机构造二叉搜索树
35练习
本章注记
第4章平衡二叉搜索树
41秩和旋转
42AVL树
43红黑树
44弱AVL树
45伸展树
46练习
本章注记
第5章优先队列和堆
51优先队列
52PQ排序、选择排序和插入排序
521选择排序
522插入排序
53堆
531基于数组结构的二叉树
532堆中的插入
533堆中的删除
54堆排序
55扩展优先队列
56练习
本章注记
第6章散列表
61映射
611映射的定义
612查找表
62散列函数
621分量求和
622多项式求值函数
623基于表格的散列
624取模
625随机线性和多项式函数
63碰撞处理与再散列
631拉链法
632开放寻址法
633线性探测
634平方探测
635双重散列
636再散列
64布谷鸟散列
65通用散列
66练习
本章注记
第7章并查集结构
71并查集及其应用
711连通分支
712迷宫建筑和渗透理论
72基于列表的实现
73基于树的实现
74练习
本章注记
第二部分排序和选择
第8章归并排序和快速排序
81归并排序
811分而治之
812归并排序和递推方程
82快速排序
821随机快速排序
822原地快速排序
83基于比较的排序的下界
84练习
本章注记
第9章快速排序和选择
91桶排序和基数排序
911桶排序
912基数排序
92选择
921随机快速选择
922确定性选择
93加权中位数
94练习
本章注记
第三部分基本技术
第10章贪心法
101分份背包问题
102任务调度
103文本压缩和哈夫曼编码
104练习
本章注记
第11章分治法
111递推与主定理
112整数乘法
113矩阵乘法
114极大点集问题
115练习
本章注记
第12章动态规划
121矩阵连乘
122通用技术
123望远镜调度
124博弈策略
1241硬币行
1242概率博弈策略与逆向归纳法
125最长公共子序列问题
1251问题定义
1252应用动态规划解LCS问题
1260-1背包问题
127练习
本章注记
第13章图及遍历
131图的术语和表示方法
1311图的一些术语
1312图的操作
1313表示图的数据结构
132深度优先搜索
133广度优先搜索
134有向图
1341遍历有向图
1342传递闭包
1343有向DFS和垃圾回收
1344有向无环图
135双连通分量
136练习
本章注记
第四部分图算法
第14章最短路径
141单源最短路径
142Dijkstra算法
143BellmanFord 算法
144有向无环图中的最短路径
145所有顶点对之间的最短路径
1451动态规划最短路径算法
1452通过矩阵乘法计算最短路径
146练习
本章注记
第15章最小生成树
151最小生成树的性质
152Kruskal算法
153PrimJarník算法
154Baruvka算法
155练习
本章注记
第16章网络流和匹配
161流与割
1611割
1612剩余容量和增流路径
162最大流算法
1621FordFulkerson算法
1622EdmondsKarp算法
163最大二分图匹配
164棒球赛的淘汰
165最低成本流
166练习
本章注记
第五部分计算困难问题
第17章NP完全性
171P和NP
1711定义复杂类P和NP
1712一些有趣的NP问题
172NP完全性
1721多项式时间归约和NP难度
1722CookLevin 定理
1723如何证明一个问题是NP完全问题
173合取范式可满足问题和3可满足问题
174顶点覆盖、团和集合覆盖
175子集和与背包问题
176哈密顿回路和TSP
177练习
本章注记
第18章近似算法
181几何旅行商问题
1811MetricTSP的一个2近似算法
1812Christofides近似算法
182覆盖问题的近似
1821顶点覆盖的2近似算法
1822集合覆盖的对数近似
183多项式时间近似方法
184回溯和分支定界
1841回溯法
1842分支定界法
185练习
本章注记
第六部分高级主题
第19章随机算法
191随机排列的生成
192稳定婚姻和优惠券收集
1921优惠券收集问题分析
1922稳定婚姻问题
193最小割
1931收缩边
1932计算最小割
1933更快的算法
194寻找素数
195切尔诺夫界
1951马尔可夫不等式
1952示性随机变量之和
1953几何型随机变量之和
196跳跃表
1961搜索
1962更新操作
1963跳跃表的概率分析
197练习
本章注记
第20章B树和外部存储器
201外部存储器
202(2,4)树和B树
2021多叉搜索树
2022(2,4)树
2023(a,b)树和B树
203外部存储器排序
204在线缓存算法
205练习
本章注记
第21章多维搜索
211范围树
212优先搜索树
2121构造优先搜索树
2122在优先搜索树中搜索
2123优先范围树
213四叉树和kd树
2131四叉树
2132kd树
214练习
本章注记
第22章计算几何
221几何对象上的操作
222凸壳
2221礼品包装算法
2222Graham扫描算法
223线段相交
224求最近点对
225练习
本章注记
第23章字符串算法
231字符串操作
232BoyerMoore 算法
233KnuthMorrisPratt算法
234基于散列的词典匹配
235字典树
2351标准字典树
2352压缩字典树
2353后缀字典树
2354搜索引擎
236练习
本章注记
第24章密码学
241最大公约数
2411一些初等数论知识
2412欧几里得GCD算法
242模运算
2421模幂运算
2422模乘法逆
243加密操作
244RSA密码系统
245El Gamal密码系统
246练习
本章注记
第25章快速傅里叶变换
251卷积
252原始单位根
253离散傅里叶变换
254快速傅里叶变换算法
255练习
本章注记
第26章线性规划
261定义问题
262单纯形法
2621松弛型
2622扩展的例子
2623单纯形算法
263对偶
264线性规划的应用
265练习
本章注记
附录A一些有用的数学知识
参考文献