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

内容简介

　　算法无疑是计算机科学的重要组成部分，近年来发展极其迅速。“算法与算法复杂性分析”已是计算机专业本科生，特别是研究生的一门必须掌握的内容。一个大家熟悉的公式：程序=算法+数据结构，这说明算法的研究不单是数学问题，和数据结构密切相关，这是必须强调的，此外还需明确，只有通过实践才能掌握算法的实质。本书是在原《组合数学（算法与分析）》下册的基础上改写而成的。书中的内容与结构都作了极大的改变。本书共分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算法
习题