绪论Ⅸ

第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章分治策略45

31二分查找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章内存分类法之一： 插入分类法、塞尔(Shell)分类法101

71分类101

72分类的下界估计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章求第k个元素135

111求最小及第二小元素135

112求第k个元素136

习题138

第12章外存分类法139

121外存归并分类法139

122置换选择段的构造141

123三条带的外存归并分类法143

124阶式归并法147

习题148

第13章分类网络149

131分类网络举例149

1320\|1原理150

133归并网络153

134巴特塞尔(Batcher)奇偶归并网络154

习题156

第14章查找及均衡树157

141AVL树——关于高度均衡的二分树157

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

习题164

第15章2\|3树和2\|3\|4树165

1512\|3树165

1522\|3\|4树167

153红黑树169

习题170

第16章B\|树171

161B\|树概念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2DFS算法185

183无向图的DFS算法187

184有向图的DFS算法189

185互连通块问题192

186强连通块问题193

187BFS算法197

习题198

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

191α\|β剪枝术200

192分支定界法和流动推销员问题200

193同顺序加工任务安排问题204

习题207

第20章整数规划208

201概述208

2020\|1规划和它的DFS搜索(隐枚举)解法210

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

习题220

第21章串匹配221

211概述221

212KMP克鲁斯摩克斯普拉德(Knuth\|Morris\|Pratt)算法222

213BM坡艺尔摩尔(Boyer\|Moore)算法224

214RK拉宾卡普(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章脉动阵列的并行处理246

241矩阵和向量乘法的并行处理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章密码学简介297

281什么是密码?297

282背包公钥密码300

283RSA公钥密码301

284数字签名303

285Hash算法303

习题304

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

291Klee和Minty举例305

292Xачｕян(哈奇扬)算法308

293Karmarkar算法311

习题321