算法导论（第二版影印版） (2008 年度畅销榜NO.70 )

本书自第一版出版以来，已经成为世界范围内广泛使用的大学教材和专业人员的标准参考手册。本书全面论述了算法的内容，从一定深度上涵盖了算法的诸多方面，同时其讲授和分析方法又兼顾了各个层次读者的接受能力。各章内容自成体系，可作为独立单元学习。所有算法都用英文和伪码描述，使具备初步编程经验的人也可读懂。全书讲解通俗易懂，且不失深度和数学上的严谨性。第二版增加了新的章节，如算法作用、概率分析与随机算法、线性编程等，几乎对第一版的各个部分都作了大量修订。

I Foundations
Introduction 3
l The Role of Algorithms in Computing 5
l.l Algorithms 5
l.2 Algorithms as a technology 10
2 Getting Started I5
2.l Insertion sort 15
2.2 Analyzing algorithms 21
2.3 Designing algorithms 27
3 Growth of Functions 41
3.l Asymptotic notation 41
3.2 Standard notations and common functions 51
4 Recurrences 62
4.l The substitution method 63
4.2 The recursion-tree method 67
4.3 The master method 73
4.4 Proof of the master theorem 76
5 Probabilistic Analysis and Randomized Algorithms
5.l The hiring problem 91
5.2 Indicator random variables 94
5.3 Randomized algorithms 99
5.4 Probabi1istic analysis and further uses of indicator 106
II Sorting and Order Statistics Introduction 123
6 Heapsort 127
6.l Heaps I27
6.2 Maintaining the heap property 130
6.3 Building a heap 132
6.4 The heapsort algorithm 135
6.5 Priority queues 138
7 Quicksort 145
7.l Description of quicksort 145
7.2 Performance ofquicksort 149
7.3 A randomized version of quicksort 153
7.4 Analysis ofquicksort 55
8 Sorting in Linear Time 165
8.l Lower bounds for sorting 165
8.2 Counting sort i68
8.3 Radix sort 170
8.4 Bucket sort 174
9 Medians and Order Statistics 183
9.1 Minimum and maximum 184
9.2 Selection in expected linear time 185
9.3 Selection in worst-case linear time 189
III Data Structures Introduction 197
10 Elementary Data Structures 200
l0.l Stacks and queues 200
l0.2 Linked lists 204
l0.3 Implementing pointers and objects 209
l0.4 Representing rooted trees 214
11 Hash Tables 221
ll.l Direct-address tables 222
11.2 Hash tables 224
ll.3 Hash functions 229
ll.4 Open addressing 237
ll.5 Perfect hashing 24S
l2 Binary Search Trees 253
l2.l What is a binary search tree? 2S3
l2.2 Querying a binary search tree 2S6
l2.3 Insertion and deletion 261
l2.4 Randoinly built binary search trees 265
13 Red-Black Thees 273
l3.l Properties of red-black trees 273
l3.2 Rotations 277
l3.3 Insertion 280
l3.4 Deletion 288
14 Augmenting Data Structures 302
l4.l Dynamic order statistics 302
l4.2 How to augment a data structure 308
l4.3 Interval trees 311
IV Advanced Desthe and Analysis Techniques Introduction 321
15 Dynamic Programming J2J
l5.l Assembly--line scheduling 324
l5.2 Matrix-chain multiplication 331
l5.3 Elements of dynamic programming 339
15.4 Longest common subsequence 350
l5.5 Optimal binary search trees 356
l6 Greedy Algorithms 370
l6.l An activity-selection problem 371
l6.2 Elements of the greedy strategy 379
l6.3 Huffman codes 385
l6.4 Theoretical foundations for greedy methods 393
16.5 A task-scheduling problem 399
17 Amortized Analysis 405
l7.1 Aggregate analysis 406
17.2 The accounting method 410
17.3 The potential method 412
l7.4 Dynamic tables 416
V Advanced Data Structures Introduction 431
18 B-Trees 434
18.l Definition of B--trees 438
l8.2 Basic operations on B-trees 44j
l8.3 Deleting a key from a B--tree 449
19 Binomial Heaps 455
l9.l Binomial trees and binomial heaps 457
19.2 Operations on binomial heaps 461
20 Fibonacci Heaps 476
20.l Structure of Fibonacci heaps 477
20.2 Mergeable-heap operations 479
20.3 Decreasing a key and deleting a node 489
20.4 Bounding the maximum degree 493
21 Data Structures for Disjoint Sets 498
2l.l Disjoint--set operations 498
2l.2 Linked-list representation of disjoint sets 501
2l.3 Disjoint--set forests 505
2l.4 Analysis of union by rank with path compression 50 VI Graph Algorithms Introduction 525
22 Elementary Graph Algorithms 527
22.l Representations of graphs 527
22.2 Breadth-first search 531
22.3 Depth-first search 540
22.4 Topological sort 549
22.5 Strongly connected components 552
23 Minimum Spanning Trees 561
23.l Growing a minimum spanning tree 562
23.2 The algorithms of Kruskal and Prim 567
24 Single-Source Shortest Paths 580
24.l The Bellman-Ford algorithm 588
24.2 Single-source shortest paths in directed acyclic graphs
24.3 Dijkstra's algorithm 595
24.4 Difference constraints and shortest paths 601
24.5 Proofs of shortest-paths properties 607
25 All-Pairs Shortest Paths 620
25.l Shortest paths and matrix multiplication 622
25.2 The Floyd-Warshall a1gorithm 629
25.3 Johnson's algorithm for sparse graphs 636
26 Maximum Flow d43
26.l Flow networks 644
26.2 The Ford-Fulkerson method 651
26.3 Maximum bipartite matching 664
26.4 Push--relabel algorithms 669
26.5 The relabel--to-front a1gorithm 68I VII Selected Topics Introduction 701
27 Sorting Networks 704
27.l Comparison networks 704
27.2 The zero-one principle 709
27.3 A bitonic sorting network 712
27.4 A merging network 716
27.5 A sorting network 719
28 Matrix Operations 725
28.l Properties of matrices 725
28.2 Strassen's algorithm for matrix multiplication 735
28.3 Solving systems of linear equations 742
28.4 Inverting matrices 7S5
28.5 Symmetric positive-definite matrices and least-squares approximation760
29 Linear Programming 770
29.1 Standard and slack forms 777
29.2 Formulating problems as linear programs 785
29.3 The simplex algorithm 790
29.4 Duality 804
29.5 The initial basic feasible solution 811
30 Polynomials and the FFT 822
30.l Representation of polynomials 824
30.2 The DFT and FFT 830
30.3 Efficient FFT implementations 839
31 Number-Theoretic Algorithms 849
3l.l E1ementary numbertheoretic notions 850
31.2 Greatest common divisor 856
3l.3 Modular arithmetic 862
3l.4 Solving modular linear equations 869
3l.5 The Chinese remainder theorem 873
3l.6 Powers of an element 876
3l.7 The RSA public-key cryptosystem 881
3l.8 Primality testing 887
3l.9 Integer factorization 896
32 String Matching 906
32.l The naive string-matching algorithm 909
32.2 The Rabin-Karp algorithm 911
32.3 String matching with finite automata 916
32.4 The Knuth-Morris-Pratt algorithm 923
33 Computational Geometry 933
33.l Line--segment properties 934
33.2 Determining whether any pair of segments intersects 940
33.3 Finding the convex hull 947
33.4 Finding the c1osest pair of points 957
34 NP-Completeness 966
34.1 Polynomial time 971
34.2 Polynomial-time verification 979
34.3 NP-completeness and reducibility 984
34.4 NP--completeness proofs 995
34.5 NP-complete problems 1003
35 Approximation Algorithms 1022
35.l The vertex-cover problem 1024
35.2 The traveling-salesman problem 1027
35.3 The set-covering problem 1033
35.4 Randomization and linear programming ]039
35.5 The subset-sum problem 1043
VH APPendir: Mathematical Background
Introduction 1057
A Summations 1058
A.l Summation formulas and properties 1058
A.2 Bounding summations 1062
B Sets, Etc. 1070
B.1 Sets 1070
B.2 Relations 1075
B.3 Functions 1077
B.4 Graphs 1080
B.5 Trees 1085
C Counting and Probability 1094
C.l Counting 1094
C.2 Probability 1100
C.3 Discrete random variables 1106
C.4 The geometric and binomial distributions 1112
C.5 The tails of the binomial distribution 1118
Bibliography 1127
Index 1145

