欢迎光临
免费的PDF电子书下载网站

算法设计与分析(第4版) PDF下载

编辑推荐

本书按照教育部*制定的计算机科学与技术专业规范的教学大纲编写,努力与国际计算机学科的教学要求接轨。强调“算法”与“数据结构”之间密不可分的联系,因而强调融数据类型与定义在该类型上的运算于一体的抽象数据类型,为面向对象的程序设计方法奠定基础,体现计算机科学方法论的理论、抽象和设计三个过程,知识面较宽,且有一定的深度;反复再现计算机科学中用到的大问题的复杂性、效率、抽象的层次、重用、折衷等带有普遍性的概念,让读者在更深的层次上掌握算法与数据结构这一主科目。

 ;

内容简介

为了适应培养我国21世纪计算机各类人才的需要,结合我国高等学校教育工作的现状,立足培养学生能跟上国际计算机科学技术的发展水平,更新教学内容和教学方法,提高教学质量,本书以算法设计策略为知识单元,系统地介绍计算机算法的设计方法与分析技巧,以期为计算机科学与技术学科的学生提供广泛而坚实的计算机算法基础知识。另有配套的《算法设计与分析(第4版)习题解答》,对本书的全部习题做了详尽的解答。 本书内容丰富,观点新颖,理论联系实际。不仅可用作高等学校计算机专业本科生和研究生学习计算机算法设计的教材,而且也适合广大工程技术人员和自学读者学习参考。

作者简介

王晓东,教授,博士生导师。近年来正式出版学术著作11部。近年在国内外学术刊物上发表学术论文60多篇。参加多项科研项目并获奖。其中获国家科技进步二等奖一项,水电部科技进步一等奖一项,福建省科技进步三等奖一项,省水电厅科技进步一等奖一项。

算法设计与分析(第4版) PDF下载

目录

