Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 3
Текст из файла (страница 3)
We wish we could have carried out allyour suggestions. The only problem is that if we had, the second edition would have beenabout 3000 pages long!The second edition was produced in. Michael Downes converted themacros from"classic"to, and he converted the text files to use these new macros. David Jonessupport. Figures for the second edition were produced by the authorsalso providedusing MacDraw Pro. As in the first edition, the index was compiled using Windex, a Cprogram written by the authors, and the bibliography was prepared using.
AyorkorMills-Tettey and Rob Leathern helped convert the figures to MacDraw Pro, and Ayorkor alsochecked our bibliography.As it was in the first edition, working with The MIT Press and McGraw-Hill has been adelight. Our editors, Bob Prior of The MIT Press and Betsy Jones of McGraw-Hill, put upwith our antics and kept us going with carrots and sticks.Finally, we thank our wives-Nicole Cormen, Gail Rivest, and Rebecca Ivry-our childrenRicky, William, and Debby Leiserson; Alex and Christopher Rivest; and Molly, Noah, andBenjamin Stein-and our parents-Renee and Perry Cormen, Jean and Mark Leiserson, Shirleyand Lloyd Rivest, and Irene and Ira Stein-for their love and support during the writing of thisbook.
The patience and encouragement of our families made this project possible. Weaffectionately dedicate this book to them.THOMAS H. CORMENHanover, New HampshireCHARLES E. LEISERSONCambridge, MassachusettsRONALD L. RIVESTCambridge, MassachusettsCLIFFORD STEINHanover, New HampshireMay 2001Part I: FoundationsChapter ListChapter 1: The Role of Algorithms in ComputingChapter 2: Getting StartedChapter 3: Growth of FunctionsChapter 4: RecurrencesChapter 5: Probabilistic Analysis and Randomized AlgorithmsIntroductionThis part will get you started in thinking about designing and analyzing algorithms. It isintended to be a gentle introduction to how we specify algorithms, some of the designstrategies we will use throughout this book, and many of the fundamental ideas used inalgorithm analysis. Later parts of this book will build upon this base.Chapter 1 is an overview of algorithms and their place in modern computing systems.
Thischapter defines what an algorithm is and lists some examples. It also makes a case thatalgorithms are a technology, just as are fast hardware, graphical user interfaces, objectoriented systems, and networks.In Chapter 2, we see our first algorithms, which solve the problem of sorting a sequence of nnumbers. They are written in a pseudocode which, although not directly translatable to anyconventional programming language, conveys the structure of the algorithm clearly enoughthat a competent programmer can implement it in the language of his choice. The sortingalgorithms we examine are insertion sort, which uses an incremental approach, and mergesort, which uses a recursive technique known as "divide and conquer." Although the timeeach requires increases with the value of n, the rate of increase differs between the twoalgorithms.
We determine these running times in Chapter 2, and we develop a useful notationto express them.Chapter 3 precisely defines this notation, which we call asymptotic notation. It starts bydefining several asymptotic notations, which we use for bounding algorithm running timesfrom above and/or below. The rest of Chapter 3 is primarily a presentation of mathematicalnotation. Its purpose is more to ensure that your use of notation matches that in this book thanto teach you new mathematical concepts.Chapter 4 delves further into the divide-and-conquer method introduced in Chapter 2.
Inparticular, Chapter 4 contains methods for solving recurrences, which are useful fordescribing the running times of recursive algorithms. One powerful technique is the "mastermethod," which can be used to solve recurrences that arise from divide-and-conqueralgorithms. Much of Chapter 4 is devoted to proving the correctness of the master method,though this proof may be skipped without harm.Chapter 5 introduces probabilistic analysis and randomized algorithms. We typically useprobabilistic analysis to determine the running time of an algorithm in cases in which, due tothe presence of an inherent probability distribution, the running time may differ on differentinputs of the same size. In some cases, we assume that the inputs conform to a knownprobability distribution, so that we are averaging the running time over all possible inputs.
Inother cases, the probability distribution comes not from the inputs but from random choicesmade during the course of the algorithm. An algorithm whose behavior is determined not onlyby its input but by the values produced by a random-number generator is a randomizedalgorithm. We can use randomized algorithms to enforce a probability distribution on theinputs-thereby ensuring that no particular input always causes poor performance-or even tobound the error rate of algorithms that are allowed to produce incorrect results on a limitedbasis.Appendices A-C contain other mathematical material that you will find helpful as you readthis book.
You are likely to have seen much of the material in the appendix chapters beforehaving read this book (although the specific notational conventions we use may differ in somecases from what you have seen in the past), and so you should think of the Appendices asreference material. On the other hand, you probably have not already seen most of thematerial in Part I.
All the chapters in Part I and the Appendices are written with a tutorialflavor.Chapter 1: The Role of Algorithms inComputingWhat are algorithms? Why is the study of algorithms worthwhile? What is the role ofalgorithms relative to other technologies used in computers? In this chapter, we will answerthese questions.1.1 AlgorithmsInformally, an algorithm is any well-defined computational procedure that takes some value,or set of values, as input and produces some value, or set of values, as output.
An algorithm isthus a sequence of computational steps that transform the input into the output.We can also view an algorithm as a tool for solving a well-specified computational problem.The statement of the problem specifies in general terms the desired input/output relationship.The algorithm describes a specific computational procedure for achieving that input/outputrelationship.For example, one might need to sort a sequence of numbers into nondecreasing order.
Thisproblem arises frequently in practice and provides fertile ground for introducing manystandard design techniques and analysis tools. Here is how we formally define the sortingproblem:••Input: A sequence of n numbers a1, a2, ..., an .Output: A permutation (reordering)of the input sequence such that.For example, given the input sequence 31, 41, 59, 26, 41, 58 , a sorting algorithm returnsas output the sequence 26, 31, 41, 41, 58, 59 .
Such an input sequence is called an instanceof the sorting problem. In general, an instance of a problem consists of the input (satisfyingwhatever constraints are imposed in the problem statement) needed to compute a solution tothe problem.Sorting is a fundamental operation in computer science (many programs use it as anintermediate step), and as a result a large number of good sorting algorithms have beendeveloped. Which algorithm is best for a given application depends on-among other factorsthe number of items to be sorted, the extent to which the items are already somewhat sorted,possible restrictions on the item values, and the kind of storage device to be used: mainmemory, disks, or tapes.An algorithm is said to be correct if, for every input instance, it halts with the correct output.We say that a correct algorithm solves the given computational problem.
An incorrectalgorithm might not halt at all on some input instances, or it might halt with an answer otherthan the desired one. Contrary to what one might expect, incorrect algorithms can sometimesbe useful, if their error rate can be controlled. We shall see an example of this in Chapter 31when we study algorithms for finding large prime numbers.
Ordinarily, however, we shall beconcerned only with correct algorithms.An algorithm can be specified in English, as a computer program, or even as a hardwaredesign. The only requirement is that the specification must provide a precise description of thecomputational procedure to be followed.What kinds of problems are solved by algorithms?Sorting is by no means the only computational problem for which algorithms have beendeveloped. (You probably suspected as much when you saw the size of this book.) Practicalapplications of algorithms are ubiquitous and include the following examples:•••The Human Genome Project has the goals of identifying all the 100,000 genes inhuman DNA, determining the sequences of the 3 billion chemical base pairs that makeup human DNA, storing this information in databases, and developing tools for dataanalysis.
Each of these steps requires sophisticated algorithms. While the solutions tothe various problems involved are beyond the scope of this book, ideas from many ofthe chapters in this book are used in the solution of these biological problems, therebyenabling scientists to accomplish tasks while using resources efficiently. The savingsare in time, both human and machine, and in money, as more information can beextracted from laboratory techniques.The Internet enables people all around the world to quickly access and retrieve largeamounts of information. In order to do so, clever algorithms are employed to manageand manipulate this large volume of data.
Examples of problems which must be solvedinclude finding good routes on which the data will travel (techniques for solving suchproblems appear in Chapter 24), and using a search engine to quickly find pages onwhich particular information resides (related techniques are in Chapters 11 and 32).Electronic commerce enables goods and services to be negotiated and exchangedelectronically. The ability to keep information such as credit card numbers, passwords,and bank statements private is essential if electronic commerce is to be used widely.•Public-key cryptography and digital signatures (covered in Chapter 31) are among thecore technologies used and are based on numerical algorithms and number theory.In manufacturing and other commercial settings, it is often important to allocate scarceresources in the most beneficial way. An oil company may wish to know where toplace its wells in order to maximize its expected profit.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
