图书详情

配套资源图书内容样章/电子教材图书评价

配套资源
本书资源
会员上传本书资源
为本书上传资源

图书内容

内容简介

本书为普通高等教育“十一五”国家级规划教材。本书内容分为3部分：算法和算法分析、算法设计策略及求解困难问题。第1部分介绍算法问题求解基础和算法分析基础，以及两种新的数据结构：伸展树与跳表；第2部分讨论常用的算法设计策略，包括基本搜索和遍历方法、分治法、贪心法、动态规划法、回溯法和分枝限界法；第3部分介绍NP完全问题、随机算法、近似算法、遗传算法和密码算法，并对现代密码学和数论做了简要论述。本书结构清晰、内容翔实、逻辑严谨、讲解深入浅出。书中算法有完整的C++程序，这些程序构思精巧，有详细注释，并且已在C++环境下编译通过能正确运行。它们既是讲解算法设计的示例，帮助理解和掌握复杂抽象的算法设计，也是很好的C++程序设计示例。书中包含大量实例，并附有丰富的习题，便于教学和自学。本书可作为高等学校计算机及其他相关专业本科生和研究生“算法设计与分析”课程的教材或参考书，是“算法与数据结构”或“数据结构”课程有益的教学参考书，也可供计算机相关从业者及其他希望了解和学习算法知识的人员参考。

图书详情

ISBN：9787121483325

开本：16(185*260)

页数：312

字数：524

本书目录

第1部分  算法和算法分析
第1章  算法问题求解基础	1
1.1  算法概述	1
1.1.1  什么是算法	1
1.1.2  为什么学习算法	3
1.2  问题求解方法	3
1.2.1  问题和问题求解	4
1.2.2  问题求解过程	4
1.2.3  软件生命周期	5
1.3  算法设计与分析	5
1.3.1  算法问题求解过程	5
1.3.2  如何设计算法	6
1.3.3  如何表示算法	6
1.3.4  如何确认算法	6
1.3.5  如何分析算法	7
1.4  递归和归纳	7
1.4.1  递归	7
1.4.2  递归算法示例	9
1.4.3  归纳证明	11
习题1	13
第2章  算法分析基础	14
2.1  算法复杂度	14
2.1.1  什么是好的算法	14
2.1.2  影响程序执行时间的因素	15
2.1.3  算法的时间复杂度	16
2.1.4  使用程序步分析算法	17
2.1.5  算法的空间复杂度	18
2.2  渐近表示法	19
2.2.1  大O记号	19
2.2.2  Ω记号	20
2.2.3  Θ记号	21
2.2.4  小o记号	21
2.2.5  算法按时间复杂度分类	21
2.3  递推关系	22
2.3.1  递推方程	22
2.3.2  替换方法	23
2.3.3  迭代方法	23
2.3.4  递归树	23
2.3.5  主方法	25
2.4  分摊分析	25
2.4.1  聚集分析	26
2.4.2  会计方法	26
2.4.3  势能方法	27
习题2	28
第3章  伸展树与跳表	31
3.1  伸展树	31
3.1.1  二叉搜索树	31
3.1.2  自调节树和伸展树	31
3.1.3  伸展操作	32
3.1.4  伸展树类	34
3.1.5  旋转的实现	34
3.1.6  插入运算的实现	35
3.1.7  分摊分析	37
3.2  跳表	39
3.2.1  什么是跳表	39
3.2.2  跳表类	40
3.2.3  层次分配	42
3.2.4  插入运算的实现	43
3.2.5  性能分析	44
习题3	45
 
第2部分  算法设计策略
 
