算法导论MIT算法导论MIT算法导论MIT算法导论MIT

4星 · 超过85%的资源需积分: 13 181 浏览量更新于2023-03-03 评论 1 收藏 12.51MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

Introduction to Algorithms, Second Edition

Thomas H. Cormen

Charles E. Leiserson

Ronald L. Rivest

Clifford Stein

The MIT Press

Cambridge , Massachusetts London, England

McGraw-Hill Book Company

Boston Burr Ridge , IL Dubuque , IA Madison , WI New York San Francisco St. Louis

Montréal Toronto

This book is one of a series of texts written by faculty of the Electrical Engineering and

Computer Science Department at the Massachusetts Institute of Technology. It was edited and

produced by The MIT Press under a joint production-distribution agreement with the

McGraw-Hill Book Company.

Ordering Information:

North America

Text orders should be addressed to the McGraw-Hill Book Company. All other orders should

be addressed to The MIT Press.

Outside North America

All orders should be addressed to The MIT Press or its local distributor.

First edition 1990

or mechanical means (including photocopying, recording, or information storage and

retrieval) without permission in writing from the publisher.

This book was printed and bound in the United States of America.

Library of Congress Cataloging-in-Publication Data

Introduction to algorithms / Thomas H. Cormen ... [et al.].-2nd ed.

p. cm.

Includes bibliographical references and index.

ISBN 0-262-03293-7 (hc.: alk. paper, MIT Press).-ISBN 0-07-013151-1 (McGraw-Hill)

1. Computer programming. 2. Computer algorithms. I. Title: Algorithms. II. Cormen, Thomas

QA76.6 I5858 2001

005.1-dc21

2001031277

Preface

This book provides a comprehensive introduction to the modern study of computer

algorithms. It presents many algorithms and covers them in considerable depth, yet makes

their design and analysis accessible to all levels of readers. We have tried to keep

explanations elementary without sacrificing depth of coverage or mathematical rigor.

Each chapter presents an algorithm, a design technique, an application area, or a related topic.

Algorithms are described in English and in a "pseudocode" designed to be readable by anyone

who has done a little programming. The book contains over 230 figures illustrating how the

algorithms work. Since we emphasize efficiency as a design criterion, we include careful

analyses of the running times of all our algorithms.

The text is intended primarily for use in undergraduate or graduate courses in algorithms or

data structures. Because it discusses engineering issues in algorithm design, as well as

mathematical aspects, it is equally well suited for self-study by technical professionals.

In this, the second edition, we have updated the entire book. The changes range from the

addition of new chapters to the rewriting of individual sentences.

To the teacher

This book is designed to be both versatile and complete. You will find it useful for a variety

of courses, from an undergraduate course in data structures up through a graduate course in

algorithms. Because we have provided considerably more material than can fit in a typical

one-term course, you should think of the book as a "buffet" or "smorgasbord" from which you

can pick and choose the material that best supports the course you wish to teach.

You should find it easy to organize your course around just the chapters you need. We have

made chapters relatively self-contained, so that you need not worry about an unexpected and

unnecessary dependence of one chapter on another. Each chapter presents the easier material

first and the more difficult material later, with section boundaries marking natural stopping

points. In an undergraduate course, you might use only the earlier sections from a chapter; in

a graduate course, you might cover the entire chapter.

We have included over 920 exercises and over 140 problems. Each section ends with

exercises, and each chapter ends with problems. The exercises are generally short questions

that test basic mastery of the material. Some are simple self-check thought exercises, whereas

others are more substantial and are suitable as assigned homework. The problems are more

elaborate case studies that often introduce new material; they typically consist of several

questions that lead the student through the steps required to arrive at a solution.

We have starred (⋆) the sections and exercises that are more suitable for graduate students

than for undergraduates. A starred section is not necessarily more difficult than an unstarred

one, but it may require an understanding of more advanced mathematics. Likewise, starred

exercises may require an advanced background or more than average creativity.

To the student

We hope that this textbook provides you with an enjoyable introduction to the field of

