第1章预备知识1

1.1简介1

1.2什么是算法1

1.3程序符号4

1.4数学符号5

1.4.1命题演算5

1.4.2集合论6

1.4.3整数、实数和区间7

1.4.4函数和关系7

1.4.5量词8

1.4.6累加与累积9

1.4.7杂项10

1.5证明技巧1——反证法11

1.6证明技巧2——数学归纳法12

1.6.1数学归纳法的法则15

1.6.2不同颜色的马18

1.6.3一般化的数学归纳法19

1.6.4构造性归纳22

1.7一些回顾24

1.7.1极限24

1.7.2简单级数26

1.7.3基本组合30

1.7.4概率基础32

1.8习题38

1.9参考与深入阅读43

第2章基本算法45

2.1简介45

2.2问题和实例45

2.3算法的效率46

2.4平均和最坏情况分析48

2.5什么是基本运算？50

2.6为什么寻求效率？52

2.7一些例子53

2.7.1计算行列式的值53

2.7.2排序53

2.7.3大整数的乘法55

2.7.4计算最大公约数55

2.7.5计算斐波纳契序列56

2.7.6傅立叶变换57

2.8什么时候算法是确定的？58

2.9习题58

2.10参考与深入阅读61

第3章渐近记法62

3.1引言62

3.2同阶记法62

3.3其他渐近记法67

3.3.1Ω记法67

3.3.2Θ记法68

3.4条件渐近记法69

3.5具有多个参数的渐近记法71

3.6渐近记法的操作71

3.7习题72

3.8参考与深入阅读75

第4章算法分析76

4.1引言76

4.2分析控制结构76

4.2.1先后顺序76

4.2.2For循环76

4.2.3递归调用78

4.2.4while和repeat循环79

4.3使用标称80

4.4补充例子82

4.4.1选择排序82

4.4.2插入排序83

4.4.3欧几里德算法83

4.4.4汉诺塔85

4.4.5计算行列式的值86

4.5平均情况分析86

4.6分期分析87

4.6.1势函数88

4.6.2账户戏法90

4.7求解递归式90

4.7.1推测90

4.7.2齐次递归式92

4.7.3非齐次递归式96

4.7.4变量变换100

4.7.5范围转换105

4.7.6渐近递归式106

4.8习题107

4.9参考与深入阅读113

第5章一些数据结构114

5.1数组、栈和队列114

5.2记录和指针116

5.3链表117

5.4图118

5.5树119

5.6关联表124

5.7堆126

5.8二项堆132

5.9不相交集结构136

5.10习题141

5.11参考与深入阅读144

第6章贪婪算法146

6.1找零钱(1)146

6.2贪婪算法的一般特性147

6.3图：最小生成树148

6.3.1Kruskal算法150

6.3.2Prim算法152

6.4图：最短路径154

6.5背包问题(1)157

6.6日程安排160

6.6.1最小化时间160

6.6.2有期限的日程安排162

6.7习题168

6.8参考与深入阅读170

第7章分治算法171

7.1简介：大整数乘法171

7.2通用模板174

7.3二分搜索176

7.4排序178

7.4.1归并排序178

7.4.2快速排序180

7.5查找中值184

7.6矩阵乘法188

7.7求幂189

7.8综合：密码学简介192

7.9习题194

7.10参考与深入阅读200

第8章动态规划202

8.1两个简单的例子202

8.1.1计算二项式系数202

8.1.2系列赛203

8.2找零钱(2)205

8.3最优性原则207

8.4背包问题(2)208

8.5最短路径209

8.6链式矩阵乘法211

8.7使用递归214

8.8存储函数216

8.9习题217

8.10参考与深入阅读221

第9章搜索图223

9.1图和游戏：简介223

9.2遍历树228

9.2.1预处理228

9.3深度优先搜索：无向图230

9.3.1关节点232

9.4深度优先搜索：有向图233

9.4.1无环图：拓扑排序234

9.5广度优先搜索236

9.6回溯法239

9.6.1背包问题(3)240

9.6.2八皇后问题242

9.6.3通用模板244

9.7分支界限244

9.7.1分配任务问题245

9.7.2背包问题(4)248

9.7.3一般考虑248

9.8极小化原则248

9.9习题251

9.10参考与深入阅读256

第10章概率算法257

10.1简介257

10.2概率不意味着不确定258

10.3预期与平均时间259

10.4生成伪随机数259

10.5数值概率算法261

10.5.1Buffon的针261

10.5.2数值积分264

10.5.3概率计数265

10.6Monte Carlo算法267

10.6.1验证矩阵乘法267

10.6.2素数性测试269

10.6.3一个数可能是素数吗？272

10.6.4随机优势的扩大274

