《算法设计与分析第二版》是2008年清华大学出版社出版的图书，作者是王晓东。本书可以作为高等院校计算机专业本科生和研究生学习计算机算法设计的教材，也可供广大工程技术人员和自学读者学习参考。
本书采用面向对象的JAVA语言作为表述手段，在保持JAVA优点的同时，尽量使算法的描述简明、清晰。为了加深对知识的理解，各章配有难易适当的习题，以适应不同程度读者练习的需要。
本书内容丰富,观点新颖,理论联系实际。采用Java语言描述算法,简明清晰、结构紧凑,可读性强。本书可以作为高等院校计算机专业本科生和研究生学习计算机算法设计的教材,也可供广大工程技术人员和自学读者学习参考。
为了适应培养21世纪计算机人才的需要,结合我国高等院校教育工作的现状,立足培养学生能跟上国际计算机科学技术的发展水平,更新教学内容和教学方法,本书以算法设计策略为知识单元,系统地介绍计算机算法的设计方法与分析技巧,以期为计算机科学与技术学科的学生提供广泛而坚实的计算机算法基础知识。
目录
- 第1章 算法引论
- 1.1 算法与程序
- 1.2 表达算法的抽象机制
- 1.3 描述算法
- 1.4 算法复杂性分析
- 小结
- 习题
- 第2章 递归与分治策略
- 2.1 速归的概念
- 2.2 分治法的基本思想
- 2.3 二分搜索技术
- 2.4 大整数的乘法
- 2.5 Strassen矩阵乘法
- 2.6 棋盘覆盖
- 2.7 合并排序
- 2.8 快速排序
- 2.9 线性时间选择
- 2.10 最接近点对问题
- 2.11 循环赛日程表
- 小结
- 习题
- 第3章 动态规划
- 3.1 矩阵连乘问题
- 3.2 动态规划算法的基本要素
- 3.3 最长公共子序列
- 3.4 凸多边形最优三角剖分
- 3.5 多边形游戏
- 3.6 图像压缩
- 3.7 电路布线
- 3.8 流水作业调度
- 3.9 0-1背包问题
- 3.10 最优二叉搜索树
- 小结
- 习题
- 第4章 贪心算法
- 4.1 活动安排问题
- 4.2 贪心算法的基本要素
- 4.2.1 贪心选择性质
- 4.2.2 最优子结构性质
- 4.2.3 贪心算法与动态规划算法的差异
- 4.3 最优装载
- 4.4 哈夫曼编码
- 4.4.1 前缀码
- 4.4.2 构造哈夫曼编码
- 4.4.3 哈夫曼算法的正确性
- 4.5 单源最短路径
- 4.5.1 算法基本思想
- 4.5.2 算法的正确性和计算复杂性
- 4.6 最小生成树
- 4.6.1 最小生成树性质
- 4 6.2 Prim算法
- 4.6.3 Kruskal算法
- 4.7 多机调度问题
- 4.8 贪心算法的理论基础
- 4.8.1 拟阵
- 4.8.2 带权拟阵的贪心算法
- 4.8.3 任务时间表问题
- 小结
- 习题
- 第5章 回溯法
- 5.1 回溯法的算法框架
- 5.1.1 问题的解空间
- 5.1.2 回溯法的基本思想
- 5.1.3 递归回溯
- 5.1.4 迭代回溯
- 5.1.5 子集树与排列树
- 5.2 装载问题
- 5.3 批处理作业调度
- 5.4 符号三角形问题
- 5.5 n后问题
- 5.6 0-1背包问题
- 5.7 最大团问题
- 5.8 图的m着色问题
- 5.9 旅行售货员问题
- 5.10 圆排列问题
- 5.11 电路板排列问题
- 5.12 连续邮资问题
- 5.13 回溯法的效率分析
- 小结
- 习题
- 第6章 分支限界法
- 6.1 分支限界法的基本思想
- 6.2 单源最短路径问题
- 6.3 装载问题
- 6.4 布线问题
- 6.5 0-1背包问题
- 6.6 最大团问题
- 6.7 旅行售货员问题
- 6.8 电路板排列问题
- 6.9 批处理作业调度
- 小结
- 习题
- 第7章 概率算法
- 7.1 随机数
- .2 数值概率算法
- 7.2.1 用随机投点法计算л值
- 7.2.2 计算定积分
- 7.2.3 解非线性方程组
- 7.3 舍伍德算法
- 7.3.1 线性时间选择算法
- 7.3.2 跳跃表
- 7.4 拉斯维加斯算法
- 7.4.1 n后问题
- 7.4.2 整数因子分解
- 7.5 蒙特卡罗算法
- 7.5.1 蒙特卡罗算法的基本思想
- 7.5.2 主元素问题
- 7.5.3 素数测试
- 小结
- 习题
- 第8章 NP完全性理论
- 8.1 计算模型
- 8.1.1 随机存取机RAM
- 8.1.2 随机存取存储程序机RASP
- 8.1.3 RAM模型的变形与简化
- 8.1.4 图灵机
- 8.1.5 图灵机模型与RAM模型的关系
- 8.1.6 问题变换与计算复杂性归约
- 8.2 P类与NP类问题
- 8.2.1 非确定性图灵机
- 8.2.2 P类与NP类语言
- 8.2.3 多项式时间验证
- 8.3 NP完全问题
- 8.3.1 多项式时间变换
- 8.3.2 Cook定理
- 8.4 一些典型的NP完全问题
- 8.4.1 合取范式的可满足性问题
- 8.4.2 3元合取范式的可满足性问题
- 8.4.3 团问题
- 8.4.4 顶点覆盖问题
- 8.4.5 子集和问题
- 8.4.6 哈密顿回路问题