第4章  基本搜索和遍历方法	46
4.1  基本概念	46
4.2  图的搜索和遍历	47
4.2.1  搜索方法	47
4.2.2  邻接表类	48
4.2.3  广度优先搜索	49
4.2.4  深度优先搜索	51
4.3  双连通分量	53
4.3.1  基本概念	53
4.3.2  发现关节点	54
4.3.3  构造双连通图	58
4.4  与或图	58
4.4.1  问题分解	58
4.4.2  判断与或树是否可解	60
4.4.3  构建解树	61
4.5  区间最值查询（RMQ）	62
4.5.1  区间信息维护与查询	62
4.5.2  ST算法求解RMQ问题	63
4.6  最近公共祖先（LCA）	65
4.6.1  概述	65
4.6.2  倍增法求解LCA问题	66
4.6.3  在线RMQ法求解LCA问题	68
4.6.4  Tarjan算法求解LCA问题	70
习题4	73
第5章  分治法	75
5.1  一般方法	75
5.1.1  分治法的基本思想	75
5.1.2  算法分析	76
5.1.3  数据结构	77
5.2  求最大、最小元	78
5.2.1  分治法求解	78
5.2.2  时间分析	79
5.3  二分搜索	80
5.3.1  分治法求解	80
5.3.2  对半搜索	81
5.3.3  二叉判定树	82
5.3.4  搜索算法的时间下界	84
5.4  排序问题	85
5.4.1  合并排序	85
5.4.2  快速排序	87
5.4.3  排序算法的时间下界	91
5.5  选择问题	92
5.5.1  分治法求解	92
5.5.2  随机选择主元	93
5.5.3  线性时间选择算法	94
5.5.4  时间分析	96
5.5.5  允许重复元素的选择算法	97
5.6  斯特拉森矩阵乘法	97
5.6.1  分治法求解	97
5.6.2  斯特拉森矩阵乘法简介	98
习题5	99
第6章  贪心法	102
6.1  一般方法	102
6.2  背包问题	103
6.2.1  问题描述	103
6.2.2  贪心法求解	104
6.2.3  算法正确性	105
6.3  带时限的作业排序问题	106
6.3.1  问题描述	106
6.3.2  贪心法求解	107
6.3.3  算法正确性	108
6.3.4  可行性判定	108
6.3.5  作业排序贪心算法	109
6.3.6  改进算法	110
6.4  最佳合并模式	112
6.4.1  问题描述	113
6.4.2  贪心法求解	113
6.4.3  算法正确性	115
6.5  最小代价生成树	116
6.5.1  问题描述	116
6.5.2  贪心法求解	116
6.5.3  普里姆算法	117
6.5.4  克鲁斯卡尔算法	119
6.5.5  算法正确性	121
6.6  单源最短路径	122
6.6.1  问题描述	122
6.6.2  贪心法求解	122
6.6.3  迪杰斯特拉算法	123
6.6.4  算法正确性	125
6.7  磁带最优存储	127
6.7.1  单带最优存储	127
6.7.2  多带最优存储	128
6.8  贪心法的基本要素	129
6.8.1  最优量度标准	129
6.8.2  最优子结构	129
习题6	130
第7章  动态规划法	133
7.1  一般方法和基本要素	133
7.1.1  一般方法	133
7.1.2  基本要素	134
7.1.3  多段图问题	134
7.1.4  资源分配问题	137
7.1.5  关键路径问题	138
7.2  每对结点间的最短路径	140
7.2.1  问题描述	140
7.2.2  动态规划法求解	140
7.2.3  弗洛伊德算法	141
7.2.4  算法正确性	143
7.3  矩阵连乘	143
7.3.1  问题描述	143
7.3.2  动态规划法求解	144
7.3.3  矩阵连乘算法	145
7.3.4  备忘录方法	147
7.4  最长公共子序列	147
7.4.1  问题描述	147
7.4.2  动态规划法求解	148
7.4.3  最长公共子序列算法	149
7.4.4  改进算法	151
7.5  最优二叉搜索树	151
7.5.1  问题描述	151
7.5.2  动态规划法求解	151
7.5.3  最优二叉搜索树算法	153
7.6  0/1背包问题	155
7.6.1  问题描述	155
7.6.2  动态规划法求解	155
7.6.3  0/1背包问题算法框架	157
7.6.4  0/1背包问题算法	160
7.6.5  性能分析	162
7.6.6  使用启发式方法	163
7.7  流水线作业调度	164
7.7.1  问题描述	164
7.7.2  动态规划法求解	165
7.7.3  Johnson算法	167
习题7	168
第8章  回溯法	170
8.1  一般方法	170
8.1.1  基本概念	170
8.1.2  剪枝函数和回溯法	171
8.1.3  回溯法的效率分析	173
8.2  n-皇后问题	173
8.2.1  问题描述	173
8.2.2  回溯法求解	174
8.2.3  n-皇后算法	175
8.2.4  时间分析	176
8.3  子集和数问题	177
8.3.1  问题描述	177
8.3.2  回溯法求解	177
8.3.3  子集和数算法	178
8.4  图着色问题	180
8.4.1  问题描述	180
8.4.2  回溯法求解	180
8.4.3  图着色算法	181
8.4.4  时间分析	182
8.5  哈密顿环问题	182
8.5.1  问题描述	182
8.5.2  哈密顿环算法	183
8.6  0/1背包问题	184
8.6.1  问题描述	184
8.6.2  回溯法求解	184
8.6.3  限界函数	185
8.6.4  0/1背包问题算法	186
8.7  批处理作业调度	188
8.7.1  问题描述	188
8.7.2  回溯法求解	188
8.7.3  批处理作业调度算法	188
习题8	190
第9章  分枝限界法	192
9.1  一般方法	192
9.1.1  分枝限界法概述	192
9.1.2  LC分枝限界法	194
9.1.3  15谜问题	195
9.2  求最优解的分枝限界法	197
9.2.1  上下界函数	197
9.2.2  FIFO分枝限界法	198
9.2.3  LC分枝限界法	199
9.3  带时限的作业排序	200
9.3.1  问题描述	200
9.3.2  分枝限界法求解	200
9.3.3  带时限的作业排序算法	201
9.4  0/1背包问题	203
9.4.1  问题描述	203
9.4.2  分枝限界法求解	203
9.4.3  0/1背包问题算法	204
9.5  旅行商问题	207
9.5.1  问题描述	207
9.5.2  分枝限界法求解	207
9.6  批处理作业调度	211
9.6.1  问题描述	211
9.6.2  分枝限界法求解	211
9.6.3  批处理作业调度算法	212
习题9	215
 