10.7Las Vegas算法276

10.7.1重访八皇后问题278

10.7.2概率选择与排序281

10.7.3通用散列282

10.7.4大整数分解因数284

10.8习题287

10.9参考与深入阅读293

第11章并行算法295

11.1并行计算的模型295

11.2一些基本的技术297

11.2.1计算完全二叉树297

11.2.2指针倍增298

11.3工作量与效率301

11.4图论的两个例子303

11.4.1最短路径303

11.4.2连通分量304

11.5表达式的并行求值308

11.6并行排序网络312

11.6.101原理313

11.6.2并行合并网络314

11.6.3改进的排序网络315

11.7并行排序316

11.7.1预备工作316

11.7.2核心思想317

11.7.3算法317

11.7.4细节概述318

11.8EREW和CRCW pram的一些注意点319

11.9分布式计算320

11.10习题321

11.11参考与深入阅读323

第12章计算复杂性324

12.1引言：一个简单的例子324

12.2信息理论论证325

12.2.1排序的复杂性327

12.2.2复杂性对算法设计的帮助330

12.3对手论证331

12.3.1查找数组的最大项332

12.3.2测试图的连通性333

12.3.3中值再考察333

12.4线性归约335

12.4.1形式定义337

12.4.2矩阵问题中的归约338

12.4.3最短路径问题中的归约342

12.5NP完全性介绍344

12.5.1P和NP类345

12.5.2多项式归约348

12.5.3NP完全性问题351

12.5.4一些NP完全性证明353

12.5.5NP难问题356

12.5.6非确定性算法357

12.6复杂性类纵览359

12.7习题362

12.8参考与深入阅读366

第13章启发式和近似算法369

13.1启发式算法369

13.1.1图着色369

13.1.2旅行商371

13.2近似算法372

13.2.1度量旅行商372

13.2.2背包问题（5）374

13.2.3装箱问题375

13.3NP难近似问题377

13.3.1绝对难近似问题378

13.3.2相对难近似问题379

13.4相同，惟一不同380

13.5近似模式383

13.5.1重访装箱问题383

13.5.2背包问题（6）384

13.6习题386

13.7参考与深入阅读389

参考文献390 2100433B

本书是关于算法导论的经典教材，书中包括大量例题解答与命题证明。本书是按照算法类型而不是按照应用类型对算法进行介绍，以其清晰的概念讲解赢得专家们的广泛赞誉。本书是优选教材。对于从事算法计算研究和工程应用的科研人员和工程技术人员，本书也是一本优秀的基础性读物。

CADCS基础算法(CADCS basic algorithm) 被控制理论算法引用的通用性计算方法.控制理论算法中，常常用到一些已知的算法，这些算法有独立意义，常常被不同的控制理论算法所引用，其本身绝大部分在CADCS中不具有控制理论算法的意义，这些算法被称之为CADCS基础算法.例如，矩阵运算、优化算法、多项式阵运算、统计算法等.这些算法的好坏直接影响控制理论算法的CADCS中的时间复杂性与空间复杂性，以及精度等数值质量，这些基础算法的研究都是计算数学的主要研究方向，计算数学可为控制理论提供好的基础算法.反过来，控制理论算法的研究也可给计算数学提出富有启发性的基础算法问题.类似控制理论算法，一个基础算法在什么条件下是好的，同样也是一个极富挑战性的问题.2100433B

旋转门算法除了平行四边形算法之外，还能用三角形算法来表示。

图遍历算法

图遍历算法是最基本的图算法之一，由指定节点开始，按照一定规则遍历图结构中所有的连通节点，包括宽度优先搜索(Breadth First Search,BFS)和深度优先搜索(Depth First Search, DFS)等核心算法。

作为最基本的图遍历算法，宽度优先搜索算法代表了图遍历算法的计算特性，具有非常重要的研究意义。一方面，BFS算法是最短路径、邻接查询、可达性查询等算法的实现基础，广泛应用于图分割、信念传播统计以及网络社区结构发现等领域;另一方面，BFS算法作为典型的数据密集型算法，体现了数据密集型应用对高性能计算系统的需求，广泛应用于大规模并行计算系统的数据处理能力评测，已经成为Parboil, Rodinia和Graph500等基准测试程序的核心算法。

在实际应用中，图的规模在不断增大，相应的，对图的存储和处理开销不断增加，有效地实现大规模并行BFS算法具有十分重要的意义。

稀疏线性方程组求解法

