算法设计：英文版， Jon Kleinberg 和 Éva Tardos 的经典之作

需积分: 9 129 浏览量更新于2024-07-18 3 收藏 5.86MB PDF 举报

"《算法设计》是一本由Jon Kleinberg 和 Éva Tardos合作编写的英文书籍，专注于算法设计技术。这本书通过多种实例详细分析了各种算法设计方法，旨在将直观性和严谨性相结合，帮助读者理解算法设计的核心概念。作者以实际问题为起点，深入分析，逐步引导读者掌握关键的算法设计思想，并对算法的正确性和效率进行了验证和分析。" 《算法设计》一书的主要内容涵盖了以下几个方面： 1. **算法设计基础**：书中首先介绍了算法设计的基本原理，包括如何定义问题、如何构建解决方案，并讨论了算法设计过程中的基本策略，如分治法、动态规划、贪心算法等。 2. **数据结构**：数据结构是算法设计的基础，书中详细阐述了数组、链表、树、图等经典数据结构，以及它们在算法实现中的应用。 3. **分治策略**：这一部分讲解了如何将大问题分解为小问题来解决，如快速排序、归并排序等典型例子，展示了分治策略在优化算法性能中的作用。 4. **动态规划**：通过解决最短路径、背包问题等实例，书中深入探讨了动态规划的思想，如何避免重复计算，以及状态转移方程的建立。 5. **贪心算法**：介绍了贪心方法在解决优化问题中的应用，如霍夫曼编码、Prim算法构建最小生成树等。 6. **图算法**：重点讲解了图的遍历、最短路径问题（Dijkstra算法、Floyd-Warshall算法）、网络流问题（Ford-Fulkerson算法）等。 7. **随机化算法**：讨论了概率方法在算法设计中的应用，如Monte Carlo算法和Las Vegas算法，以及它们在解决NP难问题时的优势。 8. **近似算法**：对于难以找到精确解的问题，书中介绍了如何设计近似算法，例如旅行商问题的2-近似算法。 9. **复杂度理论**：涵盖了计算复杂度的基本概念，如P、NP类问题，以及NP完全问题的性质。 10. **算法分析与效率**：书中详细解释了时间复杂度和空间复杂度的概念，以及如何分析和估算算法的运行效率。通过这本书，读者不仅可以学习到具体的算法，还可以了解到如何分析问题、选择合适的算法设计策略，以及评估算法性能的方法。它适合计算机科学专业的学生，以及需要提升算法设计能力的软件工程师阅读。此外，书中丰富的实例和深入的解释也使得非专业读者能够理解并受益于这些高级算法知识。

xiv

Preface

problems out in the world. At their most effective, then, algorithmic ideas do

not just provide solutions to well-posed problems; they form the language that

lets you cleanly express the underlying questions.

The goal of our book is to convey this approach to algorithms, as a design

process that begins with problems arising across the full range of computing

applications, builds on an understanding of algorithm design techniques, and

results in the development of efﬁcient solutions to these problems. We seek

to explore the role of algorithmic ideas in computer science generally, and

relate these ideas to the range of precisely formulated problems for which we

can design and analyze algorithms. In other words, what are the underlying

issues that motivate these problems, and how did we choose these particular

ways of formulating them? How did we recognize which design principles were

appropriate in different situations?

In keeping with this, our goal is to offer advice on how to identify clean

algorithmic problem formulations in complex issues from different areas of

computing and, from this, how to design efﬁcient algorithms for the resulting

problems. Sophisticated algorithms are often best understood by reconstruct-

ing the sequence of ideas—including false starts and dead ends—that led from

simpler initial approaches to the eventual solution. The result is a style of ex-

position that does not take the most direct route from problem statement to

algorithm, but we feel it better reﬂects the way that we and our colleagues

genuinely think about these questions.

Overview

The book is intended for students who have completed a programming-

based two-semester introductory computer science sequence (the standard

“CS1/CS2” courses) in which they have written programs that implement

basic algorithms, manipulate discrete structures such as trees and graphs, and

apply basic data structures such as arrays, lists, queues, and stacks. Since

the interface between CS1/CS2 and a ﬁrst algorithms course is not entirely

standard, we begin the book with self-contained coverage of topics that at

some institutions are familiar to students from CS1/CS2, but which at other

institutions are included in the syllabi of the ﬁrst algorithms course. This

material can thus be treated either as a review or as new material; by including

it, we hope the book can be used in a broader array of courses, and with more

ﬂexibility in the prerequisite knowledge that is assumed.

In keeping with the approach outlined above, we develop the basic algo-

rithm design techniques by drawing on problems from across many areas of

computer science and related ﬁelds. To mention a few representative examples

here, we include fairly detailed discussions of applications from systems and

networks (caching, switching, interdomain routing on the Internet), artiﬁcial

Preface

intelligence (planning, game playing, Hopﬁeld networks), computer vision

