算法导论（原书第3版）/计算机科学丛书

Thomas H. Cormen （托马斯•科尔曼） 达特茅斯学院计算机科学系教授、系主任。目前的研究兴趣包括：算法工程、并行计算、具有高延迟的加速计算。他分别于1993年、1986年获得麻省理工学院电子工程和计算机科学博士、硕士学位，师从Charles E. Leiserson教授。由于他在计算机教育领域的突出贡献，Cormen教授荣获2009年ACM杰出教员奖。
Charles E. Leiserson（查尔斯•雷瑟尔森）麻省理工学院计算机科学与电气工程系教授，Margaret MacVicar Faculty Fellow。他目前主持MIT超级计算技术研究组，并是MIT计算机科学和人工智能实验室计算理论研究组的成员。他的研究兴趣集中在并行和分布式计算的理论原理，尤其是与工程现实相关的技术研究。Leiserson教授拥有卡内基•梅隆大学计算机科学博士学位，还是ACM、IEEE和SIAM的会士。
Ronald L. Rivest （罗纳德•李维斯特）现任麻省理工学院电子工程和计算机科学系安德鲁与厄纳•维特尔比（Andrew and Erna Viterbi）教授。他是MIT计算机科学和人工智能实验室的成员，并领导着其中的信息安全和隐私中心。他1977年从斯坦福大学获得计算机博士学位，主要从事密码安全、计算机安全算法的研究。他和Adi Shamir和Len Adleman一起发明了RSA公钥算法，这个算法在信息安全中获得最大的突破，这一成果也使他和Shamir、Adleman一起得到2002年ACM图灵奖。他现在担任国家密码学会的负责人。
Clifford Stein（克利福德•斯坦）哥伦比亚大学计算机科学系和工业工程与运筹学系教授，他还是工业工程与运筹学系的系主任。在加入哥伦比亚大学大学之前，他在达特茅斯学院计算机科学系任教9年。Stein教授拥有MIT硕士和博士学位。他的研究兴趣包括：算法的设计与分析，组合优化、运筹学、网络算法、调度、算法工程和生物计算。

出版者的话
译者序
前言
第一部分基础知识
第1章算法在计算中的作用3
1.1算法3
1.2作为一种技术的算法6
思考题8
本章注记8
第2章算法基础9
2.1插入排序9
2.2分析算法13
2.3设计算法16
2.3.1分治法16
2.3.2分析分治算法20
思考题22
本章注记24
第3章函数的增长25
3.1渐近记号25
3.2标准记号与常用函数30
思考题35
本章注记36
第4章分治策略37
4.1最大子数组问题38
4.2矩阵乘法的Strassen算法43
4.3用代入法求解递归式47
4.4用递归树方法求解递归式50
4.5用主方法求解递归式53
4.6证明主定理55
4.6.1对b的幂证明主定理56
4.6.2向下取整和向上取整58
思考题60
本章注记62
第5章概率分析和随机算法65
5.1雇用问题65

