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

第1章 数学预备知识 1

1.1 集合 1

1.1.1 集合之间的关系 1

1.1.2 幂集 2

1.1.3 集合的运算 2

1.2 计数方法 3

1.2.1 加法法则及乘法法则 3

1.2.2 一一对应 3

1.2.3 排列 4

1.2.4 组合 6

1.3 母函数 9

1.3.1 母函数的性质及应用 9

1.3.2 指数型母函数 14

1.4 级数求和 16

1.4.1 由组合的实际意义产生的计数公式及级数求和公式 16

1.4.2 其它的一些常用求和公式 18

习题一 19

第2章 导引与基本数据结构 21

2.1 算法 21

2.1.1 算法的重要特性 21

2.1.2 算法学习的基本内容 22

2.2 分析算法 23

2.2.1 计算时间的渐近表示 24

2.2.2 常用的整数求和公式 27

2.2.3 作时空性能分布图 27

2.3 用SPARKS语言写算法 28

2.4 基本数据结构 33

2.4.1 栈和队列 34

2.4.2 树 37

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

2.4.4 图 48

习题二 50

第3章 递归算法 52

3.1 递归算法的实现机制 52

3.1.1 子程序的内部实现原理 52

3.1.2 递归过程的内部实现原理 54

3.2 递归转非递归 54

3.3 递归算法设计 57

3.4 递归关系式的计算 62

3.4.1 递归算法的时间复杂度分析 62

3.4.2 k阶线性齐次递归关系式的解法 64

3.4.3 线性常系数非齐次递归关系式的解法 68

习题三 70

第4章 分治法 71

4.1 一般方法 71

4.2 二分检索 72

4.2.1 二分检索算法 73

4.2.2 以比较为基础检索的时间下界 77

4.3 找最大和最小元素 78

4.4 归并分类 81

4.4.1 基本方法 81

4.4.2 改进的归并分类算法 84

4.4.3 以比较为基础分类的时间下界 86

4.5 快速分类 87

4.5.1 快速分类算法 87

4.5.2 快速分类分析 89

4.6 选择问题 91

4.6.1 选择问题算法 91

4.6.2 最坏情况时间是O（n）的选择算法 94

4.6.3 SELECT2的实现 96

4.7 斯特拉森矩阵乘法 97

习题四 99

5.1 一般方法 101

第5章 贪心方法 101

5.2 背包问题 102

5.3 带有限期的作业排序 104

5.3.1 带有限期的作业排序算法 104

5.3.2 一种更快的作业排序算法 107

5.4 最优归并模式 109

5.5 最小生成树 112

5.6 单源点最短路径 118

习题五 121

6.1 一般方法 124

第6章 动态规划 124

6.2 多段图 126

6.3 每对结点之间的最短路径 130

6.4 最优二分检索树 132

6.5 0/1背包问题 137

6.5.1 0/1背包问题的实例分析 137

6.5.2 DKP的实现 140

6.5.3 过程DKNAP的分析 142

6.6 可靠性设计 143

6.7 货郎担问题 146

6.8 流水线调度问题 148

习题六 151

7.1 一般方法 153

7.1.1 二元树周游 153

第7章 基本检索与周游方法 153

7.1.2 树周游 161

7.1.3 图的检索和周游 162

7.2 代码最优化 166

7.3 双连通分图和深度优先检索 176

7.4 与／或图 180

7.5 对策树 184

习题七 190

8.1.1 回溯的一般方法 193

第8章 回溯法 193

8.1 一般方法 193

8.1.2 效率估计 200

8.2 8-皇后问题 202

8.3 子集和数问题 204

8.4 图的着色 206

8.5 哈密顿环 208

8.6 背包问题 210

习题八 215

9.1 一般方法 217

第9章 分枝-限界法 217

9.1.1 LC-检索 218

9.1.2 15-谜问题——一个例子 219

9.1.3 LC-检索的抽象化控制 222

9.1.4 LC-检索的特性 223

9.1.5 分枝-限界算法 225

9.1.6 效率分析 229

9.2 0/1背包问题 230

9.2.1 LC分枝-限界求解 230

9.2.2 FIFO分枝-限界求解 234

9.3 货郎担问题 236

习题九 242

第10章 NP-难度和NP-完全的问题 243

10.1 基本概念 243

10.1.1 不确定的算法 243

10.1.2 NP-难度和NP-完全类 249

10.2 COOK定理 250

10.3 NP-难度的图问题 255

10.3.1 集团判定问题（CDP） 256

10.3.2 结点覆盖的判定问题 256

10.3.3 着色数判定问题（CN） 257

10.3.4 有向哈密顿环（DHC） 258

10.3.5 货郎担判定问题（TSP） 260

10.3.6 与／或图的判定问题（AOG） 260

10.4 NP-难度的调度问题 262

10.4.1 相同处理器调度 262

10.4.2 流水线调度 263

10.4.3 作业加工调度 264

10.5 NP-难度的代码生成问题 265

10.5.1 有公共子表达式的代码生成 265

10.5.2 并行赋值指令的实现 268

10.6 若干简化了的NP-难度问题 270

习题十 272

第11章 并行算法 274

11.1 并行计算机与并行计算模型 274

11.2 并行算法的基本概念 277

11.2.1 并行算法的复杂性度量 277

11.2.2 并行算法的性能评价 278

11.2.3 并行算法的设计 279

11.2.4 并行算法的描述 279

11.3 SIMD共享存储模型上的并行算法 280

11.3.1 广播算法 280

11.3.2 求和算法 281

11.3.3 并行归并分类算法 282

11.3.4 求图的连通分支的并行算法 284

11.4 SIMD互连网络模型上的并行算法 286

11.4.1 超立方模型上的求和算法 286

11.4.2 一维线性模型上的并行排序算法 288

11.4.3 树形模型上求最小值算法 289

11.4.4 二维网孔模型上的连通分支算法 290

11.5 MIMD共享存储模型上的并行算法 293

11.5.1 并行求和算法 293

11.5.2 矩阵乘法的并行算法 293

11.5.4 二次取中的并行选择算法 295

11.5.3 枚举分类算法 295

11.5.5 并行快速排序算法 297

11.5.6 求最小元的并行算法 299

11.5.7 求单源点最短路径的并行算法 300

11.6 MIMD异步通信模型上的并行算法 301

11.6.1 选择问题的并行算法 302

11.6.2 求极值问题的并行算法 303

11.6.3 网络生成树的并行算法 306

习题十 308

参考文献 309