计算机算法基础 第2版PDF电子书下载

第一章 导引与基本数据结构 1

1.1 算法 1

1.2 分析算法 3

1.2.1 计算时间的渐近表示 4

1.2.2 常用的整数求和公式 6

1.2.3 作时空性能分布图 7

1.3 用SPARKS语言写算法 7

1.4 基本数据结构 13

1.4.1 栈和队列 13

1.4.2 树 16

1.4.3 集合的树表示和不相交集合的合并——树结构应用实例 21

1.4.4 图 27

1.5 递归和消去递归 29

1.5.1 递归 29

1.5.2 消去递归 31

习题一 34

2.1 一般方法 37

第二章 分治法 37

2.2 二分检索 38

2.2.1 二分检索算法 39

2.2.2 以比较为基础检索的时间下界 42

2.3 找最大和最小元素 43

2.4 归并分类 46

2.4.1 基本方法 46

2.4.2 改进的归并分类算法 49

2.4.3 以比较为基础分类的时间下界 52

2.5.1 快速分类算法 53

2.5 快速分类 53

2.5.2 快速分类分析 54

2.6 选择问题 57

2.6.1 选择问题算法 57

2.6.2 最坏情况时间是O(n)的选择算法 59

2.6.3 SELECT2的实现 62

2.7 斯特拉森矩阵乘法 63

习题二 65

3.1 一般方法 67

第三章 贪心方法 67

3.2 背包问题 68

3.3 带有限期的作业排序 70

3.3.1 带有限期的作业排序算法 71

3.3.2 一种更快的作业排序算法 73

3.4 最优归并模式 76

3.5 最小生成树 78

3.6 单源点最短路径 84

习题三 87

第四章 动态规划 90

4.1 一般方法 90

4.2 多段图 92

4.3 每对结点之间的最短路径 95

4.4 最优二分检索树 98

4.5 0/1背包问题 103

4.5.1 0/1背包问题的实例分析 103

4.5.2 DKP的实现 106

4.5.3 过程DKNAP的分析 108

4.6 可靠性设计 109

4.7 货郎担问题 111

4.8 流水线调度问题 113

习题四 116

第五章 基本检索与周游方法 118

5.1 一般方法 118

5.1.1 二元树周游 118

5.1.2 树周游 126

5.1.3 图的检索和周游 127

5.2 代码最优化 131

5.3 双连通分图和深度优先检索 142

5.4 与/或图 146

5.5 对策树 149

习题五 154

第六章 回溯法 158

6.1 一般方法 158

6.1.1 回溯的一般方法 158

6.1.2 效率估计 164

6.2 8-皇后问题 166

6.3 子集和数问题 168

6.4 图的着色 170

6.5 哈密顿环 173

6.6 背包问题 175

习题六 180

7.1 一般方法 183

7.1.1 LC-检索 183

第七章 分枝-限界法 183

7.1.2 15-谜问题——一个例子 185

7.1.3 LC-检索的抽象化控制 187

7.1.4 LC-检索的特性 189

7.1.5 分枝-限界算法 190

7.1.6 效率分析 194

7.2 0/1背包问题 195

7.2.1 LC分枝-限界求解 196

7.2.2 FIFO分枝-限界求解 200

7.3 货郎担问题 202

习题七 207

第八章 NP-难度和NP-完全的问题 209

8.1 基本概念 209

8.1.1 不确定的算法 209

8.1.2 NP-难度和NP-完全类 214

8.2 COOK定理 216

8.3.1 集团判定问题(CDP) 221

8.3.2 结点覆盖的判定问题 221

8.3 NP-难度的图问题 221

8.3.3 着色数判定问题(CN) 222

8.3.4 有向哈密顿环(DHC) 223

8.3.5 货郎担判定问题(TSP) 225

8.3.6 与/或图的判定问题(AOG) 225

8.4 NP-难度的调度问题 226

8.4.1 相同处理器调度 227

8.4.2 流水线调度 228

8.4.3 作业加工调度 229

8.5.1 有公共子表达式的代码生成 230

8.5 NP-难度的代码生成问题 230

8.5.2 并行赋值指令的实现 233

8.6 若干简化了的NP-难度问题 235

习题八 236

第九章 并行算法 239

9.1 并行计算机与并行计算模型 239

9.2 并行算法的基本概念 242

9.2.1 并行算法的复杂性度量 242

9.2.2 并行算法的性能评价 243

9.2.3 并行算法的设计 244

9.2.4 并行算法的描述 244

9.3 SIMD共享存储模型上的并行算法 245

9.3.1 广播算法 245

9.3.2 求和算法 246

9.3.3 并行归并分类算法 247

9.3.4 求图的连通分支的并行算法 249

9.4.1 超立方模型上的求和算法 251

9.4 SIMD互连网络模型上的并行算法 251

9.4.2 一维线性模型上的并行排序算法 252

9.4.3 树型模型上求最小值算法 254

9.4.4 二维网孔模型上的连通分支算法 255

9.5 MIMD共享存储模型上的并行算法 257

9.5.1 并行求和算法 257

9.5.2 矩阵乘法的并行算法 258

9.5.3 枚举分类算法 259

9.5.4 二次取中的并行选择算法 260

9.5.5 并行快速排序算法 261

9.5.6 求最小元的并行算法 263

9.5.7 求单源点最短路径的并行算法 264

9.6 MIMD异步通信模型上的并行算法 266

9.6.1 选择问题的并行算法 266

9.6.2 求极值问题的并行算法 268

9.6.3 网络生成树的并行算法 270

习题九 272

参考文献 273