稀疏线性方程组的求解是对自然科学和社会科学中许多实际问题进行数值模拟时的关键技术之一。在高层建筑、桥梁、水坝、防洪堤的结构设计中，需对变形与应力情况进行模拟；在油气资源探测与分析、数值天气预报、飞行器的动力学分析中，需利用流体力学方程组进行模拟;在进行恒星大气分析与核爆实验时，常需利用辐射流体力学与粒子统计平衡等规律进行模拟。在对这些问题进行分析模拟时，通常利用偏微分方程建立数学模型。在对偏微分方程的离散求解过程中，稀疏线性方程组求解算法扮演着十分重要的角色。在许多不以偏微分方程建模的问题中，稀疏线性方程组求解同样发挥了重要的作用。在空中交通控制、电力线路中的最优电流问题中，需利用数学规划求解;在对采纳某项政策时在某给定条件下对国内、国际多个区域的相应经济指标进行预测时，需利用CGE模型进行分析；在可靠性分析、排队网络分析与计算机系统性能评估中，常利用具有大量状态的离散Markov链进行模拟。在这些问题的求解中，稀疏线性方程组的求解都占有重要位置，并且往往是整个计算过程中的性能瓶颈，稀疏线性方程组的高效求解是计算数学和工程应用中十分重要的课题之一。

解稀疏线性方程组的方法包括直接法(direct method)与迭代(iterative method)两类。直接法指在不考虑计算舍入误差的情况下，通过包括矩阵分解和三角方程组求解等有限步的操作求得方程组的精确解，因此又称精确法;迭代法指给定一个初始解向量，通过一定的计算构造一个向量列(一般通过逐次迭代得到一系列逼近精确值的近似解)，向量列的极限为方程组理论上的精确解。迭代法对存储空间的需求低，在求解高阶非病态稀疏线性方程组方面具有一定优势。然而，迭代法不适合求解病态问题，性能因问题而异，并且面临精度控制、收敛速度慢或不收敛等问题。与迭代法相比，直接法的通用性好，求解结果精度高，性能稳定。当矩阵分解结果能够被多次后续计算重用以及多右端项时，直接法的优势尤其明显。在有限元分析、模拟电路瞬态仿真等应用领域的商用软件均采用直接法求解器作为标准的稀疏线性方程组求解器。但直接法的缺点在于对存储资源要求较高，无法处理高阶稀疏矩阵。

一般来说，迭代法的求解速度高于直接法。但是，如果使用直接法时矩阵分解过程能够被很多后续计算重复使用，则后续的三角阵求解可以非常快速实现，此时直接法在性能上具有优势。典型例子是模拟电路瞬态仿真，这时需要多次以Newton-Raphson方法求解非线性方程，每一次求解均会在工作点附近展开为线性方程，而且所有线性方程的矩阵分解方式都是固定的，因此求解该类问题最好的方法是直接法。稀疏矩阵的矩阵分解在GPU上的实现是很困难的，主要难点在于现有算法的数据依赖性导致可利用的并行性不足。此外，矩阵元素的排列顺序对计算过程中间结果矩阵的非零元素个数有很大影响，同时矩阵分解后的非零元素的分布与原来矩阵可能很不相同。

迭代法的理论基础相对复杂，并且具有多种不同的具体算法，但其基本形式均为从一个猜测解出发，通过多次迭代逐渐收敛，当误差满足一定条件时迭代中止。共扼梯度法(CG)是迭代法的主流方法之一，特别适合于特征值为良态分布的对称正定方程组；其它迭代法包括Jacobi、逐次超松弛(SOR)、广义极小剩余(GMRES)、预条件共扼梯度(PCG)等。迭代法的核心算法是稀疏矩阵向量乘(SpMV)，因此实现SpMV的高效并行结构也是实现迭代法的基础。

直接法由高斯消元法发展向来，求解过程包括矩阵排序(matrix ordering)符号分解(symbolic factorization)、数值分解(numerical factorization)、三角方程组求解((triangular solves)四个步骤。其中，矩阵排序和符号分解属于预处理部分。矩阵排序通过启发算法置换稀疏矩阵的行列，试图在后续计算中维持矩阵的稀疏性或数值稳定性。符号分解则是预先对矩阵分解后的稀疏结构进行预测，预先分配存储空间并记录数据相关性。直接法的计算瓶颈在于数值分解部分和三角方程组求解部分，高效的直接法求解依赖于二者的高效实现。

对于一个稀疏线性方程组是选择直接法还是迭代法求解，一般有如下原则：对于低阶矩阵或大型带状矩阵所对应的线性方程组，用直接法求解；而对于大型(非带形)矩阵所对应的线性方程组，用迭代方法求解。实际上，选用何种方法还要看具体的应用背景，比如，对于线性规划和一些结构工程应用，只有直接法是切实可行的。对于精度要求很高的问题，还可以采用由直接法得到初始解再用迭代法进行迭代的方法求解，这种方法称为迭代精化法。