《算法导论》第二版：数据结构与高效算法详解

算法导论

algorithm

需积分: 9 145 浏览量更新于2024-08-02 收藏 13.8MB PDF 举报

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

领优惠券(最高得80元）

"《算法导论:第二版》(Introduction to Algorithms)[含图含公式]是计算机科学领域的经典之作，由Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest和Clifford Stein四位作者共同编撰。该书在2007年被china-pub会员评选为“年度我最喜爱的十大技术图书”之一，同时也在《程序员》等机构的读者评选中脱颖而出，被评为2006年最受关注的十大IT图书之一。本书以其深入浅出的方式，为读者全面介绍了众多实用的数据结构和高效算法。它采用独特的“五个一”结构，每章专注于一个算法、一种设计技术、一个特定的应用领域以及一个相关的主题，这种系统性的教学方法使得不同层次的读者都能从中受益。无论是初学者还是经验丰富的专业人士，都能在书中找到适合自己的内容。《算法导论》第二版是在1990年首次出版，2002年进行了第三次印刷，版权归属于麻省理工学院。全书严谨且富有洞察力，不仅包含了丰富的理论知识，还配以清晰的图表和公式，便于理解和实践。书中强调了算法的原创性和实用性，强调对算法的分析和设计方法，涉及的主题涵盖了排序、搜索、图算法、动态规划等核心领域。此外，该书还遵循严格的版权规定，明确指出任何部分不得未经许可进行任何形式的复制或机械或电子传播，体现了作者对知识产权的尊重。对于北美地区的读者，可以直接联系McGraw-Hill Book Company进行订购；而对于全球其他地区，应直接联系The MIT Press或其当地分销商获取书籍。《算法导论:第二版》是一本不可或缺的IT学习资源，无论你是希望深入理解算法基础，还是寻求解决实际问题的高效解决方案，都值得投入时间和精力研读。这本书不仅是学习者的教科书，也是专业人士的参考指南，为计算机科学和信息技术的发展做出了重大贡献。"

资源详情

资源推荐

Preface xv

To the professional

The wide range of topics in this book makes it an excellent handbook on algo-

rithms. 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 ﬁnd 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 is-

sues that require speciﬁc assumptions about your programming environment. We

attempt to present each algorithm simply and directly without allowing the idiosyn-

crasies 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

ﬁeld 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

ﬁnd it themselves.

Changes for the second edition

What has changed between the ﬁrst 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 ﬁrst-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 signiﬁcant changes for the

second edition:

xvi Preface

•

Cliff Stein was added as a coauthor.

•

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

•

There are three new chapters:

•

Chapter 1 discusses the role of algorithms in computing.

•

Chapter 5 covers probabilistic analysis and randomized algorithms. As in

the ﬁrst edition, these topics appear throughout the book.

•

Chapter 29 is devoted to linear programming.

•

Within chapters that were carried over from the ﬁrst edition, there are new sec-

tions on the following topics:

•

perfect hashing (Section 11.5),

•

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

•

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

ﬁrst 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 bibli-

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

results that have appeared subsequent to the printing of the ﬁrst edition.

We have also made the following changes:

•

The chapter on solving recurrences no longer contains the iteration method. In-

stead, 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 veriﬁed via the substi-

tution method.

Preface xvii

•

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 ﬁrst edition, due

to Hoare, appears as a problem in Chapter 7.

•

We have modiﬁed 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 signiﬁcantly expanded.

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

algorithms chapter, helps to clarify the relationship between dynamic program-

ming 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 ﬁrst 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.

xviii Preface

Acknowledgments for the ﬁrst 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 environ-

ment. 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 speciﬁcally thank Baruch Awerbuch, Shaﬁ Goldwasser, Leo Guibas,

Tom Leighton, Albert Meyer, David Shmoys, and

Eva Tardos. Thanks to William

Ang, Sally Bemus, Ray Hirschfeld, and Mark Reinhold for keeping our machines

(DEC Microvaxes, Apple Macintoshes, and Sun Sparcstations) running and for re-

compiling T

X whenever we exceeded a compile-time limit. Thinking Machines

Corporation provided partial support for Charles Leiserson to work on this book

during a leave of absence from MIT.

Many colleagues have used drafts of this text in courses at other schools. They

have suggested numerous corrections and revisions. We particularly wish to thank

Richard Beigel, Andrew Goldberg, Joan Lucas, Mark Overmars, Alan Sherman,

and Diane Souvaine.

Many teaching assistants in our courses have made signiﬁcant contributions to

the development of this material. We especially thank Alan Baratz, Bonnie Berger,

Aditi Dhagat, Burt Kaliski, Arthur Lent, Andrew Moulton, Marios Papaefthymiou,

Cindy Phillips, Mark Reinhold, Phil Rogaway, Flavio Rose, Arie Rudich, Alan

Sherman, Cliff Stein, Susmita Sur, Gregory Troxel, and Margaret Tuttle.

Additional valuable technical assistance was provided by many individuals.

Denise Sergent spent many hours in the MIT libraries researching bibliographic

references. Maria Sensale, the librarian of our reading room, was always cheerful

and helpful. Access to Albert Meyer’s personal library saved many hours of li-

brary time in preparing the chapter notes. Shlomo Kipnis, Bill Niehaus, and David

Wilson proofread old exercises, developed new ones, and wrote notes on their so-

lutions. Marios Papaefthymiou and Gregory Troxel contributed to the indexing.

Over the years, our secretaries Inna Radzihovsky, Denise Sergent, Gayle Sherman,

and especially Be Blackburn provided endless support in this project, for which we

thank them.

Many errors in the early drafts were reported by students. We particularly

thank Bobby Blumofe, Bonnie Eisenberg, Raymond Johnson, John Keen, Richard

Lethin, Mark Lillibridge, John Pezaris, Steve Ponzio, and Margaret Tuttle for their

careful readings.

Colleagues have also provided critical reviews of speciﬁc chapters, or informa-

tion on speciﬁc algorithms, for which we are grateful. We especially thank Bill

Aiello, Alok Aggarwal, Eric Bach, Vaˇsek Chv´atal, Richard Cole, Johan Hastad,

Alex Ishii, David Johnson, Joe Kilian, Dina Kravets, Bruce Maggs, Jim Orlin,

James Park, Thane Plambeck, Hershel Safer, Jeff Shallit, Cliff Stein, Gil Strang,

Preface xix

Bob Tarjan, and Paul Wang. Several of our colleagues also graciously supplied

us with problems; we particularly thank Andrew Goldberg, Danny Sleator, and

Umesh Vazirani.

It has been a pleasure working with The MIT Press and McGraw-Hill in the

development of this text. We especially thank Frank Satlow, Terry Ehling, Larry

Cohen, and Lorrie Lejeune of The MIT Press and David Shapiro of McGraw-Hill

for their encouragement, support, and patience. We are particularly grateful to

Larry Cohen for his outstanding copyediting.

Acknowledgments for the second edition

When we asked Julie Sussman, P.P.A., to serve as a technical copyeditor for the

second edition, we did not know what a good deal we were getting. In addition

to copyediting the technical content, Julie enthusiastically edited our prose. It is

humbling to think of how many errors Julie found in our earlier drafts, though

considering how many errors she found in the ﬁrst edition (after it was printed,

unfortunately), it is not surprising. Moreover, Julie sacriﬁced her own schedule

to accommodate ours—she even brought chapters with her on a trip to the Virgin

Islands! Julie, we cannot thank you enough for the amazing job you did.

The work for the second edition was done while the authors were members of

the Department of Computer Science at Dartmouth College and the Laboratory for

Computer Science at MIT. Both were stimulating environments in which to work,

and we thank our colleagues for their support.

Friends and colleagues all over the world have provided suggestions and opin-

ions that guided our writing. Many thanks to Sanjeev Arora, Javed Aslam, Guy

Blelloch, Avrim Blum, Scot Drysdale, Hany Farid, Hal Gabow, Andrew Goldberg,

David Johnson, Yanlin Liu, Nicolas Schabanel, Alexander Schrijver, Sasha Shen,

David Shmoys, Dan Spielman, Gerald Jay Sussman, Bob Tarjan, Mikkel Thorup,

and Vijay Vazirani.

Many teachers and colleagues have taught us a great deal about algorithms. We

particularly acknowledge our teachers Jon L. Bentley, Bob Floyd, Don Knuth,

Harold Kuhn, H. T. Kung, Richard Lipton, Arnold Ross, Larry Snyder, Michael I.

Shamos, David Shmoys, Ken Steiglitz, Tom Szymanski,

Eva Tardos, Bob Tarjan,

and Jeffrey Ullman.

We acknowledge the work of the many teaching assistants for the algorithms

courses at MIT and Dartmouth, including Joseph Adler, Craig Barrack, Bobby

Blumofe, Roberto De Prisco, Matteo Frigo, Igal Galperin, David Gupta, Raj D.

Iyer, Nabil Kahale, Sarfraz Khurshid, Stavros Kolliopoulos, Alain Leblanc, Yuan

Ma, Maria Minkoff, Dimitris Mitsouras, Alin Popescu, Harald Prokop, Sudipta

Sengupta, Donna Slonim, Joshua A. Tauber, Sivan Toledo, Elisheva Werner-Reiss,

Lea Wittie, Qiang Wu, and Michael Zhang.

剩余1202页未读，继续阅读

phoeagon

粉丝: 1
资源: 6

《算法导论》第二版：数据结构与高效算法详解

算法导论[含图含公式]【英文原版】

算法导论（Introduction to algorithms）英文原版

Design a two column layout and in the first column insert the following table and in the second column enter the details of your course and your details

activiti-bpmn-layout-5.22.0 的pom

introduction to algorithms 3rd

introduction to algorithms - hardcover edition

introduction to algorithms pdf

introduction to algorithms 4th

clrs算法导论pdf

introduction to algorithms. mit press, 2001.

typedef pair<int,int>PII

introduction to algorithms, 3rd edition, the mit press 2009 pdf

C++头文件#include <algorithms>什么意思

typedef pair<int, int> PII;

数据结构图书借阅管理系统c++

cgal读取obj格式的三维线段

Python xpath处理数据

crypto-js html

推荐一本算法最好的书籍

数据结构和算法的推荐书籍和视频

最新资源