算法设计技巧与分析(修订版)-(沙特阿拉伯)M.H.阿苏外耶著曹霑懋译
教材资讯 •
算法设计技巧与分析(修订版)-(沙特阿拉伯)M.H.阿苏外耶著曹霑懋译
目录
第一部分 基本概念和算法导引
第1章 算法分析基本概念
1.1 引言
1.2 历史背景
1.3 二分搜索
1.4 合并两个已排序的表
1.5 选择排序
1.6 插入排序
1.7 自底向上合并排序
1.8 时间复杂性
1.9 空间复杂性
1.10 很优算法
1.11 如何估计算法的运行时间
1.12 最坏情况和平均情况的分析
1.13 平摊分析
1.14 输入大小和问题实例
1.15 分治递推式
1.16 练习
1.17 参考注释
第2章 数据结构
2.1 引言
2.2 链表
2.3 图
2.4 树
2.5 根树
2.6 二叉树
2.7 练习
2.8 参考注释
第3章 堆和不相交集数据结构
3.1 引言
3.2 堆
3.3 不相交集数据结构
3.4 练习
3.5 参考注释
第二部分 基于递归的技术
第4章 归纳法
4.1 引言
4.2 寻找多数元素
4.3 整数幂
4.4 多项式求值（Horner规则）
4.5 基数排序
4.6 生成排列
4.7 练习
4.8 参考注释
第5章 分治
5.1 引言
5.2 二分搜索
5.3 合并排序
5.4 分治范式
5.5 选择：寻找中项和第k小的元素
5.6 快速排序
5.7 多选
5.8 大整数乘法
5.9 矩阵乘法
5.10 最近点对问题
5.11 练习
5.12 参考注释
第6章 动态规划
6.1 引言
6.2 最长公共子序列问题
6.3 矩阵链相乘
6.4 动态规划范式
6.5 所有点对的最短路径问题
6.6 背包问题
6.7 练习
6.8 参考注释
第三部分 优选割技术
第7章 贪心算法
7.1 引言
7.2 最短路径问题
7.3 最小耗费生成树（Kruskal算法）
7.4 最小耗费生成树(Prim算法)
7.5 文件压缩
7.6 练习
7.7 参考注释
第8章 图的遍历
8.1 引言
8.2 深度优先搜索
8.3 深度优先搜索的应用
8.4 广度优先搜索
8.5 广度优先搜索的应用
8.6 练习
8.7 参考注释
第四部分 问题的复杂性
第9章 NP接近问题
9.1 引言
9.2 P类
9.3 NP类
9.4 NP接近问题的分析
9.5 co-NP类
9.6 三种复杂性类之间的关系
9.7 练习
9.8 参考注释
第10章 计算复杂性引论
10.1 引言
10.2 计算模型：图灵机
10.3 k带图灵机和时间复杂性
10.4 离线图灵机和空间复杂性
10.5 带压缩和线性加速
10.6 复杂性类之间的关系
10.7 归约
10.8 接近性
10.9 多项式时间层次
10.10 练习
10.11 参考注释
第11章 下界
11.1 引言
11.2 平凡下界
11.3 决策树模型
11.4 代数决策树模型
11.5 线性时间归约
11.6 练习
11.7 参考注释
第五部分 克服困难性
第12章 回溯法
12.1 引言
12.2 3着色问题
12.3 8皇后问题
12.4 一般回溯法
12.5 分支限界法
12.6 练习
12.7 参考注释
第13章 随机算法
13.1 引言
13.2 Las Vegas和Monte Carlo算法
13.3 两个简单的例子
13.4 随机快速排序
13.5 随机选择
13.6 占有问题
13.7 尾部界
13.8 Chernoff界的应用：多选
13.9 随机取样
13.10 最小割问题
13.11 测试串的相等性
13.12 模式匹配
13.13 素数测试
13.14 练习
13.15 参考注释
第14章 近似算法
14.1 引言
14.2 基本定义
14.3 差界
14.4 相对性能界
14.5 多项式近似方案
14.6 接近多项式近似方案
14.7 练习
14.8 参考注释
第六部分 域指定问题的迭代改进
第15章 网络流
15.1 引言
15.2 预备知识
15.3 Ford-Fulkerson方法
15.4 优选容量增值
15.5 最短路径增值
15.6 Dinic算法
15.7 MPM算法
15.8 练习
15.9 参考注释
第16章 匹配
16.1 引言
16.2 预备知识
16.3 二分图上的网络流方法
16.4 二分图的匈牙利树方法
16.5 一般图中的优选匹配
16.6 二分图的On2.5算法
16.7 练习
16.8 参考注释
第七部分 计算几何技术
第17章 几何扫描
17.1 引言
17.2 一个简单的例子：计算点集中的极大点
17.3 几何预备知识
17.4 计算线段的交点
17.5 凸包问题
17.6 计算点集的直径
17.7 练习
17.8 参考注释
第18章 Voronoi图解
18.1 引言
18.2 最近点Voronoi图解
18.3 Voronoi图解的应用
18.4 最远点Voronoi图解
18.5 最远点Voronoi图解的应用
18.6 练习
18.7 参考注释
附录A 数学预备知识
附录B 离散概率简介
参考文献
第1章 算法分析基本概念
1.1 引言
1.2 历史背景
1.3 二分搜索
1.4 合并两个已排序的表
1.5 选择排序
1.6 插入排序
1.7 自底向上合并排序
1.8 时间复杂性
1.9 空间复杂性
1.10 很优算法
1.11 如何估计算法的运行时间
1.12 最坏情况和平均情况的分析
1.13 平摊分析
1.14 输入大小和问题实例
1.15 分治递推式
1.16 练习
1.17 参考注释
第2章 数据结构
2.1 引言
2.2 链表
2.3 图
2.4 树
2.5 根树
2.6 二叉树
2.7 练习
2.8 参考注释
第3章 堆和不相交集数据结构
3.1 引言
3.2 堆
3.3 不相交集数据结构
3.4 练习
3.5 参考注释
第二部分 基于递归的技术
第4章 归纳法
4.1 引言
4.2 寻找多数元素
4.3 整数幂
4.4 多项式求值（Horner规则）
4.5 基数排序
4.6 生成排列
4.7 练习
4.8 参考注释
第5章 分治
5.1 引言
5.2 二分搜索
5.3 合并排序
5.4 分治范式
5.5 选择：寻找中项和第k小的元素
5.6 快速排序
5.7 多选
5.8 大整数乘法
5.9 矩阵乘法
5.10 最近点对问题
5.11 练习
5.12 参考注释
第6章 动态规划
6.1 引言
6.2 最长公共子序列问题
6.3 矩阵链相乘
6.4 动态规划范式
6.5 所有点对的最短路径问题
6.6 背包问题
6.7 练习
6.8 参考注释
第三部分 优选割技术
第7章 贪心算法
7.1 引言
7.2 最短路径问题
7.3 最小耗费生成树（Kruskal算法）
7.4 最小耗费生成树(Prim算法)
7.5 文件压缩
7.6 练习
7.7 参考注释
第8章 图的遍历
8.1 引言
8.2 深度优先搜索
8.3 深度优先搜索的应用
8.4 广度优先搜索
8.5 广度优先搜索的应用
8.6 练习
8.7 参考注释
第四部分 问题的复杂性
第9章 NP接近问题
9.1 引言
9.2 P类
9.3 NP类
9.4 NP接近问题的分析
9.5 co-NP类
9.6 三种复杂性类之间的关系
9.7 练习
9.8 参考注释
第10章 计算复杂性引论
10.1 引言
10.2 计算模型：图灵机
10.3 k带图灵机和时间复杂性
10.4 离线图灵机和空间复杂性
10.5 带压缩和线性加速
10.6 复杂性类之间的关系
10.7 归约
10.8 接近性
10.9 多项式时间层次
10.10 练习
10.11 参考注释
第11章 下界
11.1 引言
11.2 平凡下界
11.3 决策树模型
11.4 代数决策树模型
11.5 线性时间归约
11.6 练习
11.7 参考注释
第五部分 克服困难性
第12章 回溯法
12.1 引言
12.2 3着色问题
12.3 8皇后问题
12.4 一般回溯法
12.5 分支限界法
12.6 练习
12.7 参考注释
第13章 随机算法
13.1 引言
13.2 Las Vegas和Monte Carlo算法
13.3 两个简单的例子
13.4 随机快速排序
13.5 随机选择
13.6 占有问题
13.7 尾部界
13.8 Chernoff界的应用：多选
13.9 随机取样
13.10 最小割问题
13.11 测试串的相等性
13.12 模式匹配
13.13 素数测试
13.14 练习
13.15 参考注释
第14章 近似算法
14.1 引言
14.2 基本定义
14.3 差界
14.4 相对性能界
14.5 多项式近似方案
14.6 接近多项式近似方案
14.7 练习
14.8 参考注释
第六部分 域指定问题的迭代改进
第15章 网络流
15.1 引言
15.2 预备知识
15.3 Ford-Fulkerson方法
15.4 优选容量增值
15.5 最短路径增值
15.6 Dinic算法
15.7 MPM算法
15.8 练习
15.9 参考注释
第16章 匹配
16.1 引言
16.2 预备知识
16.3 二分图上的网络流方法
16.4 二分图的匈牙利树方法
16.5 一般图中的优选匹配
16.6 二分图的On2.5算法
16.7 练习
16.8 参考注释
第七部分 计算几何技术
第17章 几何扫描
17.1 引言
17.2 一个简单的例子：计算点集中的极大点
17.3 几何预备知识
17.4 计算线段的交点
17.5 凸包问题
17.6 计算点集的直径
17.7 练习
17.8 参考注释
第18章 Voronoi图解
18.1 引言
18.2 最近点Voronoi图解
18.3 Voronoi图解的应用
18.4 最远点Voronoi图解
18.5 最远点Voronoi图解的应用
18.6 练习
18.7 参考注释
附录A 数学预备知识
附录B 离散概率简介
参考文献
作者简介
曹霑懋，工学博士，现供职于华南师范大学计算机学院副教授，研究生导师
曾作为美国Memphis 大学计算机系访问学者
其研究涉及机器学习，主要从事网状网算法开发以及应用系统模型开发
曾作为美国Memphis 大学计算机系访问学者
其研究涉及机器学习，主要从事网状网算法开发以及应用系统模型开发
主编推荐
“* 本书的组织方式简明扼要，而且包含一般算法书籍中较少涉及的概率算法和近似算法
* 以算法的设计技术为纲，讲述一个又一个的算法技术，然后分析其算法复杂性
* 对于想了解NP接近问题基本概念的读者，本书的篇幅给出了基本但又清楚的描述
“
* 以算法的设计技术为纲，讲述一个又一个的算法技术，然后分析其算法复杂性
* 对于想了解NP接近问题基本概念的读者，本书的篇幅给出了基本但又清楚的描述
“
内容简介
本书是国际有名算法专家李德财教授主编的系列丛书Lecture Notes Series on Computing中的一本
本书涵盖了绝大多数算法设计中的一般技术，在讲解每一种技术时，阐述了它的应用背景，注重用与其他技术相比较的方法说明它的特征，并提供大量实际问题的例子
本书同时也强调了对每一种算法的详细的复杂性分析
全书分七部分共18章，从算法设计与算法分析的基本概念和方法入手，先后介绍了递归、分治、动态规划、贪心算法、图的遍历等技术，对NP接近问题进行了基本但清晰的讨论
作者对概率算法、近似算法和计算几何这些发展迅猛的领域也用一定的篇幅讲述了基本内容
书中每章后都附有大量的练习，有利于读者对书中内容的理解和应用
本书结构简明，内容丰富，可作为计算机学科及相关学科算法课程的教材或参考书，尤其适合已有数据结构和离散数学基础的算法课程，也可作为从事算法研究的工作人员的参考书籍
本书涵盖了绝大多数算法设计中的一般技术，在讲解每一种技术时，阐述了它的应用背景，注重用与其他技术相比较的方法说明它的特征，并提供大量实际问题的例子
本书同时也强调了对每一种算法的详细的复杂性分析
全书分七部分共18章，从算法设计与算法分析的基本概念和方法入手，先后介绍了递归、分治、动态规划、贪心算法、图的遍历等技术，对NP接近问题进行了基本但清晰的讨论
作者对概率算法、近似算法和计算几何这些发展迅猛的领域也用一定的篇幅讲述了基本内容
书中每章后都附有大量的练习，有利于读者对书中内容的理解和应用
本书结构简明，内容丰富，可作为计算机学科及相关学科算法课程的教材或参考书，尤其适合已有数据结构和离散数学基础的算法课程，也可作为从事算法研究的工作人员的参考书籍
价格说明
定价：为出版社全国统一定价
教材价：为商品的销售价，是您最终决定是否购买商品的依据
受系统缓存影响，最终价格以商品放入购物车后显示的价格为准