由网友(渲染╰塵世的悲傷つ)分享简介：《算法设计取阐发（第三版）》是由王晓东编著，二零一四年清华大教出书社出书的平凡高档教诲“1015”国度级计划学材、二一世纪大教原科计较机业余系列学材。该学材没有仅可用做高档黉舍计较机业余原科熟以及研究熟进修计较机算法设计的学材，并且也合适工程技能职员以及自教读者进修参照。齐书共分一一章。该学材以算法设计计谋为常识单位，先容了计...

《算法设计与分析（第3版）》是由王晓东编著，2014年清华大学出版社出版的普通高等教育“十一五”国家级规划教材、21世纪大学本科计算机专业系列教材。该教材不仅可用作高等学校计算机专业本科生和研究生学习计算机算法设计的教材，而且也适合工程技术人员和自学读者学习参考。

全书共分11章。该教材以算法设计策略为知识单元，介绍了计算机算法的设计方法与分析技巧。

书名

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

ISBN

9787302348641

页数

330页

出版时间

2014年1月1日

开本

16开

CIP核字号

2013310958

作者

王晓东

类别

普通高等教育“十一五”国家级规划教材

出版社

清华大学出版社

装帧

平装

字数

524千字

成书过程

该教材是为了适应培养中国21世纪计算机各类人才的需要，结合中国高等学校教育工作的现状，立足培养学生能跟上国际计算机科学技术的发展水平，更新教学内容和教学方法，提高教学质量的基础上编写而成。

该教材由王晓东编著。在编写过程中，得到教育部高等学校计算机类专业教学指导委员会的支持。福州大学“211工程”计算机与信息工程重点学科实验室为该教材的写作提供了设备与工作环境。南京大学宋方敏教授和福州大学傅清祥教授审阅了全书，提出了改进意见。^[1]

出版工作

2014年1月1日，该教材由清华大学出版社出版。

出版社工作人员

责任编辑	封面设计	责任校对	责任印制
张瑞庆	傅瑞学	时翠兰	何芊[2]

内容简介

该教材以算法设计策略为知识单元，介绍了计算机算法的设计方法与分析技巧。

全书共分11章。

在第1章中首先介绍算法的基本概念，接着简要阐述算法的计算复杂性和算法的描述，然后围绕设计算法常用的基本设计策略组织第2章至第10章的内容。

第2章介绍递归与分治策略，这是设计有效算法最常用的策略。

第3章是动态规划算法，以具体实例详述动态规划算法的设计思想、适用性以及算法的设计要点。

第4章介绍贪心算法，这也是一种重要的算法设计策略，它与动态规划算法的设计思想有一定的联系，但其效率更高。按贪心算法设计出的许多算法能导致最优解。

第5章和第6章分别介绍回溯法和分支限界法。这两章所介绍的算法适合于处理难解问题。

第7章介绍概率算法，对许多难解问题提供高效的解决途径，是有较高实用价值的算法设计策略。

第8章介绍NP完全性理论。首先介绍计算模型、确定性和非确定性图灵机，然后进一步介绍NP完全性理论。

第9章介绍了解NP难问题的近似算法，这是计算机算法领域的热门研究课题，具有较高的实用价值。

第10章通过实例介绍算法设计中常用的算法优化策略。

最后，在第11章介绍算法设计中较新的研究领域——在线算法设计。^[1]

教材目录

第1章算法引论11.1算法与程序11.2表达算法的抽象机制11.3描述算法31.4算法复杂性分析11小结14习题14第2章递归与分治策略162.1递归的概念162.2分治法的基本思想222.3二分搜索技术232.4大整数的乘法242.5Strassen矩阵乘法252.6棋盘覆盖262.7合并排序282.8快速排序302.9线性时间选择332.10最接近点对问题362.11循环赛日程表43小结44习题45第3章动态规划503.1矩阵连乘问题503.2动态规划算法的基本要素553.3最长公共子序列583.4凸多边形最优三角剖分613.5多边形游戏643.6图像压缩673.7电路布线703.8流水作业调度723.90-1背包问题753.10最优二叉搜索树80小结83习题84第4章贪心算法854.1活动安排问题854.2贪心算法的基本要素884.2.1贪心选择性质884.2.2最优子结构性质884.2.3贪心算法与动态规划算法的差异894.3最优装载914.4哈夫曼编码924.4.1前缀码934.4.2构造哈夫曼编码934.4.3哈夫曼算法的正确性954.5单源最短路径974.5.1算法基本思想974.5.2算法的正确性和计算复杂性994.6最小生成树1004.6.1最小生成树性质1004.6.2Prim算法1004.6.3Kruskal算法1024.7多机调度问题1044.8贪心算法的理论基础1064.8.1拟阵1074.8.2带权拟阵的贪心算法1084.8.3任务时间表问题110小结113习题113第5章回溯法1155.1回溯法的算法框架1155.1.1问题的解空间1155.1.2回溯法的基本思想1165.1.3递归回溯1175.1.4迭代回溯1185.1.5子集树与排列树1195.2装载问题1205.3批处理作业调度1265.4符号三角形问题1285.5n后问题1305.60-1背包问题1335.7最大团问题1365.8图的m着色问题1385.9旅行售货员问题1405.10圆排列问题1425.11电路板排列问题1445.12连续邮资问题1475.13回溯法的效率分析149小结152习题152第6章分支限界法1536.1分支限界法的基本思想1536.2单源最短路径问题1566.3装载问题1586.4布线问题1676.50-1背包问题1716.6最大团问题1756.7旅行售货员问题1786.8电路板排列问题1826.9批处理作业调度184小结189习题189第7章概率算法1907.1随机数191

