





定价:21元
印次:1-10
ISBN:9787302022770
出版日期:1899.12.30
印刷日期:2004.11.11
图书责编:张民
图书分类:教材
算法无疑是计算机科学的重要组成部分,近年来发展极其迅速。“算法与算法复杂性分析”已是计算机专业本科生,特别是研究生的一门必须掌握的内容。 一个大家熟悉的公式:程序=算法+数据结构,这说明算法的研究不单是数学问题,和数据结构密切相关,这是必须强调的,此外还需明确,只有通过实践才能掌握算法的实质。 本书是在原《组合数学(算法与分析)》下册的基础上改写而成的。书中的内容与结构都作了极大的改变。 本书共分29章讨论了29个问题,前6章为:动态规划、优先策略、分治策略、哈佛曼编码、线性规划的分解原理、最佳二分树。第7~10章为内存分类法。第11章为求第K个元素。第12、13章为外存分类法和分类网络。第14~16章为查找及树。第17章为哈希表。第18章为DFS与BFS 算法。第19章为α-β剪技术和分支定界法。第20章为整数规划。第21~27章分别为串匹配、概率算法、并行算法、脉动阵列的并行处理、计算几何、NP完备理论、近似算法。第28章为密码学简介。第29章为LP问题的多项式算法,对算法和它的复杂性作了分析。 本书可作为计算机系本科学生及研究生教材,对数学系师生和科研工作者可作为参考书。
有人说“计算机科学是一门研究算法的科学”。不论这个说法是否全面,算法无疑是计算机科学的重要组成部分。它近来发展极其迅速,说是异彩纷呈并不为过。“算法与算法复杂性分析”已是计算机专业本科生,特别是研究生的一门必需掌握的内容。 与算法有关的还有一个大家熟悉的公式: 程序=算法+数据结构 这说明算法的研究不单是数学问题,还和数据结构密切相关。这个观点在这里必须突出地强调,必须强调的还有一点,那就是“实践”,只有通过动手实践才能掌握算法的实质。正因为这个原因,实例是本书的重要组成部分。 本书是在“组合数学(算法与分析)”下册的基础上改写而成。第1章至第5章及第18章、第19章由卢华明执笔,第6章至第12章及第16章由黄连生完成。没有他们的合作,本书的出版可能还得拖相当一段时间。作者深知书中存在不少缺点与错误,还望读者不吝指教。
第1章动态规划1
11最短路径问题1
12最佳原理3
13流动推销员(或旅行商)问题11
14矩阵链乘问题14
15最长公共子序列16
16图的任意两点间的最短距离18
17整数规划问题20
18同顺序流水作业的任务安排问题25
19可靠性问题27
110设备更新问题29
习题33
第2章优先策略36
21最短树的库鲁斯卡尔Kruskal算法36
22求最短树的普林Prim算法37
23求最短路径的戴克斯德斯Dijkstra算法38
24文件存储问题39
25有期限的任务安排问题41
习题42
第3章分治策略45
31二分查找45
32整数乘法46
33矩阵乘积的斯德拉逊(Strassen)算法47
34矩阵乘积的维诺格拉德Winograd算法50
35布尔矩阵的乘法问题51
习题53
第4章哈佛曼(Huffman)编码、FFT算法和数据压缩55
41哈佛曼(Huffman)编码55
42快速傅里叶变换(FFT)58
43卷积及其应用70
44数论变换72
习题74
第5章线性规划的分解原理76
51线性规划和单纯形法简介76
52丹捷卧佛(Dantzig\|Wolfe)分解算法81
习题89
第6章最佳二分树91
61二分树91
62最佳二分树94
习题100
第7章内存分类法之一: 插入分类法、塞尔(Shell)分类法101
71分类101
72分类的下界估计101
73二分插入分类法10...