《算法与复杂性》求取 ⇩

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

§3 多项式归约266

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

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

§6 复杂度类278

§7 近似算法280

§8 近代密码学简介291

*§9 Klee和Minty的举例297

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

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

习题323