算法设计与分析（第3版）
《算法设计与分析（第3版）》是由王晓东编著，2014年清华大学出版社出版的普通高等教育“十一五”国家级规划教材、21世纪大学本科计算机专业系列教材。该教材不仅可用作高等学校计算机专业本科生和研究生学习计算机算法设计的教材，而且也适合工程技术人员和自学读者学习参考。
全书共分11章。该教材以算法设计策略为知识单元，介绍了计算机算法的设计方法与分析技巧。
算法设计与分析（第3版）基本信息
| 书 名 | 算法设计与分析（第3版） | 作 者 | 王晓东 |
|---|---|---|---|
| 类 别 | 普通高等教育“十一五”国家级规划教材 | 出版社 | 清华大学出版社 |
| 出版时间 | 2014年1月1日 | 页 数 | 330 页 |
| 开 本 | 16 开 | 装 帧 | 平装 |
| ISBN | 9787302348641 | 字 数 | 524千字 |
| CIP核字号 | 2013310958 | ||
| 第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.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.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布线问题167 6.50-1背包问题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 |
（注：目录排版顺序为从左列至右列）
算法设计与分析（第3版）造价信息
该教材有配套教材——《算法设计与分析习题解答（第3版）》，书中对主教材的全部习题做了解答。
| 书名 |
书号 |
出版社 |
出版时间 |
作者 |
|---|---|---|---|---|
| 《算法设计与分析习题解答（第3版）》 |
9787302348634 |
清华大学出版社 |
2014.02.01 |
王晓东 |
算法设计与分析（第3版）修订过程
该教材是为了适应培养中国21世纪计算机各类人才的需要，结合中国高等学校教育工作的现状，立足培养学生能跟上国际计算机科学技术的发展水平，更新教学内容和教学方法，提高教学质量的基础上编写而成。
该教材由王晓东编著。在编写过程中，得到教育部高等学校计算机类专业教学指导委员会的支持。福州大学“211工程”计算机与信息工程重点学科实验室为该教材的写作提供了设备与工作环境。南京大学宋方敏教授和福州大学傅清祥教授审阅了全书，提出了改进意见。
算法设计与分析（第3版）出版工作
2014年1月1日，该教材由清华大学出版社出版。
| 责任编辑 |
封面设计 |
责任校对 |
责任印制 |
|---|---|---|---|
| 张瑞庆 |
傅瑞学 |
时翠兰 |
何芊 |
算法设计与分析（第3版）常见问题
-
易用性原则方便上网客户浏览和操作，最大限度地减轻后台管理人员的负担，做到部分业务的自动化处理。安全性原则系统采取全面的安全保护措施，具有防病毒感染、防黑客攻击措施，同时在防雷击、过载、断电和人为破坏方...
-
易用性原则 方便上网客户浏览和操作，最大限度地减轻后台管理人员的负担，做到部分业务的自动化处理。 安全性原则 系统采取全面的安全保护措施，具有防病毒感染、防黑客攻击措施，同时在防雷击、过载、断电...
-
我们河南定额模板工程量一般情况与现浇混凝土构件工程量是相同的，不是按面积计算的，大多数是按混凝土体积计算的，但楼梯是按投影面积计算的。
该教材以算法设计策略为知识单元，介绍了计算机算法的设计方法与分析技巧。
全书共分11章。
在第1章中首先介绍算法的基本概念，接着简要阐述算法的计算复杂性和算法的描述，然后围绕设计算法常用的基本设计策略组织第2章至第10章的内容。
第2章介绍递归与分治策略，这是设计有效算法最常用的策略。
第3章是动态规划算法，以具体实例详述动态规划算法的设计思想、适用性以及算法的设计要点。
第4章介绍贪心算法，这也是一种重要的算法设计策略，它与动态规划算法的设计思想有一定的联系，但其效率更高。按贪心算法设计出的许多算法能导致最优解。
第5章和第6章分别介绍回溯法和分支限界法。这两章所介绍的算法适合于处理难解问题。
第7章介绍概率算法，对许多难解问题提供高效的解决途径，是有较高实用价值的算法设计策略。
第8章介绍NP完全性理论。首先介绍计算模型、确定性和非确定性图灵机，然后进一步介绍NP完全性理论。
第9章介绍了解NP难问题的近似算法，这是计算机算法领域的热门研究课题，具有较高的实用价值。
第10章通过实例介绍算法设计中常用的算法优化策略。
最后，在第11章介绍算法设计中较新的研究领域——在线算法设计。
在该教材各章的论述中，首先介绍一种算法设计策略的基本思想，然后从解决计算机科学与应用中出现的实际问题入手，由简到繁地描述几个经典的精巧算法，同时对每个算法所需要的时间和空间进行分析。
在为各种算法设计策略选择用于展示其设计思想与技巧的具体应用问题时，该教材有意重复选择某些经典问题，使读者能体会到一个问题可以用多种设计策略求解。同时，通过对解同一问题的不同算法的比较，更容易体会到每一个具体算法的设计要点。随着该教材内容的逐步展开，读者也将进一步感受到综合应用多种设计策略可以更有效地解决问题。
该教材采用面向对象的Java语言作为表述手段，在保持Java优点的同时，尽量使算法的描述简明。为了加深对知识的理解，各章配有难易适当的习题，以适应不同程度读者练习的需要。
王晓东，男，1957年出生，山东人，中共党员，现任福建工程学院副院长、教授、博士生导师。先后担任福州大学计算机系主任、数学与计算机科学学院院长，2007年8月起担任泉州师范学院副院长，2014年8月起任现职。 2100433B
算法设计与分析（第3版）文献
算法设计与分析报告实验报告材料-实用模板
实 验 报 告 （2016/2017 学年 第一学期） 学生姓名 周文超 班级学号 B14041527 学院 (系) 计算机学院、 软件学院 专 业 软件工程 课程名称 算法分析与设计 实验名称 分治策略 实验时间 2016 年 10 月 18 日 指导单位 计算机学院软件教学中心 指导教师 季一木 2 实 验 报 告 实验名称 分治策略 指导教师 季一木 实验类型 验证 实验学时 2 实验时间 2016.10.18 一、 实验目的和任务 1.理解分治法的算法思想， 阅读实现书上已有的部分程序代码并完善程 序，加深对分治法的算法原理及实现过程的理解。 2. 用分治法实现一组无序序列的两路合并排序和快速排序。要求清楚 合并排序及快速排序的基本原理， 编程实现分别用这两种方法将输入的一组 无序序列排序为有序序列后输出。 3 二、 实验环境 (实验设备 ) 算法设计与分析课本 笔记本
基于关键链的软件开发项目管理缓冲区设置算法设计与分析
随着信息科技的飞速发展,项目管理系统在各类项目管理中占据了重要地位,越来越多的自动化管理代替了传统的人工项目管理。大多项目管理系统均采用了关键链方法,在关键链方法中缓冲区的设置是关键因素之一。因此关键链方法的缓冲区设置成为一个新的应用课题。本文在深入研究并对比现有的缓冲区计算方法的基础上,提出了综合考虑项目管理者的风险偏好、工序的复杂程度以及资源约束等几个因素,再利用时间差的方法,设计并模拟实现一种缓冲区设置的算法,具有相当大的实用价值。
-
配套教材
《计算机算法设计与分析（第5版）》有配套教材——《计算机算法设计与分析习题解答（第5版）》 。
| 书名 |
ISNB |
出版社 |
出版时间 |
作者 |
|---|---|---|---|---|
| 《计算机算法设计与分析习题解答（第5版）》 |
9787121344381 |
电子工业出版社 |
2018年10月 |
王晓东 |
《计算机算法设计与分析（第5版）》修正了第4版中发现的一些错误，并将各章的习题分为算法分析题和算法实现题两部分，增加了算法实践性内容，增加了有关串和序列的算法内容。
该教材各章的论述中，首先介绍一种算法设计策略的基本思想，然后从解决计算机科学和应用中的实际问题入手，描述几个算法。同时对每个算法所需的时间和空间进行分析，使读者既能学到一些常用的算法，也能通过对算法设计策略的反复应用，牢固掌握这些算法设计的基本策略。该教材选择某些问题，通过对解同一问题的不同算法的比较，使读者体会到每种算法的设计要点。
该教材采用面向对象的C 语言作为算法描述手段，在保持C 优点的同时，尽量使算法描述简明、清晰。每章的章首为学习要点提示，章末配有难易适度的习题，分为算法分析题和算法实现题两部分，以强化实践环节 。
《计算机算法设计与分析（第5版）》共9章，具体如下：
第1章介绍算法的基本概念，并对算法的计算复杂性和算法的描述做了阐述。然后围绕算法设计常用的基本设计策略组织了第2～9章的内容。
第2章介绍递归与分治策略。
第3章介绍动态规划算法，以具体实例讲述动态规划算法的设计思想、适用性及算法的设计要点。
第4章介绍贪心算法，它也是一种算法设计策略，它与动态规划算法的设计思想有一定的联系。
第5章和第6章分别介绍回溯法和分支限界法。这两章所介绍的算法适合处理难解问题。
第7章介绍随机化算法，对难解问题提供了解决途径。
第8章介绍线性规划与网络流算法。许多实际应用问题可以转化为线性规划和网络流问题，并可用第8章中的算法有效求解。
第9章介绍在大数据和人工智能中有应用的串和序列的算法 。
算法设计与分析（第3版）相关推荐
- 相关百科
- 相关知识
- 相关专栏
- 算法设计与数据结构
- 算法设计方法与优化
- 算法设计方法
- 管与管板的焊接工艺评定试验
- 管丽环境技术（上海）有限公司
- 管件水压试验机
- 管内传热
- 管内运输
- 管内降膜式再沸器
- 管制弹性法案
- 管制
- 管包
- 管嘴出流
- 管城回族区城乡建设和交通运输局
- 管壁厚度测厚仪MMX-6DL
- 管壳式换热器用非金属垫片
- 以MSP430FW427为核心的远程数字水表设计
- cnas-cc012007新版认可规范
- 乍嘉苏高速公路改性沥青SMA—13面层试验段施工
- 简易六角砖铺设装置CN109537417A
- 招标合同工程建设招标设标合同合同条件(第2部分)
- 招投标授权委托书(20200813145124)
- 乍嘉苏高速公路改性沥青SMA-13面层试验段施工
- 中国水电联合体13亿美元总承包尼日利亚水电站项目
- 张力膜结构的设计与分析——某商业中心屋顶风雨操场
- 以S3C2410为核心的简易智能家居监控系统设计
- 云南红河3层板式建筑食堂62#-食堂工程造价指标
- 政府采购非招标采购方式管理办法(财政部第74号)
- 引水隧洞工程中热应力中对围岩表层稳定性的影响分析
- 制水泥楼板市场现状调研及发展前景分析报告(目录)
- 张潘明污水处理厂初步设计说明书(水质工程学课程)
- 云南洱海桃溪河口净化工程的设计思路及初步净化效果
最新词条
安徽省政采项目管理咨询有限公司
数字景枫科技发展（南京）有限公司
怀化市人民政府电子政务管理办公室
河北省高速公路京德临时筹建处
中石化华东石油工程有限公司工程技术分公司
手持无线POS机
广东合正采购招标有限公司
上海城建信息科技有限公司
甘肃鑫禾国际招标有限公司
烧结金属材料
齿轮计量泵
广州采阳招标代理有限公司河源分公司
高铝碳化硅砖
博洛尼智能科技（青岛）有限公司
烧结刚玉砖
深圳市东海国际招标有限公司
搭建香蕉育苗大棚
SF计量单位
福建省中亿通招标咨询有限公司
泛海三江
威海鼠尾草
广东国咨招标有限公司
Excel 数据处理与分析应用大全
甘肃中泰博瑞工程项目管理咨询有限公司
山东创盈项目管理有限公司
拆边机
当代建筑大师
广西北缆电缆有限公司
大山槟榔
上海地铁维护保障有限公司通号分公司
舌花雏菊
甘肃中维国际招标有限公司
华润燃气（上海）有限公司
湖北鑫宇阳光工程咨询有限公司
GB8163标准无缝钢管
中国石油炼化工程建设项目部
韶关市优采招标代理有限公司
莎草目
建设部关于开展城市规划动态监测工作的通知
电梯平层准确度
广州利好来电气有限公司
苏州弘创招投标代理有限公司