算法与复杂性PDF电子书下载

目 录 1

第一章绪论 1

§1 引言 1

§2 什么是算法 1

§3 算法的效率 4

§4 若干符号和它们的意义 5

习题 6

第二章搜索技术 9

§1 引言 9

§2 DFS搜索法 9

§3 图的算法 12

§4 BFS搜索法 22

§5 α-β剪枝术 23

§6分支定界法 24

§7 同顺序加工任务安排问题 27

*§8 搜索技术在整数规划中的应用 29

*§9 分支定界法在解整数规划问题中的应用 39

§10字符串匹配 40

§11网络流问题——Ford-Fulker-son算法 46

§12 Edmonds-Karp修正算法及其它 51

习题 56

第三章动态规划 59

§1 最短路径问题 59

§2 最佳原理 60

§3 旅行商问题的动态规划解法 65

§4 矩阵链乘积问题 67

§5 最长公共子序列 69

§6 图的两点间最短路径 71

§7 其它举例 72

习题 81

第四章优先策略和分治策略 83

§1 优先策略举例——最短树的Kruskal算法 83

§2 求最短树的Prim算法 84

§3 求距离的Dijkstra算法 87

§4 Huffman树 89

§5 安排问题 92

§6 分治策略的基本思想 95

§7 Strassen矩阵乘法 97

§8 三个前苏联人的算法及Wino-grad算法 100

§9 FFT运算 103

§10卷积 115

*§11数论变换 118

*§12线性规划的分解原理 120

习题 133

第五章分类与查找 136

§1 分类和它的下界估计 136

§2 二分树的性质 140

§3 递选分类法 144

§4 下溢分类法 145

§5 归并分类法 148

§6 快速分类法 152

§7堆集分类法 155

§8 Shell分类法 160

§9 Ford-Johnson分类法 163

§10基数分类法 167

§11外存分类法 168

§12置换选取段的构造 170

§13三条带的外存归并法 173

§14阶式归并法 177

§15分类网络 178

§16 0-1原理 179

§17归并网络 182

§18 Batcher奇偶归并网络 183

§19求第k个元素 185

习 题 188

第六章均衡树等若干数据结构 191

§1 最佳二分树 191

§2 AVL树之一：关于高度均衡的二分树 197

§3 2-3树和2-3-4树 205

§4 BR树 208

§5 B－树 212

§6 混列 219

§7双重混列 225

习题 226

它 227

§1 概率算法举例 227

第七章概率算法、并行算法及其 227

§2 素数生成的概率算法 232

§3 并行计算机和并行算法若干基本概念 234

§4 求第k个元素的并行算法 237

§5 递推关系的并行计算 238

§6 “脉动”阵列和网状计算装置 239

§7 图的并行算法 249

§8 求连通块的并行算法 252

§9 分布计算简介 254

§10计算几何之一——关于线段问题 255

§11 计算几何之二——凸包问题 258

习题 261

§1 引言 262

第八章 复杂性理论及若干课题的 262

新进展 262

§2 图灵机、P和NP 263

§3 多项式归约 266

§4 可满足性问题及Cook定理 267

§5 若干NP完全问题及其证明 271

§6 复杂度类 278

§7 近似算法 280

§8 近代密码学简介 291

*§9 Klee和Minty的举例 297

*§10哈奇扬（хачиян）算法 303

*§11卡玛卡（Karmarkar）算法 315

习题 323