计算机算法导引:设计与分析 [平装] 7302022771

本书讨论了动态规划、优先策略、分治策略、线性规划的分解原理、最佳二分树、密码学等29个问题，对算法和它的复杂性作了分析。目 录 绪论 第1章　动态规划 1.1最短路径问题 1.2最佳原理 1.3流动推销员(或旅行商)问题 1.4矩阵链乘问题 1.5最长公共子序列 1.6图的任意两点间的最短距离 1.7整数规划问题 1.8同顺序流水作业的任务安排问题 1.9　可靠性问题 1.10设备更新问题 习题 第2章　优先策略 2.1最短树的库鲁斯卡尔(Kruskal)算法 2.2求最短树的普林(Prim)算法 2.3求最短路径的戴克斯德斯(Dijkstra)算法 2.4文件存储问题 2.5有期限的任务安排问题 习题 第3章　分治策略 3.1二分查找 3.2整数乘法 3.3矩阵乘积的斯德拉逊(Strassen)算法 3.4矩阵乘积的维诺格拉德Winograd算法 3.5布尔矩阵的乘法问题 习题 第4章哈佛曼(Huffman)编码.FFT算法和数据压缩 4.1哈佛曼(Huffman)编码 4.2快速傅里叶变换(FFT) 4.3卷积及其应用 4.4数论变换 习题 第5章线性规划的分解原理 5.1线性规划和单纯形法简介 5.2丹捷-卧佛(Dantzig-Wolfe)分解算法 习题 第6章最佳二分树 6.1二分树 6.2最佳二分树 习题 第7章内存分类法之一：插入分类法.塞尔(SheH)分类法 7.1分类 7.2分类的下界估计 7.3二分插入分类法 7.4塞尔(Shell)分类法 习题 第8章内存分类法之二：递选分类法.堆集分类 8.1递选分类法 8.2二分树递选分类法 8.3堆集分类法 习题 第9章内存分类法之三：下溢分类法.快速分类法 9.1下溢分类法 9.2快速分类法 习题 第10章内存分类法之四：归并分类法和基数分类法 10.1归并分类法 10.2福德-庄生(Ford-Johnson)归并插入分类法 10.3　基数分类法 习题 第11章求第女个元素 11.1求最小及第二小元素 11.2求第k个元素 习题 第12章外存分类法 12.1外存归并分类法 12.2置换选择段的构造 12.3三条带的外存归并分类法 12.4阶式归并法 习题 第13章分类网络 13.1分类网络举例 13.20-1原理 13.3归并网络 13.4巴特塞尔(Batcher)奇偶归并网络 习题 第14章查找及均衡树 14.1AVL树--关于高度均衡的二分树 14.2关于高度均衡的二分树的插入和删除 习题 第15章2-3树和2-3-4树 15.12-3树 15.22-3-4树 15.3红黑树 习题 第16章B-树 16.1B-树概念 16.2插入和删除 习题 第17章哈希表 17.1什么是哈希表 17.2哈希函数的构造方法 17.3解决冲突的方法 17.4哈希算法的分析(线性探测法分析) 17.5二重哈希法 习题 第18章DFS算法和BFS算法 18.1概述 18.2DFS算法 18.3无向图的DFS算法 18.4有向图的DFS算法 18.5互连通块问题 18.6强连通块问题 18.7BFS算法 习题 第19章a-剪枝术和分支定界法 19.1a-剪枝术 19.2分支定界法和流动推销员问题 19.3同顺序加工任务安排问题 习题 第20章　整数规划 20.1概述 20.20-1规划和它的DFS搜索(隐枚举)解法 20.3分支定界法在解整数规划中的应用 习题 第21章串匹配 21.1概述 21.2KMP克鲁斯-摩尼斯-普拉特(Knuth-Morris-Pratt)算法 21.3BM坡艺尔-摩尔(Boyer-Moore)算法 21.4RK拉宾-卡普(Rabin-Karp)算法 习题 第22章　概率算法 22.1概率算法举例 22.2随机数产生法 22.3素数的概率判定算法 习题 第23章并行算法 23.1并行计算机和并行算法的基本概念 23.2递推关系的并行计算 23.3图的并行算法举例 23.4矩阵乘积的并行计算 23.5分布计算 习题 第24章脉动阵列的并行处理 24.1矩阵和向量乘法的并行处理 24.2矩阵乘法的并行处理 24.3带状矩阵的并行乘法 习题 第25章计算几何 25.1关于线段问题 25.2求凸包问题 习题 第26章　NP完备理论 26.1确定型图灵机 26.2可满足性问题 26.3非确定型图灵机与库克(Cook)定理 26.4几个NP完备的例子 26.5复杂度类 习题 第27章近似算法 27.1任务安排的近似算法 27.2装箱问题的近似算法 27.3流动推销员问题的近似算法 27.4顶点覆盖问题的近似算法 习题 第28章密码学简介 28.1什么是密码? 28.2背包公钥密码 28.3RSA公钥密码 28.4数字签名 28.5Hash算法 习题 第29章LP问题的多项式算法 29.1Klee和Minty举例 29.2Xavu加(哈奇扬)算法 29.3Karmarkar算法 习题