7.2数值概率算法1937.2.1用随机投点法计算π值1937.2.2计算定积分1947.2.3解非线性方程组1967.3舍伍德算法1987.3.1线性时间选择算法1987.3.2跳跃表2007.4拉斯维加斯算法2057.4.1n后问题2067.4.2整数因子分解2097.5蒙特卡罗算法2117.5.1蒙特卡罗算法的基本思想2117.5.2主元素问题2137.5.3素数测试214小结217习题217第8章NP完全性理论2218.1计算模型2218.1.1随机存取机RAM2228.1.2随机存取存储程序机RASP2288.1.3RAM模型的变形与简化2318.1.4图灵机2358.1.5图灵机模型与RAM模型的关系2368.1.6问题变换与计算复杂性归约2388.2P类与NP类问题2398.2.1非确定性图灵机2398.2.2P类与NP类语言2408.2.3多项式时间验证2418.3NP完全问题2438.3.1多项式时间变换2438.3.2Cook定理2448.4一些典型的NP完全问题2478.4.1合取范式的可满足性问题2478.4.23元合取范式的可满足性问题2488.4.3团问题2498.4.4顶点覆盖问题2508.4.5子集和问题2518.4.6哈密顿回路问题2528.4.7旅行售货员问题256小结256习题257第9章近似算法2599.1近似算法的性能2599.2顶点覆盖问题的近似算法2609.3旅行售货员问题近似算法2629.3.1具有三角不等式性质的旅行售货员问题2629.3.2一般的旅行售货员问题2639.4集合覆盖问题的近似算法2649.5子集和问题的近似算法2679.5.1子集和问题的指数时间算法2679.5.2子集和问题的完全多项式时间近似格式268小结270习题270第10章算法优化策略27310.1算法设计策略的比较与选择27310.1.1最大子段和问题的简单算法27310.1.2最大子段和问题的分治算法27410.1.3最大子段和问题的动态规划算法27510.1.4最大子段和问题与动态规划算法的推广27610.2动态规划加速原理27910.2.1货物储运问题27910.2.2算法及其优化27910.3问题的算法特征28310.3.1贪心策略28310.3.2对贪心策略的改进28310.3.3算法三部曲28510.3.4算法实现28510.3.5算法复杂性29010.4优化数据结构29110.4.1带权区间最短路问题29110.4.2算法设计思想29110.4.3算法实现方案29310.4.4并查集29610.4.5可并优先队列29810.5优化搜索策略302小结308习题309第11章在线算法设计31011.1在线算法设计的基本概念31011.2页调度问题31211.3势函数分析31411.4k服务问题31511.4.1竞争比的下界31511.4.2平衡算法31611.4.3对称移动算法31711.5Steiner树问题32011.6在线任务调度32111.7负载平衡322小结323习题324词汇索引325参考文献330

（注：目录排版顺序为从左列至右列^[3]）

教学资源

该教材有配套教材——《算法设计与分析习题解答（第3版）》，书中对主教材的全部习题做了解答。

书名	书号	出版社	出版时间	作者
《算法设计与分析习题解答（第3版）》	9787302348634	清华大学出版社	2014.02.01	王晓东

教材特色

在该教材各章的论述中，首先介绍一种算法设计策略的基本思想，然后从解决计算机科学与应用中出现的实际问题入手，由简到繁地描述几个经典的精巧算法，同时对每个算法所需要的时间和空间进行分析。

在为各种算法设计策略选择用于展示其设计思想与技巧的具体应用问题时，该教材有意重复选择某些经典问题，使读者能体会到一个问题可以用多种设计策略求解。同时，通过对解同一问题的不同算法的比较，更容易体会到每一个具体算法的设计要点。随着该教材内容的逐步展开，读者也将进一步感受到综合应用多种设计策略可以更有效地解决问题。

该教材采用面向对象的Java语言作为表述手段，在保持Java优点的同时，尽量使算法的描述简明。为了加深对知识的理解，各章配有难易适当的习题，以适应不同程度读者练习的需要。^[1]

作者简介

王晓东，男，1957年出生，山东人，中共党员，现任福建工程学院副院长、教授、博士生导师。先后担任福州大学计算机系主任、数学与计算机科学学院院长，2007年8月起担任泉州师范学院副院长，2014年8月起任现职。^[4]