第3部分  求解困难问题
 
第10章  NP完全问题	217
10.1  基本概念	217
10.1.1  不确定算法和不确定机	218
10.1.2  可满足性问题	220
10.1.3  P类问题和NP类问题	221
10.1.4  NP难度问题和NP完全问题	221
10.2  Cook定理和证明	222
10.2.1  Cook定理	222
10.2.2  简化的不确定机模型	222
10.2.3  证明Cook定理	223
10.3  一些典型的NP完全问题	227
10.3.1  最大集团	227
10.3.2  顶点覆盖	228
10.3.3  三元CNF可满足性	229
10.3.4  图的着色数	230
10.3.5  有向哈密顿环	231
10.3.6  恰切覆盖	233
10.3.7  子集和数	234
10.3.8  分划	235
习题10	236
第11章  随机算法	238
11.1  基本概念	238
11.1.1  随机算法概述	238
11.1.2  随机数发生器	238
11.1.3  随机算法分类	239
11.2  拉斯维加斯算法	240
11.2.1  标记重复元素算法	240
11.2.2  性能分析	241
11.2.3  n-皇后问题	242
11.2.4  拉斯维加斯算法和回溯法的结合
       算法	244
11.3  蒙特卡罗算法	245
11.3.1  多数元素问题	246
11.3.2  素数测试问题	247
11.3.3  伪素数测试问题	248
11.3.4  米勒-拉宾算法	249
11.4  舍伍德算法	250
11.4.1  快速排序舍伍德算法	250
11.4.2  性能分析	251
11.4.3  舍伍德算法的其他应用	251
习题11	252
第12章  近似算法	253
12.1  近似算法的性能	253
12.1.1  基本概念	253
12.1.2  绝对性能保证	253
12.1.3  相对性能保证	254
12.1.4  近似方案	255
12.2  绝对近似算法的应用	255
12.2.1  最多程序存储问题	255
12.2.2  NP难度问题	256
12.3  ?-近似算法的应用	257
12.3.1  顶点覆盖问题	257
12.3.2  旅行商问题	258
12.3.3  NP难度?-近似旅行商问题	259
12.3.4  具有三角不等式性质的旅行商
       问题	260
