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

　　算法无疑是计算机科学的重要组成部分，近年来发展极其迅速。“算法与算法复杂性分析”已是计算机专业本科生，特别是研究生的一门必须掌握的内容。一个大家熟悉的公式：程序=算法+数据结构，这说明算法的研究不单是数学问题，和数据结构密切相关，这是必须强调的，此外还需明确，只有通过实践才能掌握算法的实质。本书是在原《组合数学（算法与分析）》下册的基础上改写而成的。书中的内容与结构都作了极大的改变。本书共分29章讨论了29个问题，前6章为：动态规划、优先策略、分治策略、哈佛曼编码、线性规划的分解原理、最佳二分树。第7～10章为内存分类法。第11章为求第K个元素。第12、13章为外存分类法和分类网络。第14～16章为查找及树。第17章为哈希表。第18章为DFS与BFS算法。第19章为α-β剪技术和分支定界法。第20章为整数规划。第21～27章分别为串匹配、概率算法、并行算法、脉动阵列的并行处理、计算几何、NP完备理论、近似算法。第28章为密码学简介。第29章为LP问题的多项式算法，对算法和它的复杂性作了分析。本书可作为计算机系本科学生及研究生教材，对数学系师生和科研工作者可作为参考书。

暂缺《计算机算法导引：设计与分析》作者简介

绪论                  
 第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. 2  0-1原理                  
 13. 3  归并网络                  
 13. 4  巴特塞尔(Batcher)奇偶归并网络                  
 习题                  
 第14章  查找及均衡树                  
 14. 1  AVL树--关于高度均衡的二分树                  
 14. 2  关于高度均衡的二分树的插入和删除                  
 习题                  
 第15章  2-3树和2-3-4树                  
 15. 1  2-3树                  
 15. 2  2-3-4树                  
 15. 3  红黑树                  
 习题                  
 第16章  B-树                  
 16. 1  B-树概念                  
 16. 2  插入和删除                  
 习题                  
 第17章  哈希表                  
 17. 1  什么是哈希表                  
 17. 2  哈希函数的构造方法                  
 17. 3  解决冲突的方法                  
 17. 4  哈希算法的分析(线性探测法分析)                  
 17. 5  二重哈希法                  
 习题                  
 第18章  DFS算法和BFS算法                  
 18. 1  概述                  
 18. 2  DFS算法                  
 18. 3  无向图的DFS算法                  
 18. 4  有向图的DFS算法                  
 18. 5  互连通块问题                  
 18. 6  强连通块问题                  
 18. 7  BFS算法                  
 习题                  
 第19章  a- 剪枝术和分支定界法                  
 19. 1  a- 剪枝术                  
 19. 2  分支定界法和流动推销员问题                  
 19. 3  同顺序加工任务安排问题                  
 习题                  
 第20章　整数规划                  
 20. 1  概述                  
 20. 2  0-1规划和它的DFS搜索(隐枚举)解法                  
 20. 3  分支定界法在解整数规划中的应用                  
 习题                  
 第21章  串匹配                  
 21. 1  概述                  
 21. 2  KMP克鲁斯-摩尼斯-普拉特(Knuth-Morris-Pratt)算法                  
 21. 3  BM坡艺尔-摩尔(Boyer-Moore)算法                  
 21. 4  RK拉宾-卡普(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. 3  RSA公钥密码                  
 28. 4  数字签名                  
 28. 5  Hash算法                  
 习题                  
 第29章  LP问题的多项式算法                  
 29. 1  Klee和Minty举例                  
 29. 2  Xavu加(哈奇扬)算法                  
 29. 3  Karmarkar算法                  
 习题