目录CONTENTS
第1章算法引论1
1.1算法与程序1
1.2表达算法的抽象机制1
1.3描述算法3
1.4算法复杂性分析10
小结13
习题14
第2章递归与分治策略16
2.1递归的概念16
2.2分治法的基本思想21
2.3二分搜索技术23
2.4大整数的乘法23
2.5Strassen矩阵乘法24
2.6棋盘覆盖26
2.7合并排序28
2.8快速排序30
2.9线性时间选择33
2.10最接近点对问题35
2.11循环赛日程表43
小结44
习题44
第3章动态规划50
3.1矩阵连乘问题50
3.2动态规划算法的基本要素55
3.3最长公共子序列58
3.4凸多边形最优三角剖分61
3.5多边形游戏64
3.6图像压缩67
3.7电路布线69
3.8流水作业调度72
3.90|1背包问题75
3.10最优二叉搜索树80
小结83
习题83
目录算法设计与分析(第4版)第4章贪心算法85
4.1活动安排问题85
4.2贪心算法的基本要素88
4.2.1贪心选择性质88
4.2.2最优子结构性质89
4.2.3贪心算法与动态规划算法的差异89
4.3最优装载91
4.4哈夫曼编码92
4.4.1前缀码93
4.4.2构造哈夫曼编码93
4.4.3哈夫曼算法的正确性95
4.5单源最短路径96
4.5.1算法基本思想97
4.5.2算法的正确性和计算复杂性98
4.6最小生成树99
4.6.1最小生成树性质99
4.6.2Prim算法100
4.6.3Kruskal算法102
4.7多机调度问题104
4.8贪心算法的理论基础106
4.8.1拟阵106
4.8.2带权拟阵的贪心算法107
4.8.3任务时间表问题109
小结113
习题113
第5章回溯法115
5.1回溯法的算法框架115
5.1.1问题的解空间115
5.1.2回溯法的基本思想116
5.1.3递归回溯117
5.1.4迭代回溯118
5.1.5子集树与排列树119
5.2装载问题120
5.3批处理作业调度126
5.4符号三角形问题128
5.5n后问题130
5.601背包问题133
5.7最大团问题136
5.8图的m着色问题138
5.9旅行售货员问题140
5.10圆排列问题142
5.11电路板排列问题144
5.12连续邮资问题147
5.13回溯法的效率分析149
小结152
习题152
第6章分支限界法153
6.1分支限界法的基本思想153
6.2单源最短路径问题156
6.3装载问题158
6.4布线问题166
6.501背包问题170
6.6最大团问题175
6.7旅行售货员问题178
6.8电路板排列问题181
6.9批处理作业调度184
小结189
习题189
第7章概率算法190
7.1随机数191
7.2数值概率算法193
7.2.1用随机投点法计算π值193
7.2.2计算定积分194
7.2.3解非线性方程组195
7.3舍伍德算法197
7.3.1线性时间选择算法198
7.3.2跳跃表200
7.4拉斯维加斯算法205
7.4.1n后问题206
7.4.2整数因子分解209
7.5蒙特卡罗算法211
7.5.1蒙特卡罗算法的基本思想211
7.5.2主元素问题213
7.5.3素数测试214
小结217
习题217
第8章NP完全性理论与近似算法221
8.1P类与NP类问题221
8.1.1非确定性图灵机222
8.1.2P类与NP类语言222
8.1.3多项式时间验证224
8.2NP完全问题225
8.2.1多项式时间变换225
8.2.2Cook定理226
8.3一些典型的NP完全问题229
8.3.1合取范式的可满足性问题230
8.3.23元合取范式的可满足性问题230
8.3.3团问题231
8.3.4顶点覆盖问题232
8.3.5子集和问题233
8.3.6哈密顿回路问题235
8.3.7旅行售货员问题238
8.4近似算法的性能238
8.5顶点覆盖问题的近似算法240
8.6旅行售货员问题近似算法241
8.6.1具有三角不等式性质的旅行售货员问题242
8.6.2一般的旅行售货员问题243
8.7集合覆盖问题的近似算法244
8.8子集和问题的近似算法246
8.8.1子集和问题的指数时间算法247
8.8.2子集和问题的完全多项式时间近似格式247
小结250
习题250
第9章串与序列的算法253
9.1子串搜索算法253
9.1.1串的基本概念253
9.1.2KMP算法255
9.1.3RabinKarp算法258
9.1.4多子串搜索与AC自动机260
9.2后缀数组与最长公共子串266
9.2.1后缀数组的基本概念266
9.2.2构造后缀数组的倍前缀算法267
9.2.3构造后缀数组的DC3分治法270
9.2.4最长公共前缀数组与最长公共扩展算法274
9.2.5最长公共子串算法276
9.3序列比较算法277
9.3.1编辑距离算法277
9.3.2最长公共单调子序列280
9.3.3有约束最长公共子序列281
小结284
习题285
第10章算法优化策略288
10.1算法设计策略的比较与选择288
10.1.1最大子段和问题的简单算法288
10.1.2最大子段和问题的分治算法289
10.1.3最大子段和问题的动态规划算法291
10.1.4最大子段和问题与动态规划算法的推广291
10.2动态规划加速原理294
10.2.1货物储运问题294
10.2.2算法及其优化295
10.3问题的算法特征298
10.3.1贪心策略298
10.3.2对贪心策略的改进299
10.3.3算法三部曲299
10.3.4算法实现300
10.3.5算法复杂性305
10.4优化数据结构306
10.4.1带权区间最短路问题306
10.4.2算法设计思想306
10.4.3算法实现方案308
10.4.4并查集311
10.4.5可并优先队列314
10.5优化搜索策略318
小结324
习题324
第11章在线算法设计325
11.1在线算法设计的基本概念325
11.2页调度问题327
11.3势函数分析329
11.4k服务问题330
11.4.1竞争比的下界330
11.4.2平衡算法331
11.4.3对称移动算法332
11.5Steiner树问题334
11.6在线任务调度336
11.7负载平衡337
小结338
习题338
词汇索引340
参考文献345

前沿

21世纪大学本科计算机专业系列教材编委会
主任: 李晓明副主任: 蒋宗礼卢先和委员: (按姓氏笔画为序)
马华东马殿富王志英王晓东宁洪
刘辰孙茂松李仁发李文新杨波
吴朝晖何炎祥宋方敏张莉金海
周兴社孟祥旭袁晓洁钱乐秋黄国兴
曾明廖明宏秘书: 张瑞庆

本书责任编委: 宋方敏

