算法设计与分析 （屈婉玲、刘田、张立昂、王捍贫编著书籍）

简介

全书共10章，主要内容包括基础知识、分治策略、动态规划、贪心法、回溯与分支限界、算法分析与问题的计算复杂度、NP完全性、近似算法等。

内容简介

本教材为计算机科学技术专业核心课程“算法设计与分析”教材。全书以算法设计技术和分析方法为主线来组织各知识单元，主要内容包括基础知识、分治策略、动态规划、贪心法、回溯与分支限界、算法分析与问题的计算复杂度、NP完全性、近似算法、随机算法、处理难解问题的策略等。书中突出对问题本身的分析和求解方法的阐述，从问题建模、算法设计与分析、改进措施等方面给出适当的建议，同时也简要介绍了计算复杂性理论的核心内容和处理难解问题的一些新技术。本书有配套的学习指导与习题解析用书以及PPT电子教案。本书可作为大学计算机科学与技术、软件工程、信息安全、信息与计算机科学等专业本科生和研究生教学用书，也可以作为从事实际问题求解的算法设计与分析工作的参考书。

图书目录

目录CONTENTS第1章基础知识1

1.1有关算法的基本概念1

1.2算法的伪码描述5

1.3算法的数学基础6

1.3.1函数的渐近的界6

1.3.2求和的方法10

1.3.3递推方程求解方法12

习题121

第2章分治策略25

2.1分治策略的基本思想25

2.1.1两个熟悉的例子25

2.1.2分治算法的一般性描述26

2.2分治算法的分析技术26

2.3改进分治算法的途径30

2.3.1通过代数变换减少子问题个数30

2.3.2利用预处理减少递归内部的计算量33

2.4典型实例36

2.4.1快速排序算法36

2.4.2选择问题39

2.4.3n-1次多项式在全体2n次方根上的求值43

习题246

第3章动态规划51

3.1动态规划的设计思想51

3.1.1多起点、多终点的最短路径问题51

3.1.2使用动态规划技术的必要条件53

3.2动态规划算法的设计要素54

3.2.1子问题的划分和递推方程55

3.2.2动态规划算法的递归实现56

3.2.3动态规划算法的迭代实现57

3.2.4一个简单实例的计算过程58

3.3动态规划算法的典型应用59

3.3.1投资问题59

3.3.2背包问题61

3.3.3最长公共子序列LCS64

3.3.4图像压缩67

3.3.5最大子段和71

3.3.6最优二分检索树74

3.3.7生物信息学中的动态规划算法78

习题381

目录算法设计与分析第4章贪心法85

4.1贪心法的设计思想85

4.2关于贪心法的正确性证明88

4.3对贪心法得不到最优解情况的处理92

4.4贪心法的典型应用96

4.4.1最优前缀码96

4.4.2最小生成树101

4.4.3单源最短路径106

习题4108

第5章回溯与分支限界112

5.1回溯算法的基本思想和适用条件112

5.1.1几个典型的例子112

5.1.2回溯算法的适用条件116

5.2回溯算法的设计步骤117

5.2.1回溯算法的递归实现和迭代实现117

5.2.2几个典型的例子118

5.3回溯算法的平均效率和改进途径120

5.4分支限界122

5.4.1背包问题123

5.4.2最大团问题125

5.4.3货郎问题125

5.4.4圆排列问题127

5.4.5连续邮资问题129

习题5130

第6章算法分析与问题的计算复杂度132

6.1平凡下界133

6.2直接计数求解该问题所需要的最少运算134

6.3决策树135

6.4检索算法的时间复杂度分析136

6.5排序算法的时间复杂度分析138

6.5.1冒泡排序算法138

6.5.2堆排序算法139

6.5.3排序算法的决策树与算法类时间复杂度的下界144

6.6选择算法的时间复杂度分析146

6.6.1找最大和最小问题147

6.6.2找第二大问题148

6.6.3找中位数的问题150

6.7通过归约确认问题计算复杂度的下界152

习题6153

第7章NP完全性155

7.1P类与NP类155

7.1.1易解的问题与难解的问题155

7.1.2判定问题157

7.1.3NP类159

7.2多项式时间变换与NP完全性160

7.2.1多项式时间变换160

7.2.2NP完全性162

7.2.3Cook-Levin定理--第一个NP完全问题163

7.3几个NP完全问题163

