第1页 / 共473页
第2页 / 共473页
第3页 / 共473页
第4页 / 共473页
第5页 / 共473页
第6页 / 共473页
第7页 / 共473页
第8页 / 共473页
The Design and Analysis of Computer Algorithms.pdf
PREFACE
CONTENTS
1 MODELS OF COMPUTATION
1.1 ALGORITHMS AND THEIR COMPLEXITY
1.2 RANOOM ACCESS MACHINES
1.3 COMPUTATIONAL COMPLEXITY OF RAM PROGRAMS
1.4 A STORED PROGRAM MODEL
1.5 ABSTRACTIONS OF THE RAM
I. Straight-Line Programs
II. Bitwise Computations
III. Bit Vector Operations
IV. Decision Trees
1.6 A PRIMITIVE MODEL OF COMPUTATION: THE TURING MACHINE
1.7 RELATIONSHIP BETWEEN THE TURING MACHINE AND RAM MODELS
1.8 PIDGIN ALGOL-A HIGH-LEVEL LANGUAGE
EXERCISES
BIBLIOGRAPHIC NOTES
2 DESIGN OF EFFICIENT ALGORITHMS
2.1 DATA STRUCTURES: LISTS, QUEUES, AND STACKS
2.2 SET REPRESENTATIONS
2.3 GRAPHS
2.4 TREES
2.5 RECURSION
2.6 DIVIDE-AND-CONQUER
2.7 BALANCING
2.8 DYNAMIC PROGRAMMING
2.9 EPILOGUE
EXERCISES
BIBLIOGRAPHIC NOTES
3 SORTING AND ORDER STATISTICS
3.1 THE SORTING PROBLEM
3.2 RADIX SORTING
3.3 SORTING BY COMPARISONS
3.4 HEAPSORT-AN O(n log n) COMPARISON SORT
3.5 QUICKSORT-AN O(n log n) EXPECTED TIME SORT
2.6 ORDER STATISTICS
3.7 EXPECTED TIME FOR ORDER STATISTICS
EXERCISES
BIBLIOGRAPHIC NOTES
4 DATA STRUCTURES FOR SET MANIPULATION PROBLEMS
4.1 FUNDAMENTAL OPERATIONS ON SETS
4.2 HASHING
4.3 BINARY SEARCH
4.4 BINARY SEARCH TREES
4.5 OPTIMAL BINARY SEARCH TREES
4.6 A SIMPLE DISJOINT-SET UNION ALGORITHM
4.7 TREE STRUCTURES FOR THE UNION-FIND PROBLEM
4.8 APPLICATIONS AND EXTENSIONS OF THE UNION-FIND ALGORITHM
4.9 BALANCED TREE SCHEMES
4.10 DICTIONARIES AND PRIORITY QUEUES
4.11 MERGEABLE HEAPS
4.12 CONCATENABLE QUEUES
4.13 PARTITIONING
4.14 CHAPTER SUMMARY
EXERCISES
BIBLIOGRAPHIC NOTES
5 ALGORITHMS ON GRAPHS
5.1 MINIMUM-COST SPANNING TREES
5.2 DEPTH-FIRST SEARCH
5.3 BICONNECTIVITY
5.4 DEPTH-FIRST SEARCH OF A DIRECTED GRAPH
5.5 STRONG CONNECTIVITY
5.6 PATH-FINDING PROBLEMS
5.7 A TRANSITIVE CLOSURE ALGORITHM
5.8 A SHORTEST-PATH ALGORITHM
5.9 PATH PROBLEMS AND MATRIX MULTIPLICATION
5.10 SINGLE-SOURCE PROBLEMS
5.11 DOMINATORS IN A DIRECTED ACYCLIC GRAPH: PUTTING THE CONCEPTS TOGETHER
I. Forward edges
II. Cross edges
EXERCISES
BIBLIOGRAPHIC NOTES
6 MATRIX MULTIPLICATION AND RELATED OPERATIONS
6.1 BASICS
6.2 STRASSEN'S MATRIX-MULTIPLICATION ALGORITHM
6.3 INVERSION OF MATRICES
6.4 LUP DECOMPOSITION OF MATRICES
6.5 APPLICATIONS OF LUP DECOMPOSITION
6.6 BOOLEAN MATRIX MULTIPLICATION
EXERCISES
BIBLIOGRAPHIC NOTES
7 THE FAST FOURIER TRANSFORM AND ITS APPLICATIONS
7.1 THE DISCRETE FOURIER TRANSFORM AND ITS INVERSE
7.2 THE FAST FOURIER TRANSFORM ALGORITHM
7.3 THE FFT USING BIT OPERATIONS
7.4 PRODUCTS OF POLYNOMIALS
7.5 THE SCHONHAGE-STRASSEN INTEGER-MULTIPLICATION ALGORITHM
EXERCISES
BIBLIOGRAPHIC NOTES
8 INTEGER AND POLYNOMIAL ARITHMETIC
8.1 THE SIMILARITY BETWEEN INTEGERS AND POLYNOMIALS
8.2 INTEGER MULTl PLICATION AND DIVISION
8.3 POLYNOMIAL MULTIPLICATION AND DIVISION
8.4 MODULAR ARITHMETIC
8.5 MODULAR POLYNOMIAL ARITHMETIC AND POLYNOMIAL EVALUATION
8.6 CHINESE REMAINDERING
8.7 CHINESE REMAINDERING AND INTERPOLATION OF POLYNOMIALS
8.8 GREATEST COMMON DIVISORS AND EUCLID'S ALGORITHM
8.9 AN ASYMPTOTICALLY FAST ALGORITHM FOR POLYNOMIAL GCD'S
8.10 INTEGER GCD'S
8.11 CHINESE REMAINDERING REVISITED
8.12 SPARSE POLYNOMIALS
EXERCISES
BIBLIOGRAPHIC NOTES
9 PATTERN-MATCHING ALGORITHMS
9.1 FINITE AUTOMATA AND REGULAR EXPRESSIONS
9.2 RECOGNITION OF REGULAR EXPRESSION PATTERNS
9.3 RECOGNITION OF SUBSTRINGS
9.4 TWO-WAY DETERMINISTIC PUSHDOWN AUTOMATA
9.5 POSITION TREES AND SUBSTRING IDENTIFIERS
EXERCISES
BIBLIOGRAPHIC NOTES
10 NP-COMPLETE PROBLEMS
10.1 NONDETERMINISTIC TURING MACHINES
10.2 THE CLASSES P AND NP
10.3 LANGUAGES AND PROBLEMS
10.4 NP-COMPLETENESS OF THE SATISFIABILITY PROBLEM
10.5 ADDITIONAL NP-COMPLETE PROBLEMS
10.6 POLYNOMIAL-SPACE-BOUNDED PROBLEMS
EXERCISES
BIBLIOGRAPHIC NOTES
11 SOME PROVABLY INTRACTABLE PROBLEMS
11.1 COMPLEXITY HIERARCHIES
11.2 THE SPACE HIERARCHY FOR DETERMINISTIC TURING MACHINES
11.3 A PROBLEM REQUIRING EXPONENTIAL TIME AND SPACE
11.4 A NONELEMENTARY PROBLEM
EXERCISES
BIBLIOGRAPHIC NOTES
12 LOWER BOUNDS ON NUMBERS OF ARITH.METIC OPERATIONS
12.1 FIELDS
12.2 STRAIGHT-LINE CODE REVISITED
12.3 A MATRIX .FORMULATION OF PROBLEMS
12.4 A ROW-ORIENTED LOWER BOUND ON MULTIPLICATIONS
12.5 A COLUMN-ORIENTED LOWER BOUND .ON MULTIPLICATIONS
12.6 A ROW-AND-COLUMN-ORIENTED BOUND ON MULTIPLICATIONS
12.7 PRECONDITIONING
EXERCISES
BIBLIOGRAPHIC NOTES
BIBLIOGRAPHY
INDEX
THE DESIGN
AND ANALYSIS
OF
COMPUTER
ALGORITHMS
Alfred V. Aho
Bell Laboratories
John E. Hopcroft
Cornell University
Jeffrey D. U II man
Princeton University
A " Addison-W~ley Publishing Company
Reading. Massachusetts · Menlo Park. California
London · Amsterdam · Don Mills. Ontario · Sydney
PREFACE
"' ......
The study of algorithms is at the very heart of c.:omputer science:-
Irr; -redeht
years a number of significant advances in the field of algorithms· have b'f'en
made. These advances have ranged from the development off~s,te,r; algori,th~~.
such as the fast Fourier transform. to the startling discovery of-q:rtain r)atur.~I.
problems·for which all algorithms are inefficient. These results have kindled
considerable interest in the study of algorithms. and the area of algorithm de
sign and analysis has blossomed into a field of intense interest. The intent of
this book is to bring together the fundamental results in this area, so the uni
fying principles and underlying concepts of algorithm design may more easily
be taught.
THE SCOPE OF THE BOOK
..1
To analyze the performance of an algorithm some model of a computer is
necessary. Our book begins by formulating several computer models which
are simple enough to establish analytical results but which at the same time
accurately reflect the salient features of real machines. These models include
the random access register machine. the random access stored program ma
chine, and some specialized variants of these. The Turing machine is intro
duced in order to prove the exponential lower bounds on efficiency in Chapters,
I 0 and 11. Since the trend in program design is away from machine language,
a high.:..level language called Pidgin ALGOL is introduced as the main vehicle
for describing algorithms. The complexity of a Pidgin ALGOL program is
related to the machine models.
The second chapter introduces basic data structures and programming
techniques often used in efficient algorithms.
down stores. queues. trees. and graphs. Detailed explanations of recursion.
divide-and-conquer. and dynamic programming are giv~n. along. with examples
of their use.
It covers the use of lists. push
Chapters 3 to 9 provide a sampling of the diverse areas to which the funda
mental techniques of Chapter :! can be applied. Otfr eh1phasis i"n these··chap~
ters is. on developing algo1:ithms that are a·symp.toti.caUy: th:e · m1ost' ~ffiti'ent
known. Because of thiS' emphasis. some of the algorithms. presented are.suit
able only for inputs whose size is much larger than what is currently encoun-
· ··
:" _·
iii
iv
PREFACE
tered in practice. This is particularly true of some of the matrix multiplication
algorithms in Chapter 6, the SchOnhage-Strassen integer-muitiptication algo
rithm of Chap~er 7. and some of the polynomial .and integer algorjthms of
Chapter 8.
,
On the o~her hand, most of the sorting algorithms of Chapter 3, the scarch
irig algorithms of Chapter 4, the graph a.lgorithms of Chapter 5, the fast Fourier
transform of Chapter 7, and the string-matching algorithms of Chapter 9 are
widely used, since the sizes of ,inputs for which these algorithms are efficient
are sufficiently s_maH to. be encountered in many practical situations ..
Chapters I 0 through 12 discuss lower bounds on computational com
plexity. The inherent computational difficulty of a problem is of universal
interest. both to program design and to an understanding of the nature of com
In Chapter IO an important class of problems, the NP-complete
putation.
problems, is studied. All problems in this class are equivalent in computa
qonal difficulty. in that if one problem in the class has an efficient (polynomial
ti-~e-~ound_ed) solution, then all problems in the class have efficient sol.µtions.
Since -this class of problems contains many practically important and well
studied problems, such as the integer-programming problem and the traveling
salesman problem, there is good r~ason to suspect that no problem in this class
can be solved efficiently. Thus, if a program designer knows that the problem
for which he is trying to find an effiC:ient algorithm is in this class. then he .may
very well be content to try heuristic approaches to the problem. In spite of the
overwhelming empirical evidence to the contrary, it is still an open question
whether NP-complete problems admit of efficient solutions.
In Chapter 11 certain problems are defined for which we can actually
prove that no efficient algorithms exist. The material in Chapters I 0 and 11
draws heavily on the concept of Turing machines introduced in Section~ 1.6
and 1.7.
·
·
In the final chapter of the book w.~ relate concepts of computational dif
ficulty to notions of linear independence in vector spaces. The material in this
~hapter provides techniques for proving lower bounds for much simpler prob
lems than those considered in Chapters I 0 and 11.
PREFACE
v
THE USE OF THE BOOK
This: book is intended as a first course in the design and analysis of algorithms.
The emphasis is on ideas and ease of un~erstanding rather than implementa
tion details or progra~ming tricks.
Informal, intuitive ~xplanations are often
used in place of long tedious proofs. The book is self-contained and assumes
no specific background iri mathematics or programming languages. However,
a certain amount of maturity in being able to handle mathematical concepts is
desirable, as is some exposure to a higher-level programming language such as
FORTRAN \or ALGOL. Some knowledge of linear algeb~a is needed for a
full understanding of Chapters 6; 7, 8, and 12.
This book has been used in graduate and undergraduate c'ourses in algo
In a one-semester course most of Chapters 1-5 and 9-10 were
rithm design.
covered, aiong with a smattering of topics from the remaining chapters.
In
introductory courses the emphasis was on material from Chapters 1~5. but
Se·ctions 1.6, 1.7, 4.13, 5.11, and Theorem 4.5 were generally not covered.
The book can also be used in more advanced courses emphasizing the th~ory of
algorithms. Chapters 6-12 could serve as the foundation for such a course.
Numerous exercises have been provided at the end of each chapter to
provide an instructor with a wide range of homework problems. The exercises
are graded according to difficulty. Exercises with no stars are suitable for in
troductory courses, singly starred exercises for more advanced courses, and
doubly starred exercises. for advanced graduate courses. The bibliographic
notes at the end of every chapter attempt to point to a published source for
each of the .algorithms and results contained in the text and the exercises.
ACKNOWLEDGMENTS
The material in this book has been derived from class notes for courses taught
by the authors at Cornell, Princeton, and Stevens Institute ofTechnoiogy. The
authors would like to thank the many people who have criticaily read various
portions of the manuscript and offered many helpful suggestions. In particular
we would like to thank Kellogg Booth, Stan Brown, Steve Chen, Allen Cypher.
vi
PREFACE
Arch Davis, Mike Fischer. Hania Gajewska. Mike Garey. Udai Gupta.
Mike Harrison. Matt Hecht, Harry Hunt. Dave Johnson. Marc Kaplan, Don
Johnson, Steve Johnson, Brian Kernighan. Don Knuth, Richard Ladner,
Anita LaSalle, Doug Mcllroy, Albert Meyer, Christos· Papadimitr~ou, Bill
Plauge~. John Savage, Howard Siege!, Ken Steiglit;::, Larry Stockmeyer, Tom
Szymanski, and Theodore Yen.
Special thanks go to Gemma Carnevale, Pauline Cameron. Hannah
Kresse, Edith Purser, and Ruth Suzuki for their cheerful and careful typing of
the manuscript.
The authors are also grateful to Bell Laboratories and Cornell. Princeton,
and the University of California at Berkeley for providing facilities for the
preparation of the manuscript.
June 1974
A. V. A.
J.E. H.
J. D. U.
CONTENTS
1 M_odels of Computation
2
1. l Algorithms and their complexit:,i . . . . . . . .
5
l .2 Random access machines . . . . . . . . . . .. .
l .3 Computational complexity of RAM programs .
l 2
1.4 A stored program model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
l .5 Abstractions of the RAM . . . . . . . . . . . . . . . . . . . ·. . . . . . . . . 19
25
l .6 A primitive model of computation: the Turing machine. . . .
3 J
1. 7 Relationship between the Turing machine and RAM models .
J.8
Pidgin ALGOL-a high-level language . . . . . . . . . . . .
33
2 Design of Efficient Algorithms
2.]
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
. ,.
Data structures: lists, queues, and stacks.
Set representations .
Graphs· ..
Trees ....... · ..
Recursion ..... .
Divide-and-conquer
. .
Balancing . . . . . . . .
Dynamic programming .
. . . . . . .
Epilogue
3 Sorting and Order Statist~cs
3. 1 The sorting problem . . .
3.2 Radix sorting ........ .
3.3 Sorting by comparisons ..
3.4 Heapsort-an O(n log n) comparison sort . . . . . . . .
3.5 Quicksort-an O(n log n) expected time sort.
3.6 Order statistics . . . . . . . . . . .
3. 7 Expected time for order statistics . . . . . . .
4 Data Structures for Set Manipulation Problems
Fundamental operations on sets .
4.1
4.2 Hashing . . . . . . .
4.3 Binary search , . . . . . . . .
4.4 Binary search trees . . . . . .
4.5 Optimal binary search trees .
4.6 A simple disjoint-set union algorithm.
vii
44
49
50
52
55
60
65
67
69
76
77
86
87
92
97
100'
108
111
113
] 15
] 19
124
viii
CONTENTS
4.7 Tree structures for the UNION-FIND problem . . . . . . . .
4.8 Applications and extensions of the UNION-FIND algorithm.
4.9 Balanced trP.e schemes . . . . . .
4.10 Dictionaries and priority queues .
4.11 Mergeable heaps ...
4.12 Concatenable queues .
4.13
4.14 Chapter summary . . .
Partitioning ....
5 Algorithms on Graphs
5.1 Minimum-cost spanning trees .
5.2 Depth-first search . . . . . . . .
5.3 Biconnectivity. . . . . . . . ..
5.4 Depth-first search of a directed graph .
5.5
Strong connectivity . . . . . . .
5.6
Path-finding problems . . . . .
5.7 A transitive closure algorithm .
5.8 A shortest-path algorithm ...
5.9
Path problems and matrix multiplication .
5.10 Single-source problems . . . . . . . . . . .
5.11 Dominators in a directed acyclic graph: putting the concepts together.
6 Matrix Multiplication and Related Operations
Basics .....................
6.1
6.2
Strassen's matrix-multiplication algorithm .
6.3
Inversion of matrices . . . . . . . . . .
6.4 LUP decomposition of matrices ....
6.5 Applications of LUP decomposition.
6.6 Boolean matrix multiplication . . . . .
7 The Fast Fourier Transform and its Applications
7.1 The discrete Fourier transform and its inverse.
7.:? The fast Fourier transform algorithm .
7.3 The FFT using bit operations . . . . . . . . . .
7.4
Products of polynomials . . . . . . . . . . . . .
7.5 The Schonhage-Strassen integer-multiplication algorithm .
I :?9
139
145
148
152
155
157
162
172
176
179
187
189
195
199
200
201
207
209
:?26
230
232
233
240
242
252
257
265
269
270
CONTENTS
ix
278
279
286
289
292
294
298
300
303
308
310
311
318
326
329
335
346·
364
372
374
377
384
395
406
407
410
419
8
8.1
8.2
8.3
8.4
8.5
8.6.
8.7
8.8
8.9
8.10
8.11
8.12
Integer ond Polynomial Arithmetic
The similarity between integers a.nd polynomials .
integer multiplication and division ...
Polynomial multiplication and division . . . . . . .
Modular arithmetic . . . . . . . . . . . . . . . . . .
Modular polynomial arithmetic and polynomial evaluation .
Chinese remaindering . . . . . . . . . .
. . . . . . . . . .
Chinese remaindering and interpolation of polynomials . .
Greatest common divisors and Euclid's algorithm .....
An asymptotically fast algorithm for polynomial GCD's .
Integer GCD's . . . . . . . . . .
Chinese remaindering revisited .
Sparse polynomials . . . . . .
9 Pattern-Matching Algorithms
Finite automata and regular expressions .
9.1
9.2 Recognition of regular expression patterns.
9.3 Recognition of substrings . . . . . . . . . .
9.4 Two-way deterministic pushdown automata.
9.5
Position trees and substring identifiers .
10 NP-Complete Problems
I 0.1 Nondeterministic Turing machines .
I 0.2 The classes (J' and .K(J' . . . . . . . .
I 0.3 Languages and problems . . . . . . .
I 0.4 NP-completeness of the satisfiability problem .
I 0.5 Additional NP-complete problems ..
I 0.6 Polynomial-space-bounded problems . . . . . .
11
Some Provably Intractable Problems
I 1.1 Complexity hierarchies . . . . . . . . . . . . . . . . . . .
11.2 The space hierarchy for deterministic Turing machines.
11.3 A problem requiring exponential time and space .
11.4 A nonelementary problem . . . . . . . . . . . . . . . . .
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
