计算机算法导引-设计与分析 (2009 年度畅销榜NO.5632 )

本书为《组合数学(算法与分析)》下册的第二版，书中内容、结构都作了极大的改变。本书讨论了动态规划、优先策略、分治策略、线性规划的分解原理、最佳二分树、密码学等29个问题，对算法和它的复杂性作了分析。本书可作为计算机系本科学生及研究生教材，对数学系师生和科研工作者可作为参考书。\r\n
\r\n

绪论 \r\n\r\n 第1章　动态规划 \r\n\r\n 1. 1 最短路径问题 \r\n\r\n 1. 2 最佳原理 \r\n\r\n 1. 3 流动推销员(或旅行商)问题 \r\n\r\n 1. 4 矩阵链乘问题 \r\n\r\n 1. 5 最长公共子序列 \r\n\r\n 1. 6 图的任意两点间的最短距离 \r\n\r\n 1. 7 整数规划问题 \r\n\r\n 1. 8 同顺序流水作业的任务安排问题 \r\n\r\n 1. 9　可靠性问题 \r\n\r\n 1. 10 设备更新问题 \r\n\r\n 习题 \r\n\r\n 第2章　优先策略 \r\n\r\n 2. 1 最短树的库鲁斯卡尔(Kruskal)算法 \r\n\r\n 2. 2 求最短树的普林(Prim)算法 \r\n\r\n 2. 3 求最短路径的戴克斯德斯(Dijkstra)算法 \r\n\r\n 2. 4 文件存储问题 \r\n\r\n 2. 5 有期限的任务安排问题 \r\n\r\n 习题 \r\n\r\n 第3章　分治策略 \r\n\r\n 3. 1 二分查找 \r\n\r\n 3. 2 整数乘法 \r\n\r\n 3. 3 矩阵乘积的斯德拉逊(Strassen)算法 \r\n\r\n 3. 4 矩阵乘积的维诺格拉德Winograd算法 \r\n\r\n 3. 5 布尔矩阵的乘法问题 \r\n\r\n 习题 \r\n\r\n 第4章 哈佛曼(Huffman)编码. FFT算法和数据压缩 \r\n\r\n 4. 1 哈佛曼(Huffman)编码 \r\n\r\n 4. 2 快速傅里叶变换(FFT) \r\n\r\n 4. 3 卷积及其应用 \r\n\r\n 4. 4 数论变换 \r\n\r\n 习题 \r\n\r\n 第5章 线性规划的分解原理 \r\n\r\n 5. 1 线性规划和单纯形法简介 \r\n\r\n 5. 2 丹捷-卧佛(Dantzig-Wolfe)分解算法 \r\n\r\n 习题 \r\n\r\n 第6章 最佳二分树 \r\n\r\n 6. 1 二分树 \r\n\r\n 6. 2 最佳二分树 \r\n\r\n 习题 \r\n\r\n 第7章 内存分类法之一：插入分类法. 塞尔(SheH)分类法 \r\n\r\n 7. 1 分类 \r\n\r\n 7. 2 分类的下界估计 \r\n\r\n 7. 3 二分插入分类法 \r\n\r\n 7. 4 塞尔(Shell)分类法 \r\n\r\n 习题 \r\n\r\n 第8章 内存分类法之二：递选分类法. 堆集分类 \r\n\r\n 8. 1 递选分类法 \r\n\r\n 8. 2 二分树递选分类法 \r\n\r\n 8. 3 堆集分类法 \r\n\r\n 习题 \r\n\r\n 第9章 内存分类法之三：下溢分类法. 快速分类法 \r\n\r\n 9. 1 下溢分类法 \r\n\r\n 9. 2 快速分类法 \r\n\r\n 习题 \r\n\r\n 第10章 内存分类法之四：归并分类法和基数分类法 \r\n\r\n 10. 1 归并分类法 \r\n\r\n 10. 2 福德-庄生(Ford-Johnson)归并插入分类法 \r\n\r\n 10. 3　基数分类法 \r\n\r\n 习题 \r\n\r\n 第11章 求第女个元素 \r\n\r\n 11. 1 求最小及第二小元素 \r\n\r\n 11. 2 求第k个元素 \r\n\r\n 习题 \r\n\r\n 第12章 外存分类法 \r\n\r\n 12. 1 外存归并分类法 \r\n\r\n 12. 2 置换选择段的构造 \r\n\r\n 12. 3 三条带的外存归并分类法 \r\n\r\n 12. 4 阶式归并法 \r\n\r\n 习题 \r\n\r\n 第13章 分类网络 \r\n\r\n 13. 1 分类网络举例 \r\n\r\n 13. 2 0-1原理 \r\n\r\n 13. 3 归并网络 \r\n\r\n 13. 4 巴特塞尔(Batcher)奇偶归并网络 \r\n\r\n 习题 \r\n\r\n 第14章 查找及均衡树 \r\n\r\n 14. 1 AVL树--关于高度均衡的二分树 \r\n\r\n 14. 2 关于高度均衡的二分树的插入和删除 \r\n\r\n 习题 \r\n\r\n 第15章 2-3树和2-3-4树 \r\n\r\n 15. 1 2-3树 \r\n\r\n 15. 2 2-3-4树 \r\n\r\n 15. 3 红黑树 \r\n\r\n 习题 \r\n\r\n 第16章 B-树 \r\n\r\n 16. 1 B-树概念 \r\n\r\n 16. 2 插入和删除 \r\n\r\n 习题 \r\n\r\n 第17章 哈希表 \r\n\r\n 17. 1 什么是哈希表 \r\n\r\n 17. 2 哈希函数的构造方法 \r\n\r\n 17. 3 解决冲突的方法 \r\n\r\n 17. 4 哈希算法的分析(线性探测法分析) \r\n\r\n 17. 5 二重哈希法 \r\n\r\n 习题 \r\n\r\n 第18章 DFS算法和BFS算法 \r\n\r\n 18. 1 概述 \r\n\r\n 18. 2 DFS算法 \r\n\r\n 18. 3 无向图的DFS算法 \r\n\r\n 18. 4 有向图的DFS算法 \r\n\r\n 18. 5 互连通块问题 \r\n\r\n 18. 6 强连通块问题 \r\n\r\n 18. 7 BFS算法 \r\n\r\n 习题 \r\n\r\n 第19章 a- 剪枝术和分支定界法 \r\n\r\n 19. 1 a- 剪枝术 \r\n\r\n 19. 2 分支定界法和流动推销员问题 \r\n\r\n 19. 3 同顺序加工任务安排问题 \r\n\r\n 习题 \r\n\r\n 第20章　整数规划 \r\n\r\n 20. 1 概述 \r\n\r\n 20. 2 0-1规划和它的DFS搜索(隐枚举)解法 \r\n\r\n 20. 3 分支定界法在解整数规划中的应用 \r\n\r\n 习题 \r\n\r\n 第21章 串匹配 \r\n\r\n 21. 1 概述 \r\n\r\n 21. 2 KMP克鲁斯-摩尼斯-普拉特(Knuth-Morris-Pratt)算法 \r\n\r\n 21. 3 BM坡艺尔-摩尔(Boyer-Moore)算法 \r\n\r\n 21. 4 RK拉宾-卡普(Rabin-Karp)算法 \r\n\r\n 习题 \r\n\r\n 第22章　概率算法 \r\n\r\n 22. 1 概率算法举例 \r\n\r\n 22. 2 随机数产生法 \r\n\r\n 22. 3 素数的概率判定算法 \r\n\r\n 习题 \r\n\r\n 第23章 并行算法 \r\n\r\n 23. 1 并行计算机和并行算法的基本概念 \r\n\r\n 23. 2 递推关系的并行计算 \r\n\r\n 23. 3 图的并行算法举例 \r\n\r\n 23. 4 矩阵乘积的并行计算 \r\n\r\n 23. 5 分布计算 \r\n\r\n 习题 \r\n\r\n 第24章 脉动阵列的并行处理 \r\n\r\n 24. 1 矩阵和向量乘法的并行处理 \r\n\r\n 24. 2 矩阵乘法的并行处理 \r\n\r\n 24. 3 带状矩阵的并行乘法 \r\n\r\n 习题 \r\n\r\n 第25章 计算几何 \r\n\r\n 25. 1 关于线段问题 \r\n\r\n 25. 2 求凸包问题 \r\n\r\n 习题 \r\n\r\n 第26章　NP完备理论 \r\n\r\n 26. 1 确定型图灵机 \r\n\r\n 26. 2 可满足性问题 \r\n\r\n 26. 3 非确定型图灵机与库克(Cook)定理 \r\n\r\n 26. 4 几个NP完备的例子 \r\n\r\n 26. 5 复杂度类 \r\n\r\n 习题 \r\n\r\n 第27章 近似算法 \r\n\r\n 27. 1 任务安排的近似算法 \r\n\r\n 27. 2 装箱问题的近似算法 \r\n\r\n 27. 3 流动推销员问题的近似算法 \r\n\r\n 27. 4 顶点覆盖问题的近似算法 \r\n\r\n 习题 \r\n\r\n 第28章 密码学简介 \r\n\r\n 28. 1 什么是密码? \r\n\r\n 28. 2 背包公钥密码 \r\n\r\n 28. 3 RSA公钥密码 \r\n\r\n 28. 4 数字签名 \r\n\r\n 28. 5 Hash算法 \r\n\r\n 习题 \r\n\r\n 第29章 LP问题的多项式算法 \r\n\r\n 29. 1 Klee和Minty举例 \r\n\r\n 29. 2 Xavu加(哈奇扬)算法 \r\n\r\n 29. 3 Karmarkar算法 \r\n\r\n 习题 \r\n
\r\n

