算法设计与分析 第2版

书名：算法设计与分析 第2版
作者：黄宇
译者：
ISBN：9787111657231
出版社：机械工业出版社
出版时间：2020-7-1
格式：epub/mobi/azw3/pdf
页数：240
豆瓣评分：

书籍简介：

本书是作者在多年从事算法设计与分析课程教学和研究的基础上编写而成，系统地介绍了算法设计与分析的理论、方法和技术。内容围绕两条主线来组织。一条主线是介绍典范性的算法问题，如排序、选择、图遍历等。 另一条主线是介绍典范性的算法设计分析策略，如分治、贪心、动态规划等算法设计策略和对手分析、平摊分析等算法分析策略。本书中两条主线交替进行，每条主线又各自分为基本和进阶两部分。 算法是计算的灵魂（spirit of computing），而算法设计与分析的基础知识是计算机科学的基石。算法设计与分析的内容很丰富，可以从不同视角进行组织与阐述。一种视角是关注经典的算法问题，如排序、选择、查找、图遍历等；另一种视角是关注经典的算法设计策略，如分治、贪心、动态规划等。 根据这一“二维视角”，本书的核心内容分为四块，如图1 所示。从问题的视角看，主要有两类问题。第一类为序相关的问题，包括基于比较的排序、选择与查找；第二类为图相关的问题，包括基本的图遍历问题以及最小生成树、最短路径等图优化问题。从策略的视角看，主要有两类策略。第一类为遍历策略，包括线性表上的遍历和图上的遍历；第二类为优化策略，在序相关的问题上主要体现为分治策略，在图相关的问题上体现为贪心策略与动态规划策略。 图1 二维视角下的核心内容 上述核心内容是算法设计与分析中最基础的知识与最典型的技术。以此为基础，本书进一步讨论更深入的算法设计与分析技术。一类是围绕经典数据结构的算法设计与分析，另一类是进阶的算法分析策略。此外，本书集中讨论抽象的—— 与机器、实现语言无关的—— 算法设计与分析。为此，在主体内容之前，本书首先讲解计算模型的基础知识，它是后续抽象的算法设计与分析的基础。本书的最后介绍计算复杂性的基础知识，试图让读者在了解各类算法问题、学习各种算法设计与分析技术之后，对算法问题的难度有一个总体的认识。本书内容的总体结构如图2所示。 本书的内容是作者在多年授课的过程中逐渐积淀而成的，因而它不是对算法设计与分析知识的一个百科全书式的覆盖，而是对一些重点内容更专注的讨论。本书的内容和组织方式是面向一个学期的授课而设计的。在授课形式方面，我们将课程分为主课与辅课两种形式。主课主要围绕典型的问题、经典的算法展开，而辅课则主要围绕算法策略展开。若干次的主课讲授形成一个阶段，每一个阶段结束后，通过一次辅课从策略的视角回顾最近阶段的一组算法，同时补充新的素材对相应的策略进行进一步的讨论。 图2 本书内容总体结构 在知识讲授之外，实践也是算法设计与分析课程的重要组成部分。算法课程的实践分为两类。一类是传统的习题。本书习题大体按照这样的顺序给出：首先是紧扣书本知识的习题，例如一些简单定理的证明、紧扣算法细节的一些问题等；其次是应用题，它需要读者对一个具有一定现实意义的问题进行建模，并用书中的算法知识来解决问题。另一类是编程实现题。本书的应用题大都可以用于算法编程实现的训练。在实际授课中，我们挑选了部分应用题作为编程实现题，并基于开源的OnlineJudge 平台进行自动评测，取得了良好的效果。 本书的素材主要源自南京大学计算机系本科生“算法设计与分析”课程的授课内容。其中一部分素材来源于共同授课的其他老师，包括前期负责讲授主课并指导辅课教学的陈道蓄老师，以及后期共同分班讲授这门课程的钱柱中、张胜、徐经纬老师。还有一部分素材来源于经典的算法教科书和国外大学的授课教师在其课程网站上发布的课程材料。另外，还要感谢“算法设计与分析”课程早期的两位助教魏恒峰和杨怡玲，他们对大量的课程资料进行了整理与提炼。最后要感谢上过这门课的学生，他们创造性的提问与解题时所犯的错误为本书提供了宝贵的素材。

作者简介：

黄宇，南京大学计算机科学与技术系教授，博士生导师，主要研究方向为分布式算法、分布式系统和软件方法学。曾主持两项国家自然科学基金项目，并作为主要成员参与了国家973计划、国家自然科学基金创新群体项目等多项国家重大科研项目。2014年获得南京大学登峰人才支持计划资助，2011年获教育部技术发明奖。所指导的博士论文荣获2016年中国计算机学会博士学位论文奖。已在IEEE Trans on Computers、IEEE Trans on Parallel and Distributed Systems、IEEE PerCom等重要国际期刊及会议上发表多篇论文。

书友短评：

前言
教学建议
第一部分计算模型
第1 章抽象的算法设计与分析 2
11 RAM 模型的引入 2
111 计算的基本概念 2
112计算模型的基本概念 3
113RAM 模型 3
114计算模型的选择：易用性与精确性 5
12 抽象算法设计 6
121 算法问题规约 6
122 算法正确性证明：数学归纳法 7
13 抽象算法分析 8
131 抽象算法的性能指标 8
132 最坏情况时间复杂度分析 9
133 平均情况时间复杂度分析 10
14 习题 11
第2 章从算法的视角重新审视数学的概念 14
21 数学运算背后的算法操作 14
211 取整 x 和 x 14
212 对数log n 14
213 阶乘n! 15
214 常用级数求和f (i) 16
215 期望E[X] 18
22 函数的渐近增长率 19
23 “分治递归”求解 21
231 替换法 21
232 分治递归与递归树 21
233 Master 定理 22
24 习题 23
第二部分从蛮力到分治
第3 章蛮力算法设计 31
31 蛮力选择与查找 31
32 蛮力排序 32
321选择排序 32
322插入排序 33
33 习题 35
第4 章分治排序 37
41 快速排序 37
411插入排序的不足 37
412快速排序的改进 38
413最坏情况时间复杂度分析 39
414基于递归方程的平均情况时间复杂度分析 40
415基于指标随机变量的平均情况时间复杂度分析 41
42 合并排序 43
43 基于比较的排序的下界 44
431决策树的引入 45
432比较排序的最坏情况时间复杂度的下界 45
433比较排序的平均情况时间复杂度的下界 46
44 习题 48
第5 章线性时间选择 50
51 期望线性时间选择 50
511选择算法设计 50
512选择算法分析 51
52 最坏情况线性时间选择 52
521选择算法设计 52
522选择算法分析 53
53 习题 54
第6 章对数时间查找 57
61 折半查找 57
611经典折半查找 57
612查找峰值 58
613计算√N 59
62 平衡二叉搜索树 59
621二叉搜索树及其平衡性 59
622红黑树的定义 60
623红黑树的平衡性 62
63 习题 62
第7 章分治算法设计要素 65
71 分治算法的关键特征 65
72 计算逆序对的个数 66
721依托于合并排序的逆序对计数 66
722原地的逆序对计数 67
73 整数乘法 68
731简单分治 69
732更精细的分治
· · · · · ·

添加微信公众号:好书天下获取