作者：王晓东
页数：329
出版社：清华大学出版社
出版日期：2016
ISBN：9787302348641
电子书格式：pdf/epub/txt
内容简介
本教材以ACM和IEEE CS
Computing Curricula最课程体系以及教育部计算机科学与技术教学指导委员会发布的“高等学校计算机科学与技术本科专业规范”中制定的关于算法设计与分析的知识结构和体系为依据，按计算机算法设计策略为知识单元，采用当前十分流行且适合于Internet环境的面向对象程序设计语言Java组织编写。为计算机学科的学生提供一个广泛坚实的计算机算法基础知识。
l 教材中涵盖的算法设计策略经典而且全面。包括用于问题精确求解的递归与分治策略、动态规划算法、贪心策略、回溯算法和分支限界算法；用于求解NP难题的近似算法、最化算法以及近年来算法设计与分析领域的热门研究课题在线算法的设计与分析。
l 以问题驱动的方式组织教材内容。在各章的论述中，都先介绍一种算法设计策略的基本思想，然后从解决计算机科学和应用中出现的实际问题入手，由简到繁地描述经典的精巧算法；同时对每个算法所需的时间和空间进行分析。使学生既能学到常用的精巧算法，又能通过对算法设计策略的反复应用，牢固掌握这些算法设计的基本策略，以期收到融会贯通之效。
l 广度与深度兼顾，理论与实践并重。本书强调提高学生的综合素质为最终目标，用广度与深度兼顾的教学策略，培养学生的专业兴趣，树立正确的专业思想，又能在具体知识点的学习中深入探究，逐步培养起科学严密的计算思维和创新能力。本课程对学生的抽象思维能力和逻辑推理能力要求较高。如教材中关于算法计算复杂性的内容以及NP完全理论具有较强的理论性，而对于具体算法设计策略的实现和应用又有很强的实践性。
l 教材的习题设计独具特色。各章配有难易适当的习题，分为理论分析型和应用实验型两种。理论分析型的习题侧重于算法理论的掌握与扩展，应用实验型的习题则侧重算法的实现与具体应用。两种类型的习题都有一定的难度和深度，对于深刻理解和熟练掌握算法设计策略与技巧有很大帮助。
与本教材配套的习题解答为授课教师提供全部习题的详细解答和应用实验型习题的全部测试数据。
本书是学习算法设计与分析的经典教材，配套开发了丰富的在线教学资源，可以在清华大学出版社的在线教学平台上进行练习与测试，实现教学互动、智能学习。另外配有辅助教材《算法设计与分析习题解答与学习指导（第3版）》（ISBN: 9787302348634）。本书的PPT电子教案、配套的源代码等资源，可到清华大学出版社官网下载。
本教材可适用于国内大多数普通高校计算机及相关专业算法设计与分析课程教学的需要。从2004年8月本书第1版出版到2007年底，共重印了10余次，第2版已经重印了10余次，已经被国内一百余所大学的本科生和研究生选作教材。
作者简介
王晓东，教授，博士生导师，福建工程学院副校长，曾任福州大学数学与计算机学院院长，福建省计算机学会理事长。先后主持完成了与算法设计与分析有关的国家自然科学基金项目、国家优秀留学回国人员基金项目、省杰出人才基金项目和省自然科学基金项目等7个研究课题；在国内外重要学术刊物上发表有创见性的学术论文50余篇；近年来正式出版学术著作11部；获得国家科技进步二等奖1项，水电部科技进步一等奖一项，福建省科技进步三等奖1项，福建省省水电厅科技进步一等奖1项。在算法复杂性研究方面取得了一系列有影响的理论成果和应用成果，受到同行专家的好评。
本书特色
为了适应培养我国21世纪计算机各类人才的需要，结合我国高等学校教育工作的现状，立足培养学生能跟上国际计算机科学技术的发展水平，更新教学内容和教学方法，提高教学质量，本书以算法设计策略为知识单元，系统地介绍计算机算法的设计方法与分析技巧，以期为计算机科学与技术学科的学生提供广泛而坚实的计算机算法基础知识。另有配套的《算法设计与分析习题解答（第3版）》，对本书的全部习题做了详尽的解答。本书内容丰富，观点新颖，理论联系实际。不仅可用作高等学校计算机专业本科生和研究生学习计算机算法设计的教材，而且也适合广大工程技术人员和自学读者学习参考。
目录
第1章算法引论11.1算法与程序1
1.2表达算法的抽象机制1
1.3描述算法3
1.4算法复杂性分析11
小结14
习题14
第2章递归与分治策略16
2.1递归的概念16
2.2分治法的基本思想22
2.3二分搜索技术23
2.4大整数的乘法24
2.5Strassen矩阵乘法25
2.6棋盘覆盖26
2.7合并排序28
2.8快速排序30
2.9线性时间选择33
2.10最接近点对问题36
2.11循环赛日程表43
小结44
习题45
第3章动态规划50
3.1矩阵连乘问题50
3.2动态规划算法的基本要素55
3.3最长公共子序列58
3.4凸多边形最优三角剖分61
3.5多边形游戏64目录算法设计与分析(第3版)3.6图像压缩67
3.7电路布线70
3.8流水作业调度72
3.90|1背包问题75
3.10最优二叉搜索树80
小结83
习题84
第4章贪心算法85
4.1活动安排问题85
4.2贪心算法的基本要素88
4.2.1贪心选择性质88
4.2.2最优子结构性质88
4.2.3贪心算法与动态规划算法的差异89
4.3最优装载91
4.4哈夫曼编码92
4.4.1前缀码93
4.4.2构造哈夫曼编码93
4.4.3哈夫曼算法的正确性95
4.5单源最短路径97
4.5.1算法基本思想97
4.5.2算法的正确性和计算复杂性99
4.6最小生成树100
4.6.1最小生成树性质100
4.6.2Prim算法100
4.6.3Kruskal算法102
4.7多机调度问题104
4.8贪心算法的理论基础106
4.8.1拟阵107
4.8.2带权拟阵的贪心算法108
4.8.3任务时间表问题110
小结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.601背包问题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布线问题167
6.501背包问题171
6.6最大团问题175
6.7旅行售货员问题178
6.8电路板排列问题182
6.9批处理作业调度184
小结189
习题189
第7章概率算法190
7.1随机数191
7.2数值概率算法193
7.2.1用随机投点法计算π值193
7.2.2计算定积分194
7.2.3解非线性方程组196
7.3舍伍德算法198
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.1计算模型221
8.1.1随机存取机RAM222
8.1.2随机存取存储程序机RASP228
8.1.3RAM模型的变形与简化231
8.1.4图灵机235
8.1.5图灵机模型与RAM模型的关系236
8.1.6问题变换与计算复杂性归约238
8.2P类与NP类问题239
8.2.1非确定性图灵机239
8.2.2P类与NP类语言240
8.2.3多项式时间验证241
8.3NP完全问题243
8.3.1多项式时间变换243
8.3.2Cook定理244
8.4一些典型的NP完全问题247
8.4.1合取范式的可满足性问题247
8.4.23元合取范式的可满足性问题248
8.4.3团问题249
8.4.4顶点覆盖问题250
8.4.5子集和问题251
8.4.6哈密顿回路问题252
8.4.7旅行售货员问题256
小结256
习题257
第9章近似算法259
9.1近似算法的性能259
9.2顶点覆盖问题的近似算法260
9.3旅行售货员问题近似算法262
9.3.1具有三角不等式性质的旅行售货员问题262
9.3.2一般的旅行售货员问题263
9.4集合覆盖问题的近似算法264
9.5子集和问题的近似算法267
9.5.1子集和问题的指数时间算法267
9.5.2子集和问题的完全多项式时间近似格式268
小结270
习题270
第10章算法优化策略273
10.1算法设计策略的比较与选择273
10.1.1最大子段和问题的简单算法273
10.1.2最大子段和问题的分治算法274
10.1.3最大子段和问题的动态规划算法275
10.1.4最大子段和问题与动态规划算法的推广276
10.2动态规划加速原理279
10.2.1货物储运问题279
10.2.2算法及其优化279
10.3问题的算法特征283
10.3.1贪心策略283
10.3.2对贪心策略的改进283
10.3.3算法三部曲285
10.3.4算法实现285
10.3.5算法复杂性290
10.4优化数据结构291
10.4.1带权区间最短路问题291
10.4.2算法设计思想291
10.4.3算法实现方案293
10.4.4并查集296
10.4.5可并优先队列298
10.5优化搜索策略302
小结308
习题309
第11章在线算法设计310
11.1在线算法设计的基本概念310
11.2页调度问题312
11.3势函数分析314
11.4k服务问题315
11.4.1竞争比的下界315
11.4.2平衡算法316
11.4.3对称移动算法317
11.5Steiner树问题320
11.6在线任务调度321
11.7负载平衡322
小结323
习题324
词汇索引325
参考文献330