algorithms. We have attempted to make every algorithm accessible and interesting. To help

you when you encounter unfamiliar or difficult algorithms, we describe each one in a step-by-

step manner. We also provide careful explanations of the mathematics needed to understand

the analysis of the algorithms. If you already have some familiarity with a topic, you will find

the chapters organized so that you can skim introductory sections and proceed quickly to the

more advanced material.

This is a large book, and your class will probably cover only a portion of its material. We

have tried, however, to make this a book that will be useful to you now as a course textbook

and also later in your career as a mathematical desk reference or an engineering handbook.

What are the prerequisites for reading this book?

• You should have some programming experience. In particular, you should understand

recursive procedures and simple data structures such as arrays and linked lists.

• You should have some facility with proofs by mathematical induction. A few portions

of the book rely on some knowledge of elementary calculus. Beyond that, Parts I and

VIII of this book teach you all the mathematical techniques you will need.

To the professional

The wide range of topics in this book makes it an excellent handbook on algorithms. Because

each chapter is relatively self-contained, you can focus in on the topics that most interest you.

Most of the algorithms we discuss have great practical utility. We therefore address

implementation concerns and other engineering issues. We often provide practical alternatives

to the few algorithms that are primarily of theoretical interest.

If you wish to implement any of the algorithms, you will find the translation of our

pseudocode into your favorite programming language a fairly straightforward task. The

pseudocode is designed to present each algorithm clearly and succinctly. Consequently, we do

not address error-handling and other software-engineering issues that require specific

assumptions about your programming environment. We attempt to present each algorithm

simply and directly without allowing the idiosyncrasies of a particular programming language

to obscure its essence.

To our colleagues

We have supplied an extensive bibliography and pointers to the current literature. Each

chapter ends with a set of "chapter notes" that give historical details and references. The

chapter notes do not provide a complete reference to the whole field of algorithms, however.

Though it may be hard to believe for a book of this size, many interesting algorithms could

not be included due to lack of space.

Despite myriad requests from students for solutions to problems and exercises, we have

chosen as a matter of policy not to supply references for problems and exercises, to remove

the temptation for students to look up a solution rather than to find it themselves.

Changes for the second edition

What has changed between the first and second editions of this book? Depending on how you

look at it, either not much or quite a bit.

A quick look at the table of contents shows that most of the first-edition chapters and sections

appear in the second edition. We removed two chapters and a handful of sections, but we have

added three new chapters and four new sections apart from these new chapters. If you were to

judge the scope of the changes by the table of contents, you would likely conclude that the

changes were modest.

The changes go far beyond what shows up in the table of contents, however. In no particular

order, here is a summary of the most significant changes for the second edition:

• Cliff Stein was added as a coauthor.

• Errors have been corrected. How many errors? Let's just say several.

• There are three new chapters:

o Chapter 1 discusses the role of algorithms in computing.

o Chapter 5 covers probabilistic analysis and randomized algorithms. As in the

first edition, these topics appear throughout the book.

o Chapter 29 is devoted to linear programming.

• Within chapters that were carried over from the first edition, there are new sections on

the following topics:

o perfect hashing (Section 11.5),

o two applications of dynamic programming (Sections 15.1 and 15.5), and

o approximation algorithms that use randomization and linear programming

