算法设计、分析与应用教程PDF电子书下载

第1章 算法概述 1

1.1 引言 1

1.1.1 算法的描述 2

1.1.2 算法的特性 2

1.1.3 为什么学习算法 3

1.2 算法的设计 5

1.3 算法的分析 8

1.3.1 正确性分析 9

1.3.2 时空效率分析 10

1.3.3 时空特性分析 13

1.4 解决问题的一般步骤 13

1.5 小结 15

1.6 习题 16

第2章 递归与分治策略 17

2.1 递归算法 18

2.1.1 递归的概念 18

2.1.2 具有递归特性的问题 19

2.1.3 递归算法分析 22

2.2 分治策略 28

2.2.1 分治法的基本步骤 28

2.2.2 分治法的适用条件 29

2.2.3 二分搜索技术 29

2.2.4 棋盘覆盖问题 30

2.2.5 快速排序 33

2.2.6 大整数乘法 36

2.2.7 矩阵乘法 39

2.3 ACM经典问题解析 45

2.3.1 蜂窝问题（难度：★☆☆☆☆） 45

2.3.2 Humble Numbers（难度：★★☆☆☆） 46

2.3.3 Copying Books（难度：★★★☆☆） 48

2.3.4 Fractal（难度：★★★☆☆） 51

2.3.5 TOYS（难度：★★☆☆☆） 53

2.3.6 Cable master（难度：★★☆☆☆） 56

2.4 小结 58

2.5 习题 59

第3章 动态规划 62

3.1 何谓动态规划 63

3.1.1 动态规划的基本思想 63

3.1.2 设计动态规划法的步骤 63

3.1.3 动态规划问题的特征 63

3.1.4 动态规划与静态规划的关系 64

3.2 矩阵连乘积问题 65

3.2.1 分析最优解的结构 67

3.2.2 建立递归关系 68

3.2.3 计算最优值 69

3.2.4 构造最优解 71

3.3 动态规划算法的基本要素 72

3.3.1 最优子结构 72

3.3.2 重叠子问题 72

3.3.3 备忘录方法 73

3.4 最长公共子序列 75

3.4.1 最长公共子序列的结构 75

3.4.2 子问题的递归结构 76

3.4.3 计算最优值 76

3.4.4 构造最长公共子序列 78

3.5 最大子段和 78

3.5.1 递归关系分析 78

3.5.2 算法实现 79

3.6 0-1背包问题 80

3.6.1 递归关系分析 81

3.6.2 算法实现 81

3.7 ACM经典问题解析 83

3.7.1 数塔（难度：★★☆☆☆） 83

3.7.2 免费馅饼（难度：★★★☆☆） 84

3.7.3 Dividing（难度：★★★☆☆） 86

3.7.4 Win the Bonus（难度：★★★★☆） 88

3.7.5 Monkey and Banana（难度：★★★★☆） 90

3.7.6 Railroad（难度：★★★★☆） 93

3.8 小结 96

3.9 习题 97

第4章 贪心算法 101

4.1 活动安排问题 102

4.2 贪心算法的理论基础 104

4.2.1 贪心算法的基本思想 105

4.2.2 贪心算法的基本要素 105

4.2.3 贪心算法的基本步骤 106

4.3 删数问题 107

4.3.1 贪心策略选择 107

4.3.2 最优子结构 107

4.3.3 算法实现 107

4.3.4 复杂度分析 108

4.4 背包问题 109

4.4.1 最优子结构性质 109

4.4.2 贪心选择性质 110

4.4.3 算法实现 110

4.4.4 复杂度分析 112

4.5 最优装载问题 112

4.5.1 贪心选择性质 113

4.5.2 最优子结构性质 113

4.5.3 算法实现 113

4.5.4 复杂度分析 114

4.6 单源最短路径 115

4.6.1 算法基本思想 115

4.6.2 贪心选择性质 116

4.6.3 最优子结构性质 117

4.6.4 Dijkstra算法实现 117

4.6.5 复杂度分析 119

4.7 多处最优服务次序问题 120

4.7.1 贪心选择策略 120

4.7.2 贪心选择性质 120

4.7.3 最优子结构性质 120

4.7.4 算法实现 121

4.7.5 复杂度分析 122

4.8 ACM经典问题解析 122

4.8.1 Fat Mouse Trade（难度：★★☆☆☆） 122

4.8.2 Sorting the Photos（难度：★★★☆☆） 124

4.8.3 Moving Tables（难度：★★★☆☆） 126

4.8.4 Box of Bricks（难度：★★★★☆） 127

4.8.5 Wooden Sticks（难度：★★★★☆） 128

4.8.6 钓鱼问题（难度：★★★★☆） 130

4.8.7 树形DP问题（难度：★★★★☆） 133

4.8.8 Frogs'Neighborhood（难度：★★★☆☆） 135

4.9 小结 137

4.10 习题 138

第5章 回溯法 140

5.1 回溯法的基本思想 140

5.1.1 问题的解空间 141

5.1.2 搜索的解空间 143

5.1.3 回溯的基本步骤 144

5.1.4 回溯法实现 145

5.2 图的m着色问题 147

5.2.1 问题的解空间 147

5.2.2 约束条件 148

5.2.3 搜索解空间 148

5.2.4 代码实现 148

5.2.5 算法时间复杂度分析 150

5.3 n皇后问题 150

5.3.1 问题的解空间 151

5.3.2 约束条件 151

5.3.3 搜索过程 151

