|
|
|||
|
|
|||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||
|
||
| 本书为《计算机算法导引——设计与分析》的第2版。书中内容分3部分：第1部分是基本算法，按方法论区分，包含优先策略与分治策略、动态规划、概率算法、并行算法、搜索法、数据结构等；第2部分是若干专题，包括排序算法、计算几何及计算数论、线性规划；第3部分是复杂性理论与智能型算法，其中，智能型算法主要介绍了遗传算法和模拟退火算法。 本书可作为计算机系本科学生及研究生教材，数学系师生和科研工作者也可将其作为参考书。 |
|
||
|
||
| 第1部分基 本 算 法 第1章数学准备 11母函数 12递推关系 13Fibonacci 数列 131Fibonacci 数列是典型的递推关系 132问题的解 14线性常系数递推关系举例 15其他类型的递推关系举例 习题 第2章优先策略与分治策略 21优先策略：求最短树的 Kruskal 算法 22求最短树的 Prim 算法 23求最短路径的 Dijkstra 算法 24文件存储问题 25有期限的任务安排问题 26数据压缩和 Huffman 树 27分治策略与二分查找 28整数乘法 29矩阵乘积的 Strassen 算法 210矩阵乘积的Winograd算法 211布尔矩阵乘积的分段预处理方法 212归并排序法 213快速排序法 214求序列中的第k个元素 习题 第3章动态规划 31最短路径问题 32最佳原理 33流动推销员问题 331算法及例题 332复杂性估计 34矩阵链乘问题 35最长公共子序列 36图的任意两点间的最短距离 37同顺序流水作业的任务安排问题 38可靠性问题 39最佳二分树 391二分树的一些性质 392最佳二分树的构成 习题 第4章概率算法 41生日问题 42概率算法举例 43随机数的产生器 431线性同余式法 432离散对数法 433BBS法 434素数法 44素数的概率判定算法 441关于素数的若干定理 442Fermat数 443MillerRabin的素数概率测试法 45定理证明的数学准备 451数论的基本知识 452群论的基本知识 453中国剩余定理 454xn≡1 mod p 的解 46定理A的证明 47定理B的证明 习题 第5章并行算法 51并行计算机和并行算法的基本概念 52递推关系的并行计算 53图的并行算法举例 54矩阵乘积的并行计算 55分布计算 56快速傅里叶变换 561FFT问题的背景 562预备定理 563快速算法 564傅里叶逆变换 565计算结果的重排 566复杂性估计 57卷积及其应用 571卷积 572多项式的一种快速乘法 58数论变换 59排序网络 591引论 59201原理 593Bn 型网络 594Mn 归并网络 510Batcher 奇偶归并网络 511脉动阵列的并行处理 5111矩阵和向量乘法的并行处理 5112矩阵乘法的并行处理 5113带状矩阵的并行乘法 习题 第6章搜索法 61引论 62DFS 搜索法 63无向图的 DFS 算法 64有向图的 DFS 算法 65互通块问题 66强连通块问题 67BFS 算法 68拓扑排序 69minmax 搜索法 610流动推销员问题的分支定界法 611同顺序加工任务安排问题 习题 第7章数据结构 71“堆”和“堆集排序法” 711堆 712堆集排序法 713优先级队和二进制堆 7223树 73234树 74红黑树 741RB树性质 742插入 743删除 75B树 751B树性质 752B树的插入 753B树的删除 76关于高度的均衡树 761AVL树——关于高度均衡的二分树 762关于高度均衡的二分树的插入和删除 77哈希表 771什么是哈希表 772哈希函数的构造方法 773解决冲突的方法 774哈希算法的分析(线性探测法分析) 775二重哈希法 习题 第2部分若 干 专 题 第8章排序算法 81排序 82下界估计 83二分插入排序法 84下溢排序法 85FordJohnson 归并插入排序法 851算法的非形式化描述 852一般情形的讨论 853算法分析 86外存排序 861外存归并排序法 862三条带的外存归并排序法 863阶式归并法 第9章计算几何及计算数论 91关于线段问题 92凸包问题与Voronoi问题 921凸包问题 922Voronoi图 923Voronoi图的构造法 924Voronoi图的应用简介 925Voronoi图的拓广 93串匹配 931搜索法 932KMP 算法 933BM 算法 934RK 算法 94数论的算法问题 941求最大公因数 942因数分解之一： Pollard ρ法 943Dixon 随机平方因数分解法 944椭圆曲线因数分解法 95大数模幂运算 951常规算法 96N mod M 961Barrett归约 962模乘算法 963Montgomery 模幂运算 964n是偶数的情况 第10章线性规划 101问题的提出 102线性规划的几何意义 103单纯形法理论基础 104单纯形法及单纯形表格 105改善的单纯形法表格 106对偶原理 1061对偶概念 1062对偶问题的经济意义 1063对偶问题的性质 1064对偶定理 1065影子价格 107对偶单纯形法 108退化情况及其他 1081退化情况 1082退化情况的循环不已与Bland 法则 109DantzigWolfe 分解算法 1010整数规划 10101问题的提出 1010201 规划和DFS 搜索法 10103分支定界法 1011Klee 与 Minty举例 第3部分复杂性理论与智能型算法 第11章算法复杂性理论 111图灵机 112图灵机和算法 113k 条带的图灵机 114非确定型图灵机 115停机问题 116布尔表达式 117布尔变量和网络 118问题的转换 119Cook 定理 1110几个 NP 完备的例子 1111复杂度类 1112近似解法 11121任务安排的近似算法 11122装箱问题的近似算法 11123流动推销员问题的近似算法 11124顶点覆盖问题的近似算法 1113近代密码学简介 11131密码概念 11132背包公钥密码 11133RSA 公钥密码 第12章智能型算法 121遗传算法 122什么是遗传算法 123TSP 问题 1231编码 1232初始“种群”的生成 1233杂交 1234变异算术 1235模式定理 124模拟退火算法简介 习题 |