《计算机算法设计与分析(第4版)》是王晓东主编,2012年2月电子工业出版社出版的“十二五”普通高等教育本科国家级规划教材、高等学校规划教材。该教材适合作为大学计算机科学与技术、软件工程、信息安全信息与计算科学等专业本科生和研究生教材,可作为ACM程序设计大赛培训教材,也适合广大丁程技术人员学习参考。
全书以算法设计策略为知识单元,介绍了计算机算法的设计方法与分析技巧。全书共8章,主要内容包括:算法概述、递归与分治策略、动态规划、贪心算法、回溯法、分支限界法、随机化算法、线性规划与网络流等。书中既涉及经典与实用算法及实例分析,又包括算法热点领域追踪。章首增加了学习要点提示,章末配有算法分析题和算法实现题。
目录
- 第1章 算法概述
- 1.1 算法与程序
- 1.2 算法复杂性分析
- 1.3 NP完全性理论
- 算法分析题1
- 算法实现题1
- 第2章 递归与分治策略
- 2.1 递归的概念
- 2.2 分治法的基本思想
- 2.3 二分搜索技术
- 2.4 大整数的乘法
- 2.5 Strassen矩阵乘法
- 2.6 棋盘覆盖
- 2.7 合并排序
- 2.8 快速排序
- 2.9 线性时间选择
- 2.10 最接近点对问题
- 2.11 循环赛日程表
- 算法分析题2
- 算法实现题2
- 第3章 动态规划
- 3.1 矩阵连乘问题
- 3.2 动态规划算法的基本要素
- 3.3 最长公共子序列
- 3.4 最大子段和
- 3.5 凸多边形最优三角剖分
- 3.6 多边形游戏
- 3.7 图像压缩
- 3.8 电路布线
- 3.9 流水作业调度
- 3.10 0-1背包问题
- 3.11 最优二叉搜索树
- 算法分析题3
- 算法实现题3
- 第4章 贪心算法
- 4.1 活动安排问题
- 4.2 贪心算法的基本要素
- 4.3 最优装载
- 4.4 哈夫曼编码
- 4.5 单源最短路径
- 4.6 最小生成树
- 4.7 多机调度问题
- 算法分析题4
- 算法实现题4
- 第5章 回溯法
- 5.1 回溯法的算法框架
- 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 回溯法的效率分析
- 算法分析题5
- 算法实现题5
- 第6章 分支限界法
- 6.1 分支限界法的基本思想
- 6.2 单源最短路径问题
- 6.3 装载问题
- 6.4 布线问题
- 6.5 0-1背包问题
- 6.6 最大团问题
- 6.7 旅行售货员问题
- 6.8 电路板排列问题
- 6.9 批处理作业调度
- 算法分析题6
- 算法实现题6
- 第7章 随机化算法
- 7.1 随机数
- 7.2 数值随机化算法
- 7.2.1 用随机投点法计算π值
- 7.2.2 计算定积分
- 7.2.3 解非线性方程组
- 7.3 舍伍德(Sherwood)算法
- 7.3.1 线性时间选择算法
- 7.3.2 搜索有序表
- 7.3.3 跳跃表
- 7.4 拉斯维加斯(Las Vegas)算法
- 7.4.1 n后问题
- 7.4.2 整数因子分解
- 7.5 蒙特卡罗(Monte Carlo)算法
- 7.5.1 蒙特卡罗算法的基本思想
- 7.5.2 主元素问题
- 7.5.3 素数测试
- 算法分析题7
- 算法实现题7
- 第8章 线性规划与网络流
- 8.1 线性规划问题和单纯形算法
- 8.1.1 线性规划问题及其表示
- 8.1.2 线性规划基本定理
- 8.1.3 约束标准型线性规划问题的单纯形算法
- 8.1.4 将一般问题转化为约束标准型
- 8.1.5 一般线性规划问题的两阶段单纯形算法
- 8.1.6 单纯形算法的描述和实现
- 8.1.7 退化情形的处理
- 8.1.8 应用举例
- 8.2 最大网络流问题
- 8.2.1 网络与流
- 8.2.2 增广路算法
- 8.2.3 预流推进算法
- 8.2.4 最大流问题的变换与应用
- 8.3 最小费用流问题
- 8.3.1 最小费用流
- 8.3.2 消圈算法
- 8.3.3 最小费用路算法
- 8.3.4 网络单纯形算法
- 8.3.5 最小费用流问题的变换与应用算法分析题8
- 算法实现题8
- 附录A C++概要
- 1.变量、指针和引用
- 2.函数与参数传递
- 3. C++的类
- 4.类的对象
- 5.构造函数与析构函数
- 6.运算符重载
- 7.友元函数
- 8.内联函数
- 9.结构
- 10.联合
- 11.异常
- 12.模板
- 13.动态存储分配
- 参考文献