算法设计：从应用到高效解决方案

算法设计

需积分: 19 28 浏览量更新于2023-05-22 收藏 5.06MB PDF 举报

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

30元优惠券

"算法设计（英文文字版）by Jon_Kleinberg & Eva_Tardos" 本书是Jon Kleinberg和Eva Tardos合著的英文版《算法设计》，旨在阐述算法设计作为解决问题过程的核心，以及它如何在计算机科学领域中发挥重要作用。作者强调算法不仅在计算机科学内部广泛应用，而且广泛渗透到生物学、经济学等多个领域。书中提到，互联网路由标准的变化、基因和基因组相似性的表达方式、组合拍卖的可行性问题，甚至像是网络广告分配和医院人员调度等现实世界的问题，其本质都与算法设计密切相关。算法设计不仅仅是解决具体问题，更是一种理解和表述问题的工具。算法问题通常伴随着大量的应用细节，既有关键要素也有非必要的复杂性。因此，算法设计的过程包括两个关键部分：一是将问题提炼成数学上清晰的核心，二是根据问题结构选择合适的算法设计技术。这种互动过程使我们能识别并解决现实世界中复杂问题的清洁形式。该书的目标是引导读者理解算法设计作为一种始于各种计算应用问题，依赖于对算法设计技术的理解，并最终形成高效解决方案的方法。书中探讨了算法思想在计算机科学中的作用，并将其与可以设计和分析的精确问题框架联系起来。书中还试图解答如何在不同计算领域的问题中识别出清晰的算法问题定义，以及如何基于这些定义设计高效的算法。书中采用了一种叙述风格，不直接从问题陈述过渡到算法，而是通过重构从简单初始方法到最终解决方案的思考过程来深入理解复杂的算法。这反映了作者及其同行在处理这些问题时的真实思考方式。此外，该书的制作团队包括编辑、项目经理、设计师、插画师、校对员和技术索引编制者，由Windfall Software进行排版和印刷，确保了内容的专业性和质量。书中可能包含了制造商和销售商用于区分其产品的商标，但仅在作者知道其为商标时才以特定格式表示。同时，书中还提到了程序和应用的示例，可能涉及到具体的编程语言和技术。

资源详情

资源推荐

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

Preface

xix

ﬁnd this is a valuable way to emphasize that intractability doesn’t end at

NP-completeness, and PSPACE-completeness also forms the underpinning for

some central notions from artiﬁcial intelligence—planning and game playing—

that would otherwise not ﬁnd a place in the algorithmic landscape we are

surveying.

Chapters 10 through 12 cover three major techniques for dealing with com-

putationally intractable problems: identiﬁcation of structured special cases,

approximation algorithms, and local search heuristics. Our chapter on tractable

special cases emphasizes that instances of NP-complete problems arising in

practice may not be nearly as hard as worst-case instances, because they often

contain some structure that can be exploited in the design of an efﬁcient algo-

rithm. We illustrate how NP-complete problems are often efﬁciently solvable

when restricted to tree-structured inputs, and we conclude with an extended

discussion of tree decompositions of graphs. While this topic is more suit-

able for a graduate course than for an undergraduate one, it is a technique

with considerable practical utility for which it is hard to ﬁnd an existing

accessible reference for students. Our chapter on approximation algorithms

discusses both the process of designing effective algorithms and the task of

understanding the optimal solution well enough to obtain good bounds on it.

As design techniques for approximation algorithms, we focus on greedy algo-

rithms, linear programming, and a third method we refer to as “pricing,” which

incorporates ideas from each of the ﬁrst two. Finally, we discuss local search

heuristics, including the Metropolis algorithm and simulated annealing. This

topic is often missing from undergraduate algorithms courses, because very

little is known in the way of provable guarantees for these algorithms; how-

ever, given their widespread use in practice, we feel it is valuable for students

to know something about them, and we also include some cases in which

guarantees can be proved.

Chapter 13 covers the use of randomization in the design of algorithms.

This is a topic on which several nice graduate-level books have been written.

Our goal here is to provide a more compact introduction to some of the

ways in which students can apply randomized techniques using the kind of

background in probability one typically gains from an undergraduate discrete

math course.

Use of the Book

The book is primarily designed for use in a ﬁrst undergraduate course on

algorithms, but it can also be used as the basis for an introductory graduate

course.

When we use the book at the undergraduate level, we spend roughly

one lecture per numbered section; in cases where there is more than one

剩余862页未读，继续阅读

颹蕭蕭

粉丝: 5w+
资源: 36

算法设计：从应用到高效解决方案

【电子版】算法设计 中文版+英文版+习题 作者: [美]克菜因伯格 / 塔多斯

算法设计Jon_Kleinberg&Eva;_Tardos.pdf

《algorithm design》/《算法设计》的pdf版本的课件(slides)个人觉得挺有用的

《算法设计》Kleinberg & Tardos 教材英文版

算法设计：Kleinberg & Tardos方法解析

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

Eva Tardos与Jon Kleinberg的算法设计扫描版

Kleinberg & Tardos的算法设计精要

算法设计答案 jon kleinberg , eva tardos 张立昂 屈婉玲

jon kleinberg and eva tardos. algorithm design答案

算法设计 jon kleinberg 答案

算法设计 jon kleinberg 中文pdf

算法设计jon kleinberg版答案

算法设计jon kleinberg pdf

算法设计jon kleinbergpdf

算法设计kleinberg答案

有米有一些进阶算法书推荐呢

复杂网络HITS算法

以关键码序列（Tim ，Kay ，Eva ，Roy ，Dot ，Jon ， Kim ，Ann ，Tom ，Jim， Guy ，Amy ）为例，手工执行一下排序算法（按字典序列比较关健字的大小）写出每一趟的关键码状态：1.直接插入排序；2.起泡排序；3.选择排序；4快速排序

数据结构与算法设计相关学习书籍

最新资源

【电子版】算法设计中文版+英文版+习题作者: [美]克菜因伯格 / 塔多斯

算法设计答案 jon kleinberg , eva tardos 张立昂屈婉玲