5.3.4 算法的时间复杂度分析 154

5.4 装载问题 154

5.4.1 问题的解空间 154

5.4.2 约束条件 154

5.4.3 限界条件 154

5.4.4 搜索过程 155

5.4.5 算法效率分析 157

5.5 0-1背包问题 157

5.5.1 问题的解空间 157

5.5.2 约束条件 157

5.5.3 限界条件 157

5.5.4 搜索过程 158

5.5.5 算法效率分析 160

5.6 旅行商问题 160

5.6.1 问题的解空间 161

5.6.2 约束条件 161

5.6.3 限界条件 161

5.6.4 搜索解空间 161

5.6.5 时间复杂度分析 163

5.7 批处理流水作业调度问题 163

5.7.1 问题的解空间 163

5.7.2 约束条件 164

5.7.3 限界条件 164

5.7.4 搜索过程 164

5.7.5 时间复杂度分析 166

5.8 ACM经典问题解析 166

5.8.1 Dreisam Equations（难度：★★★☆☆） 166

5.8.2 A Plug for UNIX（难度：★★★☆☆） 170

5.8.3 回文构词检测（Anagram Checker）（难度：★★☆☆☆） 174

5.8.4 Unshuffle（难度：★★★☆☆） 178

5.9 小结 181

5.10 习题 181

第6章 分支限界算法 183

6.1 分支限界法的基本理论 184

6.1.1 分支限界法的搜索策略 184

6.1.2 分支结点的选择 185

6.1.3 限界函数 185

6.2 单源最短路径问题 186

6.2.1 问题描述 186

6.2.2 算法描述与设计 186

6.2.3 算法实现 188

6.3 装载问题 190

6.3.1 问题描述 190

6.3.2 算法设计与实现 191

6.4 0-1背包问题 196

6.4.1 问题描述 196

6.4.2 算法描述与设计 196

6.4.3 算法实现 198

6.5 旅行商问题 202

6.5.1 问题描述 202

6.5.2 算法描述与设计 203

6.5.3 算法实现 204

6.7 ACM经典问题 209

6.7.1 布线问题（难度：★★★☆☆） 209

6.7.2 方格调整问题（难度：★★★☆☆） 212

6.7.3 旅行售货员问题（难度：★★★☆☆） 213

6.7.4 Grandpa's Estate（难度：★★★☆☆） 216

6.7.5 Find The Multiple（难度：★★★☆☆） 218

6.8 小结 220

6.9 习题 220

第7章 图的搜索算法 222

7.1 图的广度优先搜索遍历 224

7.1.1 算法描述与分析 224

7.1.2 程序实现 227

7.2 图的深度优先搜索遍历 232

7.2.1 算法描述与分析 232

7.2.2 程序实现 234

7.2.3 有向无圈图的拓扑排序 237

7.3 有向图的强连通分支 244

7.3.1 算法描述与分析 244

7.3.2 程序实现 247

7.4 无向图的双连通分支 250

7.4.1 算法描述与分析 250

7.4.2 程序实现 254

7.5 流网络与最大流问题 256

7.5.1 算法描述与分析 256

7.5.2 程序实现 263

7.6 ACM经典问题解析 265

7.6.1 Is It A Tree？（难度：★★★☆☆） 265

7.6.2 Stockbroker Grapevine（难度：★★★☆☆） 267

7.6.3 A Plug for UNIX（难度：★★★☆☆） 269

7.7 小结 273

7.8 习题 273

第8章 公钥加密算法 281

8.1 RSA公钥密码算法 283

8.1.1 算法描述 283

8.1.2 快速模幂算法 284

8.1.3 素数的生成 285

8.1.4 扩展欧几里得算法 288

8.2 因子分解算法 290

8.2.1 Pollard's p-l法 290

8.2.2 Pollard's rho法 291

8.3 离散对数密码算法 293

8.3.1 Diffie-Hellman密钥交换协议 293

8.3.2 ElGamal公钥密码算法 294

8.4 离散对数算法 295

8.4.1 小步／大步法 295

8.4.2 Pohlig-Hellman法 297

8.5 ACM的经典问题 299

8.5.1 简单的加密算法（难度：★★☆☆☆） 299

8.5.2 古代密码（难度：★★★☆☆） 300

8.6 小结 302

8.7 习题 303

第9章 P和NP问题浅析 304

9.1 决策问题和优化问题 305

9.2 何谓P类和NP类问题 306

9.2.1 P类问题 306

9.2.2 NP类问题 307

9.3 （确定性）图灵机 307

9.3.1 图灵机的定义 307

9.3.2 k带图灵机形式化描述 308

9.3.3 图灵机计算实例 308

9.4 非确定性图灵机 311

9.4.1 非确定性图灵机定义 311

9.4.2 非确定性图灵机形式化描述 312

9.4.3 非确定性图灵机计算实例 312

9.4.4 非确定性算法 313

9.4.5 NP类问题的定义 314

9.4.6 NP难（NP-hard） 315

9.5 NP完全问题P＊ 315

9.5.1 定义 316

9.5.2 多项式时间规约 316

9.5.3 库克定理 318

9.5.4 3-SAT问题 320

9.5.5 NP完全问题的近似算法 321

9.6 NP难问题的近似算法 332

9.6.1 旅行商问题的近似算法 333

9.6.2 背包问题的近似算法 339

9.7 小结 342

9.8 习题 343

附录A 求和 345

附录B 数论入门 352

参考文献 356