IntroductiontoAlgorithms(2ndEdition)算法导论(英文版)资源-CSDN文库

需积分: 10 111 浏览量 2013-04-23 17:58:19 上传评论 1 收藏 12.48MB PDF 举报

### 知识点详述 #### 一、书籍概述与背景《算法导论》（第二版）是一本由Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest和Clifford Stein四位作者共同编写的经典教材。这本书由麻省理工学院出版社（The MIT Press）和McGraw-Hill Book Company联合出版发行，主要针对电气工程与计算机科学领域的读者。 #### 二、书籍内容与结构本书提供了对现代计算机算法研究的全面介绍，不仅涵盖了各种经典的算法及其设计技术，还深入探讨了它们的应用领域以及相关的理论知识。每一章都围绕一个特定的主题展开，包括但不限于： - **算法介绍**：书中详细介绍了多种重要的算法，并通过易懂的语言和伪代码来阐述其工作原理。 - **设计技巧**：每种算法背后的设计思路都被精心剖析，帮助读者理解算法设计的核心理念。 - **应用领域**：算法在不同场景下的应用被广泛讨论，例如排序算法在数据处理中的应用等。 - **相关主题**：除了具体的算法之外，还包括了如算法复杂性分析、数据结构设计等相关的重要概念。 #### 三、编写风格与特点 - **语言表达清晰易懂**：尽管本书涉及大量复杂的数学概念和技术细节，但作者们努力保持语言的平实和通俗，使得不同程度的读者都能轻松理解。 - **丰富的示例与图解**：为了帮助读者更好地理解算法的工作机制，书中包含了超过230幅精美的插图，这些图表直观地展示了算法的执行过程。 - **强调效率的重要性**：效率是本书评估算法好坏的一个重要标准，因此书中不仅关注算法的正确性，还非常注重其运行效率。 #### 四、版权与版本信息 - **版权归属**：本书版权归麻省理工学院所有，未经出版社书面许可，任何部分均不得以任何形式复制。 - **版本历史**：第一版于1990年发布，本书为第二版，于2001年出版。 - **ISBN号**：本书有两个ISBN号，分别对应不同的出版商： - ISBN 0-262-03293-7（MIT Press） - ISBN 0-07-013151-1（McGraw-Hill） #### 五、读者定位与适用范围 - **初学者友好**：对于计算机科学入门者而言，《算法导论》提供了一个易于理解和接受的起点。 - **进阶读者适用**：即使是对于已经有一定编程基础或算法了解的读者，本书也能提供深入的技术指导和理论支撑。 - **科研工作者必备**：对于从事计算机科学研究的专业人士来说，《算法导论》是一部不可或缺的参考书。 #### 六、结语《算法导论》作为一本广受赞誉的经典教材，不仅因其全面而深入的内容获得了广泛认可，更因其清晰的写作风格和实用的教学方法而深受读者喜爱。无论是对于学习计算机科学的学生，还是对于从事相关领域工作的专业人士来说，这都是一本值得反复阅读和深入钻研的好书。

资源推荐

资源详情

资源评论

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页未读，继续阅读

评论收藏

内容反馈

白水不开

粉丝: 91
资源: 78

Introduction to Algorithms(2nd Edition) 算法导论 (英文版)

最新资源

Introduction to Algorithms(2nd Edition) 算法导论 (英文版)

算法导论（MIT Press - Introduction To Algorithms, 2nd Edition）

Introduction to Algorithms (2nd Edition).pdf

Introduction.To.Algorithms,.Second.Edition

Introduction To Algorithms (Mit Press 2Nd Edition).pdf

Introduction to Algorithms 2nd Edition算法导论原版

Introduction to Algorithms Second Edition

Introduction to Algorithms, Second Edition

Introduction To Algorithms，算法导论英文版

Introduction to algorithms (2nd edition)

Introduction to Algorithms 2nd Edition

Introduction to Algorithms 2nd Edition（算法导论第二版）

算法导论MIT(第二版)及习题解答Introduction to Algorithms 2nd Edition.pat1(共2部分)

MIT Introduction to Algorithms 2nd-Edition

introduction to algorithms 2nd edition - MIT algorithm module assignments and solutioins 算法导论第二版 - MIT算法课的作业, 答案和考题

算法导论（第二版） 英文版 Introduction to Algorithms 2nd Edition

算法导论 英文 第二版（Introduction To Algorithm second edition）

算法导论英文版

算法导论MIT(第二版)及习题解答Introduction to Algorithms 2nd Edition.part2(共2部分)

算法导论（英文）（第2版）Introduction To Algorithms 2nd Edition

算法导论第二版（Introduction to Algorithms）2nd Edition （chm格式）

MIT - Introduction to Algorithms 2nd Edition

算法导论英文版(Word版)---Introduction_to_Algorithms_2nd_Edition

算法导论 英文版

算法导论（英文版）

最新资源

算法导论（第二版）英文版 Introduction to Algorithms 2nd Edition

算法导论英文第二版（Introduction To Algorithm second edition）

算法导论英文版