第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