算法设计与分析（第4版）

图书标准信息

• 作者 王晓东
• 出版社 清华大学出版社
• 出版时间 2018-10
• 版次 4
• ISBN 9787302510109
• 定价 49.90元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸

【内容简介】

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

【作者简介】

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

【目录】

目录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