前言FOREWORD
以最低的成本、最快的速度、最好的质量开发出适合各种应用需求的软件,必须遵循软件工程的原则,设计出高效率的程序。一个高效的程序不仅需要编程技巧,更需要合理的数据组织和清晰高效的算法。这正是计算机科学领域里数据结构与算法设计所研究的主要内容。一些著名的计算机科学家在有关计算机科学教育的论述中提出,计算机科学是一种创造性思维活动,其教育必须面向设计。计算机算法设计与分析正是一门面向设计,且处于计算机科学与技术学科核心地位的教育课程。通过对计算机算法系统的学习与研究,理解和掌握算法设计的主要方法,培养对算法的计算复杂性进行正确分析的能力,为独立地设计算法和对给定算法进行复杂性分析奠定坚实的理论基础,对从事计算机系统结构、系统软件和应用软件研究与开发的科技工作者是非常重要和必不可少的。为了适应我国21世纪计算机人才培养的需要,结合我国高等学校教育工作的现状,立足培养学生能跟上国际计算机科学技术的发展水平,更新教学内容和教学方法,本书以算法设计策略为知识单元,系统地介绍计算机算法的设计方法与分析技巧,以期为计算机科学与技术学科的学生提供一个广泛而坚实的计算机算法基础知识。
全书共分11章。在第1章中首先介绍算法的基本概念,接着简要阐述算法的计算复杂性和算法的描述,然后围绕设计算法常用的基本设计策略组织第2章至第10章的内容。第2章介绍递归与分治策略,这是设计有效算法最常用的策略,是必须掌握的方法。第3章是动态规划算法,以具体实例详述动态规划算法的设计思想、适用性以及算法的设计要点。第4章介绍贪心算法,这也是一种重要的算法设计策略,它与动态规划算法的设计思想有一定的联系,但其效率更高。按贪心算法设计出的许多算法能导致最优解,其中有许多典型问题和典型算法可供学习和使用。第5章和第6章分别介绍回溯法和分支限界法,这两章所介绍的算法适合处理难解问题,其解题的思想各具特色,值得学习和掌握。第7章介绍概率算法,对许多难解问题提供高效的解决途径,是有很高实用价值的算法设计策略。第8章介绍NP完全性理论和解NP难问题的近似算法。首先介绍计算模型、确定性和非确定性图灵机,然后进一步深入介绍NP完全性理论,最后介绍解NP难问题的近似算法,这是当前计算机算法领域的热门研究课题,具有很高的实用价值。第9章介绍有关串和序列的高效算法。第10章通过实例介绍算法设计中常用的算法优化策略。最后,在第11章介绍算法设计中较新的研究领域——在线算法设计。
在本书各章的论述中,首先介绍一种算法设计策略的基本思想,然后从解决计算机科学与应用中出现的实际问题入手,由简到繁地描述几个经典的精巧算法,同时对每个算法所需要的时间和空间进行分析。这样使读者既能学到一些常用的精巧算法,又能通过对算法设计策略的反复应用,牢固掌握这些算法设计的基本策略,以期收到融会贯通之效。在为各种算法设计策略选择用于展示其设计思想与技巧的具体应用问题时,本书有意重复选择某些经典问题,使读者能深刻地体会到一个问题可以用多种设计策略求解。同时,通过对解同一问题的不同算法的比较,更容易体会到每一个具体算法的设计要点。随着本书内容的逐步展开,读者也将进一步感受到综合应用多种设计策略可以更有效地解决问题。
本书采用面向对象的Java语言作为表述手段,在保持Java优点的同时,尽量使算法的描述简明、清晰。
为了便于读者加深对知识的理解,各章配有难易适当的习题,以适应不同程度读者练习的需要。
在本书的编写过程中,得到教育部高等学校计算机类专业教学指导委员会的关心和支持。福州大学“211工程”计算机与信息工程重点学科实验室和福建工程学院为本书的写作提供了优良的设备与工作环境。清华大学出版社负责本书编辑出版工作的全体人员为本书的出版付出了大量辛勤劳动,他们认真细致、一丝不苟的工作精神保证了本书的出版质量。南京大学宋方敏教授和福州大学傅清祥教授在百忙中认真审阅了全书,提出了许多宝贵的改进意见。在此,谨向每一位曾经关心和支持本书编写工作的各方面人士表示衷心的谢意!
由于作者的知识和写作水平有限,书稿虽几经修改,仍难免存在缺点。热忱欢迎同行专家和读者惠予批评指正,使本书在使用过程中不断改进,日臻完善。作者2018年6月前言算法设计与分析(第4版)

算法设计与分析(第4版) pdf下载声明

本pdf资料下载仅供个人学习和研究使用,不能用于商业用途,请在下载后24小时内删除。如果喜欢,请购买正版

pdf下载地址

版权归出版社和作者所有,下载链接已删除。如果喜欢,请购买正版!

链接地址:算法设计与分析(第4版)