(image segmentation), data mining (change-point detection, clustering), op-

erations research (airline scheduling), and computational biology (sequence

alignment, RNA secondary structure).

The notion of computational intractability, and NP-completeness in par-

ticular, plays a large role in the book. This is consistent with how we think

about the overall process of algorithm design. Some of the time, an interest-

ing problem arising in an application area will be amenable to an efﬁcient

solution, and some of the time it will be provably NP-complete; in order to

fully address a new algorithmic problem, one should be able to explore both

of these options with equal familiarity. Since so many natural problems in

computer science are NP-complete, the development of methods to deal with

intractable problems has become a crucial issue in the study of algorithms,

and our book heavily reﬂects this theme. The discovery that a problem is NP-

complete should not be taken as the end of the story, but as an invitation to

begin looking for approximation algorithms, heuristic local search techniques,

or tractable special cases. We include extensive coverage of each of these three

approaches.

Problems and Solved Exercises

An important feature of the book is the collection of problems. Across all

chapters, the book includes over 200 problems, almost all of them developed

and class-tested in homework or exams as part of our teaching of the course

at Cornell. We view the problems as a crucial component of the book, and

they are structured in keeping with our overall approach to the material. Most

of them consist of extended verbal descriptions of a problem arising in an

application area in computer science or elsewhere out in the world, and part of

the problem is to practice what we discuss in the text: setting up the necessary

notation and formalization, designing an algorithm, and then analyzing it and

proving it correct. (We view a complete answer to one of these problems as

consisting of all these components: a fully explained algorithm, an analysis of

the running time, and a proof of correctness.) The ideas for these problems

come in large part from discussions we have had over the years with people

working in different areas, and in some cases they serve the dual purpose of

recording an interesting (though manageable) application of algorithms that

we haven’t seen written down anywhere else.

To help with the process of working on these problems, we include in

each chapter a section entitled “Solved Exercises,” where we take one or more

problems and describe how to go about formulating a solution. The discussion

devoted to each solved exercise is therefore signiﬁcantly longer than what

would be needed simply to write a complete, correct solution (in other words,

xvi

Preface

signiﬁcantly longer than what it would take to receive full credit if these were

being assigned as homework problems). Rather, as with the rest of the text,

the discussions in these sections should be viewed as trying to give a sense

of the larger process by which one might think about problems of this type,

culminating in the speciﬁcation of a precise solution.

It is worth mentioning two points concerning the use of these problems

as homework in a course. First, the problems are sequenced roughly in order

of increasing difﬁculty, but this is only an approximate guide and we advise

against placing too much weight on it: since the bulk of the problems were

designed as homework for our undergraduate class, large subsets of the

problems in each chapter are really closely comparable in terms of difﬁculty.

Second, aside from the lowest-numbered ones, the problems are designed to

involve some investment of time, both to relate the problem description to the

algorithmic techniques in the chapter, and then to actually design the necessary

algorithm. In our undergraduate class, we have tended to assign roughly three

of these problems per week.

Pedagogical Features and Supplements

In addition to the problems and solved exercises, the book has a number of

further pedagogical features, as well as additional supplements to facilitate its

use for teaching.

As noted earlier, a large number of the sections in the book are devoted

to the formulation of an algorithmic problem—including its background and

underlying motivation—and the design and analysis of an algorithm for this

problem. To reﬂect this style, these sections are consistently structured around

a sequence of subsections: “The Problem,” where the problem is described

and a precise formulation is worked out; “Designing the Algorithm,” where

the appropriate design technique is employed to develop an algorithm; and

“Analyzing the Algorithm,” which proves properties of the algorithm and

analyzes its efﬁciency. These subsections are highlighted in the text with an

icon depicting a feather. In cases where extensions to the problem or further

analysis of the algorithm is pursued, there are additional subsections devoted

to these issues. The goal of this structure is to offer a relatively uniform style

of presentation that moves from the initial discussion of a problem arising in a

computing application through to the detailed analysis of a method to solve it.

A number of supplements are available in support of the book itself. An

instructor’s manual works through all the problems, providing full solutions to

each. A set of lecture slides, developed by Kevin Wayne of Princeton University,

is also available; these slides follow the order of the book’s sections and can

thus be used as the foundation for lectures in a course based on the book. These

ﬁles are available at www.aw.com. For instructions on obtaining a professor

Preface

xvii

contact your local Addison-Wesley representative.

Finally, we would appreciate receiving feedback on the book. In particular,

as in any book of this length, there are undoubtedly errors that have remained

in the ﬁnal version. Comments and reports of errors can be sent to us by e-mail,

at the address algbook@cs.cornell.edu; please include the word “feedback”

in the subject line of the message.

Chapter-by-Chapter Synopsis

Chapter 1 starts by introducing some representative algorithmic problems. We

begin immediately with the Stable Matching Problem, since we feel it sets

up the basic issues in algorithm design more concretely and more elegantly

than any abstract discussion could: stable matching is motivated by a natural

