计算机算法导引：设计与分析

第1部分基 本 算 法
第1章数学准备
1.1母函数
1.2递推关系
1.3Fibonacci 数列
1.3.1Fibonacci 数列是典型的递推关系
1.3.2问题的解
1.4线性常系数递推关系举例
1.5其他类型的递推关系举例
习题
第2章优先策略与分治策略
2.1优先策略：求最短树的 Kruskal 算法
2.2求最短树的 Prim 算法
2.3求最短路径的 Dijkstra 算法
2.4文件存储问题
2.5有期限的任务安排问题
2.6数据压缩和 Huffman 树
2.7分治策略与二分查找
2.8整数乘法
2.9矩阵乘积的 Strassen 算法
2.10矩阵乘积的Winograd算法
2.11布尔矩阵乘积的分段预处理方法
2.12归并排序法
2.13快速排序法
2.14求序列中的第k个元素
习题
第3章动态规划
3.1最短路径问题
3.2最佳原理
3.3流动推销员问题
3.3.1算法及例题
3.3.2复杂性估计
3.4矩阵链乘问题
3.5最长公共子序列
3.6图的任意两点间的最短距离
3.7同顺序流水作业的任务安排问题
3.8可靠性问题
3.9最佳二分树
3.9.1二分树的一些性质
3.9.2最佳二分树的构成
习题
第4章概率算法
4.1生日问题
4.2概率算法举例
4.3随机数的产生器
4.3.1线性同余式法
4.3.2离散对数法
4.3.3BBS法
4.3.4素数法
4.4素数的概率判定算法
4.4.1关于素数的若干定理
4.4.2Fermat数
4.4.3MillerRabin的素数概率测试法
4.5定理证明的数学准备
4.5.1数论的基本知识
4.5.2群论的基本知识
4.5.3中国剩余定理
4.5.4xn≡1 mod p 的解
4.6定理A的证明
4.7定理B的证明
习题
第5章并行算法
5.1并行计算机和并行算法的基本概念
5.2递推关系的并行计算
5.3图的并行算法举例
5.4矩阵乘积的并行计算
5.5分布计算
5.6快速傅里叶变换
5.6.1FFT问题的背景
5.6.2预备定理
5.6.3快速算法
5.6.4傅里叶逆变换
5.6.5计算结果的重排
5.6.6复杂性估计
5.7卷积及其应用
5.7.1卷积
5.7.2多项式的一种快速乘法
5.8数论变换
5.9排序网络
5.9.1引论
5.9.201原理
5.9.3Bn 型网络
5.9.4Mn 归并网络
5.10Batcher 奇偶归并网络
5.11脉动阵列的并行处理
5.11.1矩阵和向量乘法的并行处理
5.11.2矩阵乘法的并行处理
5.11.3带状矩阵的并行乘法
习题
第6章搜索法
6.1引论
6.2DFS 搜索法
6.3无向图的 DFS 算法
6.4有向图的 DFS 算法
6.5互通块问题
6.6强连通块问题
6.7BFS 算法
6.8拓扑排序
6.9minmax 搜索法
6.10流动推销员问题的分支定界法
6.11同顺序加工任务安排问题
习题
第7章数据结构
7.1“堆”和“堆集排序法”
7.1.1堆
7.1.2堆集排序法
7.1.3优先级队和二进制堆
7.223树
7.3234树
7.4红黑树
7.4.1RB树性质
7.4.2插入
7.4.3删除
7.5B树
7.5.1B树性质
7.5.2B树的插入
7.5.3B树的删除
7.6关于高度的均衡树
7.6.1AVL树--关于高度均衡的二分树
7.6.2关于高度均衡的二分树的插入和删除
7.7哈希表
7.7.1什么是哈希表
7.7.2哈希函数的构造方法
7.7.3解决冲突的方法
7.7.4哈希算法的分析(线性探测法分析)
7.7.5二重哈希法
习题
第2部分若 干 专 题
第8章排序算法
8.1排序
8.2下界估计
8.3二分插入排序法
8.4下溢排序法
8.5FordJohnson 归并插入排序法
8.5.1算法的非形式化描述
8.5.2一般情形的讨论
8.5.3算法分析
8.6外存排序
8.6.1外存归并排序法
8.6.2三条带的外存归并排序法
8.6.3阶式归并法
第9章计算几何及计算数论
9.1关于线段问题
9.2凸包问题与Voronoi问题
9.2.1凸包问题
9.2.2Voronoi图
9.2.3Voronoi图的构造法
9.2.4Voronoi图的应用简介
9.2.5Voronoi图的拓广
9.3串匹配
9.3.1搜索法
9.3.2KMP 算法
9.3.3BM 算法
9.3.4RK 算法
9.4数论的算法问题
9.4.1求最大公因数
9.4.2因数分解之一： Pollard ρ法
9.4.3Dixon 随机平方因数分解法
9.4.4椭圆曲线因数分解法
9.5大数模幂运算
9.5.1常规算法
9.6N mod M
9.6.1Barrett归约
9.6.2模乘算法
9.6.3Montgomery 模幂运算
9.6.4n是偶数的情况
第10章线性规划
10.1问题的提出
10.2线性规划的几何意义
10.3单纯形法理论基础
10.4单纯形法及单纯形表格
10.5改善的单纯形法表格
10.6对偶原理
10.6.1对偶概念
10.6.2对偶问题的经济意义
10.6.3对偶问题的性质
10.6.4对偶定理
10.6.5影子价格
10.7对偶单纯形法
10.8退化情况及其他
10.8.1退化情况
10.8.2退化情况的循环不已与Bland 法则
10.9DantzigWolfe 分解算法
10.10整数规划
10.10.1问题的提出
10.10.201 规划和DFS 搜索法
10.10.3分支定界法
10.11Klee 与 Minty举例
第3部分复杂性理论与智能型算法
第11章算法复杂性理论
11.1图灵机
11.2图灵机和算法
11.3k 条带的图灵机
11.4非确定型图灵机
11.5停机问题
11.6布尔表达式
11.7布尔变量和网络
11.8问题的转换
11.9Cook 定理
11.10几个 NP 完备的例子
11.11复杂度类
11.12近似解法
11.12.1任务安排的近似算法
11.12.2装箱问题的近似算法
11.12.3流动推销员问题的近似算法
11.12.4顶点覆盖问题的近似算法
11.13近代密码学简介
11.13.1密码概念
11.13.2背包公钥密码
11.13.3RSA 公钥密码
第12章智能型算法
12.1遗传算法
12.2什么是遗传算法
12.3TSP 问题
12.3.1编码
12.3.2初始“种群”的生成
12.3.3杂交
12.3.4变异算术
12.3.5模式定理
12.4模拟退火算法简介
习题