有人说“计算机科学是一门研究算法的科学”. 不论这个说法是否全面, 算法无疑是计算机科学的重要组成部分. 它近来发展极其迅速, 说是异彩纷呈并不为过. “算法与算法复杂性分析”已是计算机专业本科生, 特别是研究生的一门必需掌握的内容.

与算法有关的还有一个大家熟悉的公式：

程序＝算法十数据结构

这说明算法的研究不单是数学问题, 还和数据结构密切相关. 这个观点在这里必须突出地强调, 必须强调的还有一点, 那就是“实践”, 只有通过动手实践才能掌握算法的实质. 正因为这个原因, 实例是本书的重要组成部分.

本书是在“组合数学(算法与分析)”下册的基础上改写而成. 第1章至第5章及第18章. 第19章由卢华明执笔, 第6章至第12章及第16章由黄连生完成. 没有他们的合作, 本书的出版可能还得拖相当一段时间. 作者深知书中存在不少缺点与错误, 还望读者不吝指教.

计算机科学组合学丛书前言

电子计算机的出现是20世纪的大事, 它改变了我们这个世界的面貌. 可以毫不夸张地说, 它的影响遍及所有的角落, 几乎无处不感觉到它的存在. 数学更不例外. 严格地说, 电子计算机本身就是近代数学的辉煌成就. 将计算机与数学割裂开来, 既不合理也不可能. 组合学也就是在计算机科学篷勃发展的刺激下而崛起的, 从而成为近若干年来员活跃的数学分支. 它研究的问题有的可追溯到欧拉和哈密尔顿等18世纪的数学家, 但它成为一新的分支还是近若干年的事. 它从与计算机科学相结合中获得了广阔的发展空间, 从而也为计算机科学奠定了理论基础.

