计算机算法导引 设计与分析PDF电子书下载

目录 1

绪论…………………………………………………………………………………………Ⅸ第1章 动态规划 1

1.1 最短路径问题 1

1.2 最佳原理 3

1.3 流动推销员（或旅行商）问题 11

1.4 矩阵链乘问题 14

1.5 最长公共子序列 16

1.6 图的任意两点间的最短距离 18

1.7 整数规划问题 20

1.8　同顺序流水作业的任务安排问题 25

1.9 可靠性问题 27

1.10 设备更新问题 29

习题 33

第2章 优先策略 36

2.1 最短树的Kruskal算法 36

2.2 求最短树的Prim算法 37

2.3 求最短路径的Dijkstra算法 38

2.4 文件存储问题 39

2.5 有期限的任务安排问题 41

习题 42

3.1 二分查找 45

第3章 分治策略 45

3.2 整数乘法 46

3.3 矩阵乘积的Strassen算法 47

3.4 矩阵乘积的Winograd算法 50

3.5 布尔矩阵的乘法问题 51

习题 53

第4章 Huffman编码、FFT算法和数据压缩 55

4.1　Huffman编码 55

4.2 快速傅里叶变换（FFT） 58

4.3 卷积及其应用 70

4.4 数论变换 72

习题 74

第5章 线性规划的分解原理 76

5.1 线性规划和单纯形法简介 76

5.2 Dantzig-Wolfe分解算法 81

习题 89

第6章 最佳二分树 91

6.1 二分树 91

6.2 最佳二分树 94

习题 100

7.2 分类的下界估计 101

第7章 内存分类法之一：插入分类法、Shell分类法 101

7.1 分类 101

7.3　二分插入分类法 104

7.4　Shell分类法 106

习题 108

第8章　内存分类法之二：递选分类法、堆集分类 111

8.1　递选分类法 111

8.2　二分树递选分类法 112

8.3　堆集分类法 113

习题 117

第9章　内存分类法之三：下溢分类法、快速分类法 118

9.1　下溢分类法 118

9.2　快速分类法 121

习题 125

第10章　内存分类法之四：归并分类法和基数分类法 127

10.1　归并分类法 127

10.2　Ford-Johnson归并插入分类法 129

10.3　基数分类法 133

习题 134

11.1 求最小及第二小元素 135

第11章 求第k个元素 135

11.2 求第k个元素 136

习题 138

第12章 外存分类法 139

12.1 外存归并分类法 139

12.2 置换选择段的构造 141

12.3 三条带的外存归并分类法 143

12.4 阶式归并法 147

习题 148

13.1 分类网络举例 149

第13章 分类网络 149

13.2 0-1原理 150

13.3 归并网络 153

13.4　Batcher奇偶归并网络 154

习题 156

第14章　查找及均衡树 157

14.1　AVL树——关于高度均衡的二分树 157

14.2　关于高度均衡的二分树的插入和删除 161

习题 164

第15章　2-3树和2-3-4树 165

15.1 2-3树 165

15.2　2-3-4树 167

15.3　红黑树 169

习题 170

第16章　B-树 171

16.1　B-树概念 171

16.2　插入和删除 172

习题 175

第17章　哈希表 176

17.1　什么是哈希表 176

17.2 哈希函数的构造方法 176

17.3 解决冲突的方法 177

17.4 哈希算法的分析（线性探测法分析） 180

17.5 二重哈希法 181

习题 182

第18章 DFS算法和BFS算法 184

18.1 概述 184

18.2 DFS算法 185

18.3 无向图的DFS算法 187

18.4 有向图的DFS算法 189

18.5 互连通块问题 192

18.6 强连通块问题 193

18.7 BFS算法 197

习题 . 198

第19章　α-β剪枝术和分支定界法 200

19.1　α-β剪枝术 200

19.2　分支定界法和流动推销员问题 200

19.3　同顺序加工任务安排问题 204

习题 207

第20章　整数规划 208

20.1　概述 208

20.2　0-1规划和它的DFS搜索（隐枚举）解法 210

20.3　分支定界法在解整数规划中的应用 218

习题 220

第21章　串匹配 221

21.1　概述 221

21.2 KMP（Knuth-Morris-Pratt）算法 222

21.3　BM（Boyer-Moore）算法 224

21.4　RK（Rabin-Karp）算法 225

习题 226

第22章　概率算法 228

22.1　概率算法举例 228

22.2　随机数产生法 231

22.3 素数的概率判定算法 232

习题 233

第23章 并行算法 234

23.1 并行计算机和并行算法的基本概念 234

23.2 递推关系的并行计算 237

23.3 图的并行算法举例 238

23.4 矩阵乘积的并行计算 242

23.5 分布计算 244

习题 245

24.1 矩阵和向量乘法的并行处理 246

第24章 脉动阵列的并行处理 246

24.2 矩阵乘法的并行处理 247

24.3 带状矩阵的并行乘法 249

习题 252

第25章 计算几何 253

25.1 关于线段问题 253

25.2 求凸包问题 257

习题 259

第26章 NP完备理论 260

26.1 确定型图灵机 260

26.2 可满足性问题 263

26.3 非确定型图灵机与Cook定理 265

26.4 几个NP完备的例子 269

26.5 复杂度类 277

习题 279

第27章 近似算法 281

27.1 任务安排的近似算法 281

27.2 装箱问题的近似算法 285

27.3 流动推销员问题的近似算法 287

27.4 顶点覆盖问题的近似算法 294

习题 295

28.1 什么是密码？ 297

第28章 密码学简介 297

28.2 背包公钥密码 300

28.3 RSA公钥密码 301

28.4 数字签名 303

28.5　Hash算法 303

习题 304

第29章　LP问题的多项式算法 305

29.1　Klee和Minty举例 305

29.2　Χачцян（哈奇扬）算法 308

29.3　Karmarkar算法 311

习题 321