算法设计与分析

第1章 绪论 1

1.1 算法在计算机科学体系中的地位 1

1.1.1 计算机理论模型和计算问题的分类 1

1.1.2 利用计算机求解问题 2

1.1.3 计算机科学的知识体系 3

1.1.4 算法是计算机科学的重要主题 4

1.1.5 算法设计与分析的意义 5

1.2 算法的概念 5

1.3 算法分析 7

1.3.1 算法正确性分析 7

1.3.2 算法复杂度分析 8

1.4 算法设计方法 10

习题 10

第2章 数学基础 12

2.1 复杂度函数的阶 12

2.1.1 函数阶的定义 12

2.1.2 函数阶的性质 15

2.2 标准符号和通用函数 15

2.2.1 flour函数和ceiling函数 15

2.2.2 求和 16

2.3 递归方程 19

2.3.1 常系数线性递归方程 19

2.3.2 非常系数线性递归方程 21

2.3.3 生成函数 22

2.3.4 分治算法递归方程 23

习题 27

第3章 分治算法 29

3.1 分治算法原理 29

3.2 大整数乘法 31

3.3 Strassen矩阵乘法 32

3.4 快速傅里叶变换 33

3.5 最邻近点问题 35

3.6 平面点集的凸包 38

3.6.1 求解凸包问题的蛮力算法 38

3.6.2 GrahamScan算法 41

3.6.3 凸包问题的分治算法 43

3.7 基于剪枝搜索方法的分治算法 44

3.7.1 剪枝搜索方法 44

3.7.2 线性时间选择算法 45

3.7.3 二元线性规划的线性时间算法 46

3.7.4 1－圆心问题的线性时间算法 51

习题 55

第4章 动态规划算法 57

4.1 动态规划原理 57

4.2 最长公共子序列 59

4.3 矩阵链乘法 63

4.4 0-1背包问题 66

4.5 最优二叉搜索树 69

4.6 评注 74

习题 75

第5章 贪心算法 77

5.1 贪心算法的基本原理 77

5.2 活动选择问题 79

5.3 哈夫曼编码问题 81

5.4 最小生成树问题 85

5.4.1 Kruskal算法 85

5.4.2 Prim算法 87

5.5 贪心算法的理论基础 90

5.5.1 拟阵 90

5.5.2 加权拟阵上的贪心算法 91

5.6 单位时间任务调度问题 93

习题 94

第6章 平摊分析 96

6.1 平摊分析方法 96

6.1.1 聚集方法 96

6.1.2 会计方法 98

6.1.3 势能方法 99

6.2 动态表性能的平摊分析 101

6.2.1 动态表及其操作 101

6.2.2 动态表的扩张 102

6.2.3 动态表扩张和收缩 104

6.3 斐波那契堆及其操作代价的平摊分析 106

6.3.1 斐波那契堆 106

6.3.2 斐波那契堆操作算法及其平摊代价 108

6.3.3 斐波那契堆最大度的上界 112

6.4 并查集及其操作代价的平摊分析 113

6.4.1 并查集及其基本性质 113

6.4.2 阿克曼函数及其逆函数 115

6.4.3 并查集上操作序列代价的平摊分析 116

习题 118

第7章 最大值最小值方法 120

7.1 网络流 120

7.1.1 最大流问题和最小割问题 120

7.1.2 Ford-Fulkerson算法 124

7.1.3 Edmonds-Karp算法 126

7.1.4 推送复标算法 128

7.1.5 复标前置算法 133

7.2 匹配算法 138

7.2.1 匹配与覆盖 138

7.2.2 最大二分匹配 140

7.2.3 一般图上的最大匹配 144

7.2.4 最大权值二分匹配 147

7.2.5 稳定二分匹配 150

习题 152

第8章 树的搜索策略 154

8.1 问题解空间的树表示 154

8.2 典型搜索策略 157

8.2.1 广度优先搜索 157

8.2.2 深度优先搜索 158

8.2.3 爬山法 159

8.2.4 最佳优先搜索 160

8.2.5 分支限界法 161

8.3 分支限界法的应用 163

8.3.1 用分支限界法求解人员分配问题 163

8.3.2 用分支限界法求解旅行商问题 166

8.3.3 用分支限界法求解0-1背包问题 169

8.4 A*算法及其应用 171

8.5 博弈树和α-β剪枝 174

8.5.1 博弈树及其评估 174

8.5.2 α-β剪枝 176

习题 178

第9章 随机算法 179

9.1 随机算法概述 179

9.2 数值随机算法 180

9.2.1 随机投点法 180

9.2. 2平均值方法 181

9.3 随机选择和拉斯维加斯算法 182

9.3.1 随机选择算法 182

9.3.2 拉斯维加斯算法 184

9.4 快速排序和舍伍德算法 185

9.4.1 快速排序算法描述 185

9.4.2 快速排序算法的性能分析 186

9.4.3 随机快速排序算法 187

9.4.4 舍伍德算法 188

9.5 素数测试和蒙特卡罗算法 189

9.5.1 素数测试随机算法 189

9.5.2 蒙特卡罗算法 190

9.6 最小割随机算法 190

习题 192

第10章 近似算法 194

10.1 近似算法的性能分析 194

10.2 基于组合优化的近似算法 195

10.2.1 顶点覆盖问题的近似算法 195

10.2.2 装箱问题的近似算法 196

10.2.3 最短并行调度问题的近似算法 197

10.2.4 旅行商问题的近似算法 198

10.2.5 子集和问题的完全多项式近似模式 199

10.3 基于贪心思想的近似算法 202

10.3.1 集合覆盖问题的近似算法 202

10.3.2 不相交路径问题的近似算法 204

10.4 基于局部搜索的近似算法 205

10.4.1 最大割问题的近似算法 205

10.4.2 设施定位问题的近似算法 207

10.5 基于动态规划的近似算法 210

10.5.1 0-1背包问题的完全多项式近似模式 210

10.5.2 装箱问题的多项式近似模式 212

10.6 基于线性规划的近似算法 215

10.6.1 线性规划及对偶定理 215

10.6.2 加权集合覆盖问题的线性规划表示 216

10.6.3 舍入法及随机舍入法 217

10.6.4 对偶拟合方法 219

10.6.5 原偶模式 220

10.7 不可近似性 222

10.7.1 鸿沟归约与不可近似性 222

10.7.2 PCP定理 224

10.7.3 MAX-3SAT问题的不可近似性 225

10.7.4 α,β－鸿沟归约与不可近似性 227

习题 228

第11章 在线算法 230

11.1 在线算法与竞争度分析 230

11.2 欧几里得最小生成树问题的在线算法 231

11.2.1 在线贪心算法 231

11.2.2 在线随机算法 232

11.3 凸包在线算法 235

11.4 线性链表在线更新算法 238

11.5 最短并行调度在线算法 240

习题 246

参考文献 248