5.2指示器随机变量67
5.3随机算法69
5.4概率分析和指示器随机变量的进一步使用73
5.4.1生日悖论73
5.4.2球与箱子75
5.4.3特征序列76
5.4.4在线雇用问题78
思考题79
本章注记80
第二部分排序和顺序统计量
第6章堆排序84
6.1堆84
6.2维护堆的性质85
6.3建堆87
6.4堆排序算法89
6.5优先队列90
思考题93
本章注记94
第7章快速排序95
7.1快速排序的描述95
7.2快速排序的性能97
7.3快速排序的随机化版本100
7.4快速排序分析101
7.4.1最坏情况分析101
7.4.2期望运行时间101
思考题103
本章注记106
第8章线性时间排序107
8.1排序算法的下界107
8.2计数排序108
8.3基数排序110
8.4桶排序112
思考题114
本章注记118
第9章中位数和顺序统计量119
9.1最小值和最大值119
9.2期望为线性时间的选择算法120
9.3最坏情况为线性时间的选择算法123
思考题125
本章注记126
第三部分数据结构
第10章基本数据结构129
10.1栈和队列129
10.2链表131
10.3指针和对象的实现134
10.4有根树的表示137
思考题139
本章注记141
第11章散列表142
11.1直接寻址表142
11.2散列表143
11.3散列函数147
11.3.1除法散列法147
11.3.2乘法散列法148
11.3.3全域散列法148
11.4开放寻址法151
11.5完全散列156
思考题158
本章注记160
第12章二叉搜索树161
12.1什么是二叉搜索树161
12.2查询二叉搜索树163
12.3插入和删除165
12.4随机构建二叉搜索树169
思考题171
本章注记173
第13章红黑树174
13.1红黑树的性质174
13.2旋转176
13.3插入178
13.4删除183
思考题187
本章注记191
第14章数据结构的扩张193
14.1动态顺序统计193
14.2如何扩张数据结构196
14.3区间树198
思考题202
本章注记202
第四部分高级设计和分析技术
第15章动态规划204
15.1钢条切割204
15.2矩阵链乘法210
15.3动态规划原理215
15.4最长公共子序列222
15.5最优二叉搜索树226
思考题231
本章注记236
第16章贪心算法237
16.1活动选择问题237
16.2贪心算法原理242
16.3赫夫曼编码245
16.4拟阵和贪心算法250
16.5用拟阵求解任务调度问题253
思考题255
本章注记257
第17章摊还分析258
17.1聚合分析258
17.2核算法261
17.3势能法262
17.4动态表264
17.4.1表扩张265
17.4.2表扩张和收缩267
思考题270
本章注记273
第五部分高级数据结构
第18章B树277
18.1B树的定义279
18.2B树上的基本操作281
18.3从B树中删除关键字286
思考题288
本章注记289
第19章斐波那契堆290
19.1斐波那契堆结构291
19.2可合并堆操作292
19.3关键字减值和删除一个结点298
19.4最大度数的界300
思考题302
本章注记305
第20章vanEmdeBoas树306
20.1基本方法306
20.2递归结构308
20.2.1原型vanEmdeBoas结构310
20.2.2原型vanEmdeBoas结构上的操作311
20.3vanEmdeBoas树及其操作314
20.3.1vanEmdeBoas树315
20.3.2vanEmdeBoas树的操作317
思考题322
本章注记323
第21章用于不相交集合的数据结构324
21.1不相交集合的操作324
21.2不相交集合的链表表示326
21.3不相交集合森林328
21.4带路径压缩的按秩合并的分析331
思考题336
本章注记337
第六部分图算法
第22章基本的图算法341
22.1图的表示341
22.2广度优先搜索343
22.3深度优先搜索349
22.4拓扑排序355
22.5强连通分量357
思考题360
本章注记361
第23章最小生成树362
23.1最小生成树的形成362
23.2Kruskal算法和Prim算法366
思考题370
本章注记373
第24章单源最短路径374
24.1Bellman-Ford算法379
24.2有向无环图中的单源最短路径问题381
24.3Dijkstra算法383
24.4差分约束和最短路径387
24.5最短路径性质的证明391
思考题395
本章注记398
第25章所有结点对的最短路径问题399
25.1最短路径和矩阵乘法400
25.2Floyd-Warshall算法404
25.3用于稀疏图的Johnson算法409
思考题412
本章注记412
第26章最大流414
26.1流网络414
26.2Ford\Fulkerson方法418
26.3最大二分匹配428
26.4推送重贴标签算法431
26.5前置重贴标签算法438
思考题446
本章注记449
第七部分算法问题选编
第27章多线程算法453
27.1动态多线程基础454
27.2多线程矩阵乘法465
27.3多线程归并排序468
思考题472
本章注记476
第28章矩阵运算478
28.1求解线性方程组478
28.2矩阵求逆486
28.3对称正定矩阵和最小二乘逼近489
思考题493
本章注记494
第29章线性规划495
29.1标准型和松弛型499
29.2将问题表达为线性规划504
29.3单纯形算法507
29.4对偶性516
29.5初始基本可行解520
思考题525
本章注记526
第30章多项式与快速傅里叶变换527
30.1多项式的表示528
30.2DFT与FFT531
30.3高效FFT实现536
思考题539
本章注记541
第31章数论算法543
31.1基础数论概念543
31.2最大公约数547
31.3模运算550
31.4求解模线性方程554
31.5中国余数定理556
31.6元素的幂558
31.7RSA公钥加密系统561
31.8素数的测试565
31.9整数的因子分解571
思考题574
本章注记576
第32章字符串匹配577
32.1朴素字符串匹配算法578
32.2Rabin\Karp算法580
32.3利用有限自动机进行字符串匹配583
32.4Knuth-Morris-Pratt算法588
思考题594
本章注记594
第33章计算几何学595
33.1线段的性质595
33.2确定任意一对线段是否相交599
33.3寻找凸包604
33.4寻找最近点对610
思考题613
本章注记615
第34章NP完全性616
34.1多项式时间619
34.2多项式时间的验证623
34.3NP完全性与可归约性626
34.4NP完全性的证明633
34.5NP完全问题638
34.5.1团问题638
34.5.2顶点覆盖问题640
34.5.3哈密顿回路问题641
34.5.4旅行商问题644
34.5.5子集和问题645
思考题647
本章注记649
第35章近似算法651
35.1顶点覆盖问题652
35.2旅行商问题654
35.2.1满足三角不等式的旅行商问题654
35.2.2一般旅行商问题656
35.3集合覆盖问题658
35.4随机化和线性规划661
35.5子集和问题663
思考题667
本章注记669
第八部分附录：数学基础知识
附录A求和672
A.1求和公式及其性质672
A.2确定求和时间的界674
思考题678
附录注记678
附录B集合等离散数学内容679
B.1集合679
B.2关系682
B.3函数683
B.4图685
B.5树687
B.5.1自由树688
B.5.2有根树和有序树689
B.5.3二叉树和位置树690
思考题691
附录注记692
附录C计数与概率693
C.1计数693
C.2概率696
C.3离散随机变量700
C.4几何分布与二项分布702
C.5二项分布的尾部705
思考题708
附录注记708
附录D矩阵709
D.1矩阵与矩阵运算709
D.2矩阵基本性质712
思考题714
附录注记715
参考文献716
索引732

显示更多