20世纪末，以计算机和通信技术为代表的信息科学和技术对世界经济、科技、军事、教育和文化等产生了深刻影响。信息科学技术的迅速普及和应用，带动了世界范围信息产业的蓬勃发展，为许多国家带来了丰厚的回报。 进入2l世纪，尤其随着我国加入WTO，信息产业的国际竞争将更加激烈。我国信息产业虽然在20世纪末取得了迅猛发展，但与发达国家相比，甚至与印度、爱尔兰等国家相比，还有很大差距。国家信息化约发展速度和信息产业的国际竞争能力，最终都将取决于信息科学技术人才的质量和数量。引进国外信息科学和技术优秀教材，在有条件的学校推动开展英语授课或双语教学、是教育部为加快培养大批高质量的信息技术人才采取的一项重要举措。 为此，教育部要求由高等教育出版社首先开展信息科学和技术教材的引进试点工作。同时提出了两点要，一是要高水平，二是要低价格。在高等教育出版社和信息科学技术引进教材专家组的努力下，经过比较短的间，第一批引进的20多种教材已经陆续出版。这套教材出版后受到了广泛的好评，其中有不少是世界信息科学技术领域著名专家、教授的经典之作和反映信息科学技术最新进展的优秀作品，代表了目前世界信息科学技术育的一流水平，而且价格也是最优惠的，与国内同类自编教材相当。这项教材引进工作是在教育部高等教育司和高教社的共同组织下，由国内信息科学技术领域的专家、教授广泛参与，在对大量国外教材进行多次遴选的基础上，参考了国内和国外著名大学相关专业的课程设置进行系统引进的。其中，JohnWiley公司出版的贝尔实验室信息科学研究中心副总裁Silberschatz教授的经典著作《操作系统概念》，是我们经过反复谈判，做了很多努力才得以引进的。William Stallings先生曾编写了在美国深受欢迎的信息科学技术系列教材，其中有多种教材获得过美国教材和学术著作者协会颁发的计算机科学与工程教材奖，这批引进教材中就有他的两本著作。留美中国学者Jiawei Han先生的《数据挖掘》是该领域中具有里程碑意义的著作。由达特茅斯学院Thomas Cormen和麻省理工学院、哥伦比亚大学的几位学者共同编著的经典著作《算法导论》，在经历了11年的锤炼之后于2001年出版了第二版。目前任教于美国Massachusetts大学的James Kurose教授，曾在美国三所高校先后10次获得杰出教师或杰出教学奖，由他主编的《计算机网络》出版后，以其体系新颖、内容先进而倍受欢迎。在努力降低引进教材售价方面，高等教育出版社做了大量和细致的工作。这套引进的教材体现了权威性、系统性、先进性和经济性等特点。 教育部也希望国内和国外的出版商积极参与此项工作，共同促进中国信息技术教育和信息产业的发展。我们在与外商的谈判工作中，不仅要坚定不移地引进国外最优秀的教材，而且还要千方百计地将版权转让费降下来，要让引进教材的价格与国内自编教材相当，让广大教师和学生负担得起。中国的教育市场巨大，外国出版公司和国内出版社要通过扩大发行数量取得效益。 在引进教材的同时，我们还应做好消化吸收，注意学习国外先进的教学思想教学方法，提高自编教材的水平，使我们的教学和教材在内容体系上，在理论与实践的结合上，在培养学生的动手能力上能有较大的突破和创新。 目前，教育部正在全国35所高校推动示范性软件学院的建设和实施，这也是加快培养信息科学技术人才的重要举措之一。示范性软件学院要立足于培养具有国际竞争力的实用性软件人才，与国外知名高校或著名企业合作办学，以国内外著名IT企业为实践教学基地，聘请国内外知名教授和软件专家授课，还要率先使用引进教材开展教学。 我们希望通过这些举措，能在较短的时间，为我国培养一大批高质量的信息技术人才，提高我国软件人才的国际竞争力，促进我国信息产业的快速发展，加快推动国家信息化进程，进而带动整个国民经济的跨越式发展。