计算机算法导引.doc

第1部分 基 本 算 法第1章 数学准备1.1 母函数1.2 递推关系1.3 Fibonacci 数列1.3.1 Fibonacci 数列是典型的递推关系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.3 BBS法4.3.4 素数法4.4 素数的概率判定算法4.4.1 关于素数的若干定理4.4.2 Fermat数4.4.3 MillerRabin的素数概率测试法4.5 定理证明的数学准备4.5.1 数论的基本知识4.5.2 群论的基本知识4.5.3 中国剩余定理4.5.4 xn1 mod p 的解4.6 定理A的证明4.7 定理B的证明习题第5章 并行算法5.1 并行计算机和并行算法的基本概念5.2 递推关系的并行计算5.3 图的并行算法举例5.4 矩阵乘积的并行计算5.5 分布计算5.6 快速傅里叶变换5.6.1 FFT问题的背景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.2 01原理5.9.3 Bn 型网络5.9.4 Mn 归并网络5.10 Batcher 奇偶归并网络5.11 脉动阵列的并行处理5.11.1 矩阵和向量乘法的并行处理5.11.2 矩阵乘法的并行处理5.11.3 带状矩阵的并行乘法习题第6章 搜索法6.1 引论6.2 DFS 搜索法6.3 无向图的 DFS 算法6.4 有向图的 DFS 算法6.5 互通块问题66 强连通块问题6.7 BFS 算法6.8 拓扑排序6.9 minmax 搜索法6.10 流动推销员问题的分支定界法图 6.256.11 同顺序加工任务安排问题习题第7章 数据结构7.1 “堆”和“堆集排序法”7.1.1 堆7.1.2 堆集排序法7.1.3 优先级队和二进制堆7.2 23树7.3 234树7.4 红黑树7.4.1 RB树性质7.4.2 插入7.4.3 删除7.5 B树7.5.1 B树性质7.5.2 B树的插入7.5.3 B树的删除7.6 关于高度的均衡树7.6.1 AVL树关于高度均衡的二分树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.5 FordJohnson 归并插入排序法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.2 Voronoi图9.2.3 Voronoi图的构造法9.2.4 Voronoi图的应用简介9.2.5 Voronoi图的拓广9.3 串匹配9.3.1 搜索法9.3.2 KMP 算法9.3.3 BM 算法9.3.4 RK 算法9.4 数论的算法问题9.4.1 求最大公因数9.4.2 因数分解之一： Pollard 法9.4.3 Dixon 随机平方因数分解法9.4.4 椭圆曲线因数分解法9.5 大数模幂运算9.6 N mod M9.6.1 Barrett归约9.6.2 模乘算法9.6.3 Montgomery 模幂运算9.6.4 n是偶数的情况第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.9 DantzigWolfe 分解算法10.10 整数规划10.10.1 问题的提出10.10.2 01 规划和DFS 搜索法10.10.3 分支定界法10.11 Klee 与 Minty举例第3部分 复杂性理论与智能型算法第11章 算法复杂性理论11.1 图灵机11.2 图灵机和算法11.3 k 条带的图灵机11.4 非确定型图灵机11.5 停机问题11.6 布尔表达式11.7 布尔变量和网络11.8 问题的转换11.9 Cook 定理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