(Section 35.4

• To allow more algorithms to appear earlier in the book, three of the chapters on

mathematical background have been moved from Part I

to the Appendix, which is Part

VIII.

• There are over 40 new problems and over 185 new exercises.

• We have made explicit the use of loop invariants for proving correctness. Our first

loop invariant appears in Chapter 2

, and we use them a couple of dozen times

throughout the book.

• Many of the probabilistic analyses have been rewritten. In particular, we use in a

dozen places the technique of "indicator random variables," which simplify

probabilistic analyses, especially when random variables are dependent.

• We have expanded and updated the chapter notes and bibliography. The bibliography

has grown by over 50%, and we have mentioned many new algorithmic results that

have appeared subsequent to the printing of the first edition.

We have also made the following changes:

• The chapter on solving recurrences no longer contains the iteration method. Instead, in

Section 4.2, we have "promoted" recursion trees to constitute a method in their own

right. We have found that drawing out recursion trees is less error-prone than iterating

recurrences. We do point out, however, that recursion trees are best used as a way to

generate guesses that are then verified via the substitution method.

• The partitioning method used for quicksort (Section 7.1) and the expected linear-time

order-statistic algorithm (Section 9.2) is different. We now use the method developed

by Lomuto, which, along with indicator random variables, allows for a somewhat

simpler analysis. The method from the first edition, due to Hoare, appears as a

problem in Chapter 7.

• We have modified the discussion of universal hashing in Section 11.3.3 so that it

integrates into the presentation of perfect hashing.

• There is a much simpler analysis of the height of a randomly built binary search tree in

Section 12.4.

• The discussions on the elements of dynamic programming (Section 15.3) and the

elements of greedy algorithms (Section 16.2

) are significantly expanded. The

exploration of the activity-selection problem, which starts off the greedy-algorithms

chapter, helps to clarify the relationship between dynamic programming and greedy

algorithms.

• We have replaced the proof of the running time of the disjoint-set-union data structure

in Section 21.4 with a proof that uses the potential method to derive a tight bound.

• The proof of correctness of the algorithm for strongly connected components in

Section 22.5 is simpler, clearer, and more direct.

• Chapter 24, on single-source shortest paths, has been reorganized to move proofs of

the essential properties to their own section. The new organization allows us to focus

earlier on algorithms.

• Section 34.5 contains an expanded overview of NP-completeness as well as new NP-

completeness proofs for the hamiltonian-cycle and subset-sum problems.

Finally, virtually every section has been edited to correct, simplify, and clarify explanations

and proofs.

Web site

Another change from the first edition is that this book now has its own web site:

http://mitpress.mit.edu/algorithms/. You can use the web site to report errors, obtain a list of

known errors, or make suggestions; we would like to hear from you. We particularly welcome

ideas for new exercises and problems, but please include solutions.

We regret that we cannot personally respond to all comments.

Acknowledgments for the first edition

Many friends and colleagues have contributed greatly to the quality of this book. We thank all

of you for your help and constructive criticisms.

MIT's Laboratory for Computer Science has provided an ideal working environment. Our

colleagues in the laboratory's Theory of Computation Group have been particularly supportive

and tolerant of our incessant requests for critical appraisal of chapters. We specifically thank

Baruch Awerbuch, Shafi Goldwasser, Leo Guibas, Tom Leighton, Albert Meyer, David

Shmoys, and Éva Tardos. Thanks to William Ang, Sally Bemus, Ray Hirschfeld, and Mark

Reinhold for keeping our machines (DEC Microvaxes, Apple Macintoshes, and Sun

剩余983页未读，继续阅读

garfieldkai

2012-08-14

内容不错，可惜是英文的

jiang_xi

粉丝: 0
资源: 1

会员权益专享

算法导论MIT算法导论MIT算法导论MIT算法导论MIT

评论2

会员权益专享

最新资源

算法导论MIT算法导论MIT算法导论MIT算法导论MIT

评论2

MIT算法导论MIT

MIT算法导论（part2）（chm格式）

算法导论MIT课程内容

mit算法导论 课件

mit算法导论bellman笔记

算法导论 csdn pdf

awz3 算法导论 电子书

算法导论 baase gelder

算法导论 下载 csdn

算法导论第三版答案 pdf

算法导论中文版pdf

生物信息学算法导论 solution

算法导论pdf完整版

算法导论第三版epub

算法导论 第三版pdf

clrs算法导论pdf

算法导论中文版 csdn

算法导论23章算法导论23章最小生成树习题

学算法导论需要掌握哪些知识

s算法导论25.3-1

会员权益专享

最新资源

mit算法导论课件

awz3 算法导论电子书

算法导论下载 csdn

算法导论第三版pdf