though complex real-world issue, from which one can abstract an interesting

problem statement and a surprisingly effective algorithm to solve this problem.

The remainder of Chapter 1 discusses a list of ﬁve “representative problems”

that foreshadow topics from the remainder of the course. These ﬁve problems

are interrelated in the sense that they are all variations and/or special cases

of the Independent Set Problem; but one is solvable by a greedy algorithm,

one by dynamic programming, one by network ﬂow, one (the Independent

Set Problem itself) is NP-complete, and one is PSPACE-complete. The fact that

closely related problems can vary greatly in complexity is an important theme

of the book, and these ﬁve problems serve as milestones that reappear as the

book progresses.

Chapters 2 and 3 cover the interface to the CS1/CS2 course sequence

mentioned earlier. Chapter 2 introduces the key mathematical deﬁnitions and

notations used for analyzing algorithms, as well as the motivating principles

behind them. It begins with an informal overview of what it means for a prob-

lem to be computationally tractable, together with the concept of polynomial

time as a formal notion of efﬁciency. It then discusses growth rates of func-

tions and asymptotic analysis more formally, and offers a guide to commonly

occurring functions in algorithm analysis, together with standard applications

in which they arise. Chapter 3 covers the basic deﬁnitions and algorithmic

primitives needed for working with graphs, which are central to so many of

the problems in the book. A number of basic graph algorithms are often im-

plemented by students late in the CS1/CS2 course sequence, but it is valuable

to present the material here in a broader algorithm design context. In par-

ticular, we discuss basic graph deﬁnitions, graph traversal techniques such

as breadth-ﬁrst search and depth-ﬁrst search, and directed graph concepts

including strong connectivity and topological ordering.

xviii

Preface

Chapters 2 and 3 also present many of the basic data structures that will

be used for implementing algorithms throughout the book; more advanced

data structures are presented in subsequent chapters. Our approach to data

structures is to introduce them as they are needed for the implementation of

the algorithms being developed in the book. Thus, although many of the data

structures covered here will be familiar to students from the CS1/CS2 sequence,

our focus is on these data structures in the broader context of algorithm design

and analysis.

Chapters 4 through 7 cover four major algorithm design techniques: greedy

algorithms, divide and conquer, dynamic programming, and network ﬂow.

With greedy algorithms, the challenge is to recognize when they work and

when they don’t; our coverage of this topic is centered around a way of clas-

sifying the kinds of arguments used to prove greedy algorithms correct. This

chapter concludes with some of the main applications of greedy algorithms,

for shortest paths, undirected and directed spanning trees, clustering, and

compression. For divide and conquer, we begin with a discussion of strategies

for solving recurrence relations as bounds on running times; we then show

how familiarity with these recurrences can guide the design of algorithms that

improve over straightforward approaches to a number of basic problems, in-

cluding the comparison of rankings, the computation of closest pairs of points

in the plane, and the Fast Fourier Transform. Next we develop dynamic pro-

gramming by starting with the recursive intuition behind it, and subsequently

building up more and more expressive recurrence formulations through appli-

cations in which they naturally arise. This chapter concludes with extended

discussions of the dynamic programming approach to two fundamental prob-

lems: sequence alignment, with applications in computational biology; and

shortest paths in graphs, with connections to Internet routing protocols. Fi-

nally, we cover algorithms for network ﬂow problems, devoting much of our

focus in this chapter to discussing a large array of different ﬂow applications.

To the extent that network ﬂow is covered in algorithms courses, students are

often left without an appreciation for the wide range of problems to which it

can be applied; we try to do justice to its versatility by presenting applications

to load balancing, scheduling, image segmentation, and a number of other

problems.

Chapters 8 and 9 cover computational intractability. We devote most of

our attention to NP-completeness, organizing the basic NP-complete problems

thematically to help students recognize candidates for reductions when they

encounter new problems. We build up to some fairly complex proofs of NP-

completeness, with guidance on how one goes about constructing a difﬁcult

reduction. We also consider types of computational hardness beyond NP-

completeness, particularly through the topic of PSPACE-completeness. We

剩余863页未读，继续阅读

后知后觉lyl

粉丝: 0
资源: 5

算法设计：英文版， Jon Kleinberg 和 Éva Tardos 的经典之作

第二届全国算法编程挑战赛春季赛题解分析

Kleinberg算法设计练习答案解析

算法(英文版)第4版：程序员必读的经典算法解析

算法设计与分析_算法导论（中文版第二版）

project3_java_软件体系结构与设计模式_加密算法_

Slay the Spire地图生成算法STS_MAP_ORACLE使用教程

达摩老生出品：高效光伏发电MPPT算法仿真_matlab

算法导论第三版英文版

算法导论 第二版 英文版

【算法】计算机程序设计艺术（第三版，英文版，第一卷：基本算法，Donald+E.Knuth+著）_Part1

最新资源

算法导论第二版英文版