7.3.1最大可满足性与三元可满足性163

7.3.2顶点覆盖、团与独立集165

7.3.3哈密顿回路与货郎问题167

7.3.4恰好覆盖169

7.3.5子集和、背包、装箱与双机调度171

习题7174

第8章近似算法176

8.1近似算法及其近似比176

8.2多机调度问题177

8.2.1贪心的近似算法177

8.2.2改进的贪心近似算法178

8.3货郎问题179

8.3.1最邻近法179

8.3.2最小生成树法180

8.3.3最小权匹配法181

8.4背包问题182

8.4.1一个简单的贪心算法182

8.4.2多项式时间近似方案182

8.4.3伪多项式时间算法与完全多项式时间近似方案183

习题8185

第9章随机算法187

9.1概率论预备知识187

9.2对随机快速排序算法的分析189

9.3随机算法的分类及其局限性191

9.3.1拉斯维加斯型随机算法191

9.3.2蒙特卡洛型随机算法191

9.3.3随机算法的局限性192

9.4素数检验和多项式恒等检验193

9.4.1素数检验193

9.4.2多项式恒等检验194

9.5随机游动算法195

9.5.1有限马氏链及其表示195

9.5.2求解二元布尔可满足性问题的随机游动算法196

习题9197

第10章处理难解问题的策略198

10.1对问题施加限制198

10.1.1二元可满足性问题199

10.1.2霍恩公式可满足性问题200

10.2固定参数算法201

10.3改进指数时间算法203

10.4启发式方法205

10.5平均情形的复杂性206

10.6难解算例生成208

10.6.1相变现象与难解性208

10.6.2隐藏解的难解算例210

10.7基于统计物理的消息传递算法211

10.7.1消息传递算法与回溯法、局部搜索算法的比较211

10.7.2基于统计物理的消息传递算法212

10.8量子算法简介213

10.8.1量子比特213

10.8.2正交测量214

10.8.3量子门215

10.8.4一个量子算法216

习题10218

成书过程

修改情况

该教材是作者在多年从事算法设计分析及计算复杂性理论的教学和研究的基础上编写而成。

该教材的第1~4章由屈婉玲完成，第5~6章由王捍贫完成，第7~8章由张立昂完成，第9~10章由刘田完成。

在编写过程中，作者参考了中国国内外多种版本的算法设计与分析以及计算复杂性方面的教材、论文和专著，从中吸取了一些好的思路和素材；李晓明教授审阅了初稿并提出了修改意见。

出版工作

2011年5月1日，该教材由清华大学出版社出版。

教学资源

• 配套教材

该教材有配套的学习指导与习题解析用书——《算法设计与分析习题解答与学习指导》。

• 课程资源

该教材提供PPT电子教案。

教学特色

该教材的主要特点是：

1. 该教材没有过多地关注实现细节，算法描述采用伪码，突出对问题本身的分析和求解方法的阐述，从问题建模、算法设计与分析、改进措施等方面给出了建议，为从事实际问题的算法设计与分析工作在理论上提供思路和方法；

2. 该教材介绍了一些关于问题复杂度的分析方法；

3. 该教材对计算复杂性理论的核心内容和针对难解问题的处理策略加以简单的介绍；

4. 该教材的素材来自多年的教学积淀，先引入基本概念和数学基础知识，然后进入算法设计与分析的核心内容。

作者简介

屈婉玲，北京大学信息科学技术学院教授、博士生导师，长期从事离散数学、算法分析和计算复杂性等方向的教学和研究工作。曾获得北京市教学成果奖一等奖，被评为北京大学十佳教师和北京市优秀教师。

刘田，博士，北京大学信息科学技术学院副教授、中国电子学会电路与系统分会图论与系统优化专委会副理事长、中国计算机学会理论计算机科学专委会委员，主要从事算法分析与计算复杂度方面的研究和教学工作。

张立昂，北京大学信息科学技术学院教授、博士生导师，一直从事数学和理论计算机科学的教学与研究工作，主要研究方向是计算复杂性理论和算法设计与分析，曾获得北京市教学成果奖一等奖和教育部科技进步二等奖。

王捍贫，博士，北京大学信息科学技术学院教授、博士生导师、软件研究所副所长、中国人工智能学会离散智能计算专委会主任，长期从事离散数学、形式化方法及算法设计与分析的教学和研究工作，曾获得北京市教学成果奖一等奖。