《计算机算法导引 设计与分析》求取 ⇩

目录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