什么是计算机科学呢?有的学者将它定义为研究算法的一门学科. 研究算法无疑是计算机科学的重要领域, 也是本丛书的核心内容, 贯穿始终. 组合学家在20世纪70年代初建立的算法复杂性“NP理论”, 至今仍然令无数计算机科学工作者与数学工作者为之折腰.

计算机科学里的组合学内容十分广泛. 本丛书涉及组合分析. 图论. 组合算法. 近代密码学. 编码理论及算法复杂性等七部分.

组合分析是算法的理论基础. 组合分析之与组合算法犹如数学分析之与计算数学. 众所周知, 前者是后者的理论根基.

图论原本是组合数学这个“家族”的主要成员, 只因它已成长壮大, 故自立门户独立出去.

算法复杂性的NP理论是近30年的一大成就. 研究表明对于一类叫做NPC类的困难问题, 至今都不存在有效算法, 但它们难度相当, 只要其中任何一个找到多项式解法, 则全体都获得解决, 或证明它们根本不存在有效办法. 不论是前者还是后者都还看不见露到海平面上的桅杆塔, 它吸引了众多的有志之士. 密码学是其中十分引人入胜的分支. 如若设计好的密码, 对它的破译等价于某一NPC类困难问题, 无疑这样的密码将是牢不可破的.

在计算机网络深入普及的信息时代, 信息本身就是时间, 就是财富. 信息的传输通过的是脆弱的公共信道, 信息储存于“不设防”的计算机系统中, 如何保护信息的安全使之不被窃取及不至于被篡改或破坏, 已成为当今被普遍关注的重大问题. 密码是有效而且可行的办法. 在计算机网络的刺激下, 近代密码学便在算法复杂性理论的基础上建立起来了. 密码作为一种技术, 自从人类有了战争, 不久便有了它. 但作为一门学科则是近20多年的事. 甚至于它已成为其它学科的基础. 密码也从此走出“军营”, 进入百姓家.

实际中的“优化”问题是大量的, 半个多世纪以来它曾经几度辉煌. 近来在计算机科学的影响下, 又出现了若干闪光点, 十分耀眼, 引人注目.

实际上密码也是一种编码. 如果说密码学研究的编码是保证通信的保密与安全, 则编码理论研究的是通信中如何纠错与检错. 计算机纠错码是既实用. 理论上又饶有趣味的分支.

本丛书是作者在清华大学计算机科学与技术系长期工作的总结. 它不是一部“长篇”记述, 而是互相关联又彼此相对独立, 因此难免有少量交叉. 它们涉及的面如此之广, 囿于作者的水平, 缺点和错误在所难免, 敬请读者不吝指正. 谢谢.