算法设计、分析与应用教程

内容概要

李文书，教授，工学博士，现任浙江理工大学信息学院，智能检测与系统实验室主任，硕士生导师。IEEE (1-1163129461)、中国计算机学会（E200016385M）会员和杭州市计算机学会会员；151第三层次培养人才。

书籍目录

第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.60—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.50—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.40—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—1法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.43—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

作者简介

《算法设计、分析与应用教程》通过设计、分析ACM库的经典问题，把理论与实践结合。各章遵循从一个例子或故事中引出本章知识点，简述相关理论，分析经典问题及算法实现。主要包括算法概述、递归与分治策略、动态规划、贪心算法、回溯算法、分支限界算法、图的搜索算法、加密算法与安全机制、P和NP问题等内容。有故事、有理论、有公式、有实践。所有算法实现结果都经参加ACM的队员验证。本书适合高样计算机专业以及相关专业做为教材使用，也可供编程爱好者参考使用。

 算法设计、分析与应用教程下载 更多精彩书评