12.3.5  多机调度问题	261
12.4  ?(n)-近似算法	263
12.4.1  集合覆盖问题	263
12.4.2  集合覆盖问题近似算法	264
12.4.3  ln(n)-近似算法	264
12.5  多项式时间近似方案	266
12.5.1  多机调度近似方案	266
12.5.2  时间分析	267
12.6  子集和数问题的完全多项式时间近似
       方案	267
12.6.1  子集和数问题的指数时间算法	267
12.6.2  完全多项式时间近似方案	268
习题12	270
第13章  遗传算法	272
13.1  进化计算	272
13.2  遗传算法的生物学基础	273
13.3  遗传算法的基本思想	274
13.4  基本遗传算法	275
13.4.1  基本遗传算法的构成要素	275
13.4.2  基本遗传算法的流程图	278
13.5  遗传算法的特点和应用	278
13.5.1  遗传算法的特点	278
13.5.2  遗传算法的应用	278
13.6  基本遗传算法的实现方法	279
13.6.1  数据结构	279
13.6.2  主程序	279
13.6.3  选择运算	280
13.6.4  交叉运算	282
13.6.5  变异运算	283
13.7  旅行商问题	283
13.7.1  排列编码	284
13.7.2  目标函数和适应度函数	284
13.7.3  锦标赛选择法	284
13.7.4  顺序交叉	285
13.7.5  交换变异	286
13.7.6  参数选择	287
13.7.7  实例运行结果	287
习题13	288
第14章  密码算法	289
14.1  信息安全和密码学	289
14.1.1  信息安全	289
14.1.2  什么是密码	289
14.1.3  密码体制	290
14.2  数论初步	291
14.3  背包问题密码算法	292
14.3.1  背包问题	292
14.3.2  超递增背包问题	293
14.3.3  由私人密钥产生公开密钥	294
14.3.4  加密方法	294
14.3.5  解密方法	294
14.3.6  背包问题安全性	295
14.4  RSA算法	295
14.4.1  RSA算法概述	295
14.4.2  RSA算法安全性	296
14.5  散列函数和消息认证	297
14.5.1  散列函数	297
14.5.2  散列函数的结构	297
14.5.3  消息认证	298
14.6  数字签名	298
14.6.1  RSA算法实现直接数字签名	298
14.6.2  需仲裁的数字签名	299
习题14	299
参考文献	300

展开

前言

