2016新编计算机算法导引

《2016新编计算机算法导引》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第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、2.11布尔矩阵乘积的分段预处理方法2.12归并排序法2.13快速排序法2.14求序列中的第k个元素习题第2章动态规划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最佳二分树的构成习题第2章概率算法4.1生日问题4.2概率算法举例4.3随机数的产生器4.3.1线性同余式法4.3.2离散对数法4.3.3BBS法4.3

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≡1modp的解4.6定理A的证明4.7定理B的证明习题第2章并行算法5.1并行计算机和并行算法的基本概念5.2递推关系的并行计算5.3图的并行算法举例5.4矩阵乘积的并行计算5.5分布计算5.6快速傅里叶变换5.6.1FFT问题的背景5.6.2预备定理5.6.3快速算法5.6.4傅里叶

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带状矩阵的并行乘法习题第2章搜索法6.1引论6.2DFS搜索法6.3无向图的DFS算法6.4有向图的DFS算法6.5互通块问题6．6强连通块问题6.7BFS算法6.8拓扑排序6.

5、9minmax搜索法6.10流动推销员问题的分支定界法图6.256.11同顺序加工任务安排问题习题第2章数据结构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哈希函数的构

6、造方法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.3Vorono

7、i图的构造法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.6NmodM9.6.1Barrett归约9.6.2模乘算法9.6.3Montgomery模幂运算9.6.4n是偶数的情况第10章线性规划10.1问题的提出10.2线性规划的几何意义10.3单纯形法

8、理论基础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退化情况