前    言
本书为普通高等教育“十一五”国家级规划教材。
算法设计与分析不仅是计算学科学生的必备知识，也是计算机工作者必不可少的基础知识。掌握扎实的算法设计与分析理论和方法有助于学生进一步学习计算机技术，适应更广泛的职业挑战。
ACM/IEEE计算课程体系规范2020（Computing Curricula 2020，CC2020）在CC2005等版本的基础上做了重要更新，提出了“胜任力”（competency）模型，融合了知识（knowledge）、技能（skills）和品行（dispositions）三个方面的综合能力培养，认为知识是对事实的理解，技能表达了知识的应用。CC2020列出了34个知识元素，并划分为6类。数据结构、算法和复杂性（data structures、algorithm and complexity）被列为软件基础知识类的一个知识元素。
算法领域涉及的内容广泛，包括很多基本和经典的算法，例如，排序算法、搜索算法、图算法、组合问题算法、字符串算法和大量的数值算法，还包括算法问题求解、算法分析技术和常用的算法设计策略，以及可计算性理论和问题复杂性的研究，如计算模型、NP完全问题和问题复杂度下界理论。近年来，计算机应用领域不断拓展和深化，促使计算学科以前所未有的速度突飞猛进。无论处于世界何处，都能感知到计算技术对各行各业，乃至人类社会生活各方面带来的巨大改变。所有这些，都伴随着算法研究的演进和创新。算法研究在随机算法、近似算法、密码算法、分布式算法和并行算法，尤其在人工智能领域（遗传算法、机器学习、神经网络和深度学习等）都有诸多亮丽成果。
《算法设计与分析》一书自2006年出版以来，深受读者欢迎，在此表示衷心感谢。
随着遗传算法的深入研究以及与其他学科的相互融合，遗传算法作为进化计算的主要分支，在智能计算上占有重要地位，其应用范围涉及组合最优化、图像处理、模式识别、智能控制、神经网络、自动程序设计、机器学习、数据挖掘、人工生命和网络通信等许多领域。遗传算法应该成为计算学科各专业学生和计算机工作者的必备知识，而不是只在人工智能课程中才学习此算法，将其引入传统的“算法设计与分析”课程并与其他算法一起讨论，很有必要。为此，本书第3版增加了第13章“遗传算法”，帮助学生和相关人员了解遗传算法，并进一步学习进化计算。
本书第4版新增了4.5和4.6节，讨论区间最值查询（RMQ）和最近公共祖先（LCA）问题。这是两个很有意思的问题，它们是许多应用中可能遇到的基础问题，经常出现在各类信息学竞赛的试题中。讨论内容包括：求解RMQ和LCA问题的在线和离线算法；运用倍增和ST（Sparse Table）技术提高算法的时间性能；在LCA问题的Tarjan离线算法中，设计者巧妙地使用了并查集，获取了极佳的时空复杂度；RMQ与LCA问题可以相互归约。尽管将一个问题采用不同设计方法和技术的多种算法进行集中讨论的做法与本书按算法设计策略划分章节的方式有所偏离，但因为这些算法的主体是搜索和遍历，尚属合理。其好处是学生可从对问题实例多种解法的讨论中看到，为了设计一个高效算法，设计者需要灵活运用数据结构、算法和复杂度知识。
此外，本书第4版对随机算法的内容进行了增补修订，意在加深学生对随机算法及其复杂度分析的学习和理解。 
算法知识理论性较强，涉及的范围又很广，给学习和理解造成了困难。为了将本书写成结构清晰、内容翔实、逻辑严谨、讲解深入浅出的“算法设计与分析”教材，作者做了以下努力。
首先，本书分3部分组织内容，力求做到结构清晰、内容取舍恰当。
其次，书中算法有完整的C++程序，程序结构清楚、构思精巧，并且有详细注释。所有程序都已在C++环境下编译通过并能正确运行，它们既是学习算法设计的示例，也是很好的C++程序设计示例。
最后，本书通过大量实例介绍算法，并有丰富的习题，便于教学和自学。
这样做的目的是在保持算法科学性的同时，加强其技术性和实用性，降低算法学习的难度，使复杂抽象的算法设计更容易为学习者理解和掌握。这也体现了计算学科的科学性与工程性、理论性与实践性并重的学科特点。
全书包括3部分内容：算法和算法分析、算法设计策略及求解困难问题。
第1部分介绍算法问题求解基础和算法分析基础，以及两种新的数据结构：伸展树与跳表，包括伸展树性能分析的分摊方法和跳表算法性能分析的概率方法。
第2部分讨论常用的算法设计策略，包括基本搜索和遍历方法、分治法、贪心法、动态规划法、回溯法和分枝限界法。对每种算法设计策略，通常先介绍一般方法，然后使用该策略解决若干经典的算法问题。
第3部分介绍NP完全问题、随机算法、近似算法、遗传算法和密码算法，并对现代密码学和数论做了简要论述。
作者在南京邮电大学讲授“算法设计与分析”和“数据结构”课程多年，本书是在作者编写的多本算法与数据结构教材的基础上，参考了近年来国内外多种算法设计与分析的优秀教材编写而成的。本书的编写得到了电子工业出版社的大力支持，并得到了南京邮电大学和计算机学院领导的推荐和关心，深表感谢。
书中若有不妥之处，敬请读者批评指正。

作  者  
                                        
附录A  专有名词中英文对照表                   附录B  C++程序设计概要

展开

作者简介

陈慧南，教授，南京邮电大学计算机学院，主持了多项信息产业部基金项目的研究工作，并负责了多项企业办公自动化和信息管理网络系统的研制开发。出版多本教材。曾获江苏省普通高校教学成果三等奖，其主持的《数据结构》课程获江苏省高校一类优秀课程。

样章试读

本书暂无样章试读！
图书评价我要评论

本书资源

会员上传本书资源

内容简介

图书详情

本书目录

前 言

作者简介

前言