算法设计pdf电子书

所需积分/C币:25 2017-02-28 16:04:43 42.78MB PDF
收藏 收藏
举报

(美)克林伯格(Kleinberg 书籍出版:清华大学出版社 书籍页数:573 书籍ISBN:9787302143352 书籍人气:2116 推荐指数:★★★★
d itor: Mali Goldstein arn! Leyb Illy About the authors Cover phc to: o200S Tim Laman Natioral Geographic. A pair of wec ther on their nesi in Afri Prepress Printer: Courier Westford Ton Kleinberg is a professor of Computer Scicnce at Access the latest information abcut Addison-Wesley titles from our Worid Wide Web Cornell University. He d his ph D. from MIt aw-bc. com/ computing in 1996. He is the recipient of an NSF Career Award, Many of the designations used by manufacturers and sellers to distinguish the an ONR Young Investigator Award, an IBM Outstand- products are claimed as trademarks. Where those designations appear in this book, and Addison-Wcsley was aware of a trademark claim, the designations have been ences Award for Initiatives in Research, research fel printed in initial caps of ali lowships from the Packard and Sloan Foundations The programs and applicalions presented in this bock have been included for their s and teaching awards from the Cornell Engineering instructional value. They have been tested with care, but are not guaranteed for any particular purpose. Thc publisher does not offer any warranties or representations, nor ollege and Computer Science Department does it accept any liabilities with respect to the programs or applications. Kleinberg' s research is centered around algorithms, particularly those con cerned win the structure of networks and information, and with applications -Publication data Iu infornation science, optimization, data mining, and computational biol- Kleinberg, Jon ogy. His work on network analysis using hubs and authorities helped form the gorithm design/ Jon Kleinberg, Eva ' lardos -lst ed foundation for the curren: generation of internet search engines includes bibliographical references and inde ISBN 0-321-29535-B(alk. paper) 1. Computer algorithms. 2. Data stru orputer science)I 'lardos, Eva Eva Tardos is a professor of Computer Science at Co nel University. She rcceived her Ph. D. from eotvos 43K542005 2005000401 member ol the American Academy of Arts and Sci ACM Fellow shc is pient of Copyright e 20(G by Pearson Educalion, Inc. For information on obtaining pcrInnss1oL of =I NSF Presidential Young Investigator Award, the Fulk hein, Packard, and Sloan Foundations, and teacl ards fi'om the Cornell Engineering College and retrieval systen, ot' transmitted, in any form or by any means, electrnic, mechanicai Input er Science Department photocopying, recording, or ally toher media emboli now known ur hereafter to Tardos s research interests are focused on the design and analysis of become known, without thie prior written permission of the publisher:. Printed in th algorithms for proble graphs or networks, She is most known for he United States of America work on network-flow algorithms and approximation algorithIns for network problems. Her recent work focuses on algorithmic gamc thcory, an emerging ISBN0321-295358 234567810-CRW-080?0605 area concerned with designing systems and algorithms for selfish users Contents About the Authors introduction: Some Representative Problems 1.1 A First Problem: Stable Matching 1 1.2 Five 12 Solved exercises Exercises 2 Notes and Further Reading 28 2.1 CoMputational Tractability 29 2.2 Asymptotic Order of Growth 35 2.3 Implementing the Stable Matching Algorithm Using Lists and Arrays 42 4 A Survey of 2.5 A More Complex Data Structure: Priority Queues 57 Further read 3 Graph 3.1 Basic Defi 3. 3 Implementing Graph Traversal Using Queues and Stacks 87 3.4 Testing Biparliteness: An Application of Breadth-First Search 94. in Directed Graphs 97 Contenits 3.6 Directed Acyclic Graphs and Topological Ordering 99 Solved exercises 104 6.5 RNA Sccondary Structure: Dynamic xfitogramming over Exercises 107 Notes and Further Readling 112 6.6 Sequence Alignment 278 6.7 Sequence Alignment in Linear Space via Divide and 4 Greedy algoritiLmnS 115 4.1 Interval Scheduling: The Greedy Algorithm Stays Ahead 116 6. 8 Shortest Paths in a Graph 2: 4.2 Scheduling to Minimize Lateness: An Exchange Argument 125 6.9 Shorest Paths and Distance vector Protocols 297 4.3 Optimal Caching: A More Complex Exchange Argumcat I 6.10 4.4 Shortest Paths in a Graph 137 Solved exercises 307 4.5 The Minimum Spanning Tree Problem 142 4.6 Implementing Kruskal's Algorithm: The Union-Find Da(la Notes and Further Reading 335 Structure 151 4.7 Clustering 157 7 Network Flow 4.8 Huffman Codes and Data Compression 161 1 The Maximum-Flow Ptoblem and the Ford-Fulkerson 4.9 Minimum-Cost Arborescences: A Multi-Phase Greedy Algorithm 山 igorithm177 7.2 Maximnm Flows and Minimum Cuts in a network 34-6 Solved Exercises 18 7.3 Choosing Good Augmenting Paths 352 Exercises 188 7. 4 The Preflow-Push Maximum-Flow Algorithm. 357 Notes and Further Reading 20 7. 5 A First Application: The Bipartite Matching Problem 367 7.6 Disjoint Paths in Directed and Undirected Graphs 37 s Divide and Conquer 7.7 Extensions to the Maxium- Fiow problein 378 5.1 A First Recurrence: The Mergesort Algorithm 210 5.2 Further R Relations 21 7.9 Airline Scheduling 387 5.3 Counting inversions 221 7.I0 Image Segmentation 35 5.4 Finding the Ciosest Pair of points 225 7.1.1 Project Selection 396 5.5 Integer MII ltiplication 7.12 Basebal Elimination 400 5. 6 Convolutions and the Fast Fourier Transform 234 7.13 A Further Direction: Adding Cosls Lo the Matching ProbleIn7 404 Solved Exercises 242 Solyed exercises 411 Exercises 246 Exercises 415 Notes and Further Reading 249 Not es and Further Reading 448 6 Dynamic Programming 6. 1 Weighted interval Scheduling: A Recursive Procedt l Polynomial-Time Reductions 454 6.2 Principles of Dynamic Programming: Memoization or iteration 8.2 Reductions via"Gadgets": The Satisfiability Problen 459 Subproblems 258 3 Efficient Certification and the Definition of Np 6.3 Segmented Least Squares: Mulli-way Choices 261 -complete problems 466 ng Proble 473 The star indicates an optional section. (See the Preface for more information about the rel 6 Partitioning Prob 8.7 Graph Coloring 485 long the chapters and sections.) Contents Contents 8 Numerical Problems 490 11. 8 Arbitrarily Good Approximations: The Knapsack Problem 644 8.9 Co-NP and the Asymmetry of NP 495 Solved exercises 649 8.10 A Partial 'Taxonomy of hard Problems 49 Exercises 651 Solved exercises 500 Notes and Further Reading G59 Notes and Further Reading 529 12 Local Search 661 12. I The Landscape af an Optimization Prablem 652 9 PSPACE: A Class of Problems beyond Np 12.2 The Metropolis Algorithm and Simulated Annealing 666 9.1 PSPACE 531 12. 3 An Application of local Search to Hopfield Neural Networks 67 9.2 Some Hard Problems in PSPACE 533 12.4 Maximum-Cut Approximation via Local Search 9. 3 Solving Quantified Problems anld Games in Polynomial 12.5 Choosing a Neighbor Relation T 12.6 Classification via Local search 681 9.4 Solving the Planning Problem in Polynomial Space 538 12.7 Best Respunse Dynamics and Nash Equilibria 690 9.5 Proving Problems PSPACE-Complete 543 Solved exercises 700 olved Exercises 547 exerci Notes and Further Reading 705 Notes and Further Reading 551 13 Randomized Algorithms 10 Extending the Limits of tractabilit 13.1 A First Application: Contention Resolution 708 nding Small ve 13.2 Finding the Global Minimum Cut 71.4 10.2 Solving Np-Hard Problems on frees 558 r Expectations 719 10. 3 Coloring a Set of Circular Arcs 563 13. 4 A Rainndonizcd approximation Algorithm for MAX 3-SAT 724 Tree Decompositions of Graphs 572 13.5 Rande Constructing a lree Decomposition 584 13.6 Hashing: A Randomized implementation of Dictionaries 734 Icse 13.7 Finding the Closest Pair of points: A Randomized Approach 741 Exercises 59 Notes and Further Reading 598 13.8 Randomized Caching 750 13.9 Chernoff Bounds 758 Clng I1 Approximation Algorithms 599 11.1 Greedy Algorithms and Bounds on the Optimum: A Load 13.11 Packet Routing 762 Balancing Problem 600 13. 12 Backg ound: Some Basic Prohability Definitions 769 Solved exercises 11.2 The Center Selection Prohlem 606 11.3 Set Cover: A General Greedy Heuristic 61.2 11.4 The Pricing Method: Vertex Cover 618 Notes and Further Reading 793 11.5 Maximization via the Pricing Method: The Disjoint Paths Epilogue: aigoritiuns That Run Forer Problem 624 11.6 Linear Programming and Rounding: An appiication to Vertex References index 11.7 Load Balancing Revisited: A More Advanced LP Application 637 P reface gorithmic ideas are pervasive, and their reach is apparent in examples both within computer science and beyond. Sume uf lie major shifts in Internet routing standards can be viewed as debates over the deficiencies of one shortest-path algorithm and the relative advantages of another. The basic ions used by biologists tu express sinilaritic and ger have algorithmic definitions, The concerns voiced by economists over the feasibility of comhinatorial auctions in practice are rooted partly in the fact that these auctions contain computationally intractable search prohlems as specia! cases. And algorithmic notions arent just restricted to well-known and long. standing problems; one sees the reflections of these ideas on a regular bas in novel issues arising across a wide range of areas. The scientist from Yahoo! The told us over lunch one day abont their system for serving ads to users was Tibing a set of lu be modeled as a network fo former student, now a on staffing protocols for large hospitals, whom we happened to meet on a trip to new york cit he point is not simply that algorithms have many applications. The deeper issue is that the subjcct of algorithms is a powerful lens through which to view the field of computer science in general Algorithmic problems form Lhe heart of cormputer science, but they rarely arrive as cleanly packaged mathematically precise questions. Rather, they tend to come bundled together with lots of messy, apphicatiun-specific detail, some uf it essential of it terprise consists of two fundamental component s: the task of getting to the mathematically clean core of a problem and then the task of identifying the appropriale algorithrn design techniques, based on the structure of the problem. These two components interact: the more com)for table one is with the full array of possible design technique the muie one starts to recognize the clean furmulaLiuns that lie withinI nessy preface problems out in the world. At their most effective, then, algorithmic ideas do intelligence (planning, game playing, Hopfield net works ater vision not just provide solutions to well-pased problems; they form the language th (image segmentation), data mining (change-point detection, clustering), op lets you cleanly express the underlying question erations research (airline scheduling), and computational biology (sequence The goal of our book is to convey this approach to algorithms, as a design alignment, RNA secondary structure) process that begins with problems arising across the full range of computing The notion of computational intractability, and Np-complet n applications, builds on an understanding oi algorithm design techniques, and ticular,plays a large role in the book. This is consistent with results in the development of efficient solutions to these prohlems. We seek about the overali process of algorithm design. Some of the time, an interest to explore the role of algorithmic ideas in computer science generally, and ing problem in an application area will be amenable to an efficient relate these ideas to the range of precisely formulated problems for. which we solution, and some of the time it will be provably NP-complete; in order to cari design and analyze algorithms. In other words, what are the underlying fully address a new algorithmic problem, one should be able to explore both issues that motivate these prohlems, and how did we choose these particular of these options with equal familiarity. Since so many natural problems in 7s of formulating them? How did we recognize which design principles were uter: science are NP-complete, the development of methods to deal with appropriate in different situation table problems has becoine a crucial issue in the study of algorithms In keeping with this, our goal is to offer advice on how to identify clean ur book heavily reflects this themc. The discovery that a problem is NP oritlumic problem formulations in complex issues from different areas of complete should not be taken as the end of the story but as an invitation to computing and, from this, how to design efficient algorithms for the resulting ing the sequence of ideas-including false starts and dead ends-that led fom approach.es. simpler initial approaches to the eventual solution. The result is a style of position that does not take the most direct route from problem statement to Problems and solved exercises algorithm, hut we fccl it better reflects the way that we and our colleagues rtant feature of the hook is the collection of problems. Across all enuinely think about these questio chapters, the book includes over 200 proh almost all of them de and class-tested in homework or exams as part of our teaching of the course Overview at Cornell. W'e view the problems as a crucial component of the book, and he book is intended for students who have completed a prograrmming they arc structured in keeping with our overall approach to the materia!. Most based two-semester introductory computer science sequence(thic standard of them consist of extended verbal descriptions of a problem arising in an CS2” courses] ir which application area in computer science or elsewhere out in the world, and pait of basic aigorithms, manipulate discrete structures such as trees and graphs, and the problem is to practice what we discuss in the text: setting up the necessary apply basic data structures such as arrays, lists, que d stacks. Since notation and formalization, designing an algorithm, and then analyzing it and the interface between CS1/CS2 and a first algorithms course is not entirely proving it correct. (We view a complete answer to one of these problems as standard, we begin the book with self-contained coverage of topics that at orisistirig of all these components: a fully explained algorithm, an analysis of some institutions are familiar to students froin CSl/CS2, but which at other he running time, and a proof of correctness. ]The ideas for these problems institutions are included in the syllabi of the first algorithms course. This come in large part from discussions we have had over the years with people material can thus be treated either as a review or as new material; by including working in different areas, and in some cases they serve the dual purpose of it, we hope the book can be used in a broader array of courses, and with more recording an interesting (though manageable]application of algorithms that flexibility in the prerequisite knowledge that is assumed haven't seen written down anywhere else. To help with the proccss of working on these problems, we include in ithm design techniques by drawing on problems from across many areas of each chapter a section entitled"Solved Exercises, where we take one or more computer science arid related fields. To mention a few representative examples problems and describe how to go about formulating a solution. the discussion here we include fairly detailed discussions of applications from syster devoted to each solved exercise is therefore significantly longer than what networks(caching, switching, interdomain routing on the Internet), artificial would be needed simply to write a complete, correct solution (in other words, Preface XVIl significantly longer than what it would lake io receive full credit if thcsc were login and password, search the site for either "Kleinberg"ar "Tardos"or being assigned as homework proble with the rest of the text contact your local Addison-Wesley representative the discussions in these sections should be viewed as trying to give a sense Finally, we would appreciate receiving feedback on the book. In particular, of the larger process by which one might think about problems of this ly pe, culminating in the specification of a precise solution as in any book of this length, therc are undoubtedly crrors that have rcmaincd in the iina) version. Comments and reports of errors can be sent to us by e-mail It is worth mentioning poinis concerning the use of these problems at the address algbook@cs. cornell. edu; please include the word"feedbac as homework in a course are sequenced roughly in order in the subject line of the mmessage af increasing difficulty, but this is only an apploxirnate guide and we advise against placing too much weight on it: since the bulk of the problems were Nework Chapter-by-Chapter synopsis problems in each chapter arc really closely comparable in terms of difficulty Second, aside from the lowest-numbered ones, the probiems are designed to Chapter I starts by introducing some representative algorithmic problems. We involve sorme investrnent of tine, both to relate the problem description to the begini irrirnediately with the Stable Matching Problem, since we feel it sets algorithmic techniques in thc chaptcr, and then to actually design the necessary up the basic issues in algorithm design more concretely and more elegantly algorithm In our undergraduate class, we have tended to assign roughly three thar any abstract discussion could: stable matching is motivated by a natural of these problems per week though complex real-world issue, from which one can abstract an interesting problen statement and a surprisingly effective algorithm to solve this problcm. Pedagogical Features and Supplements of Chapter 1 discusses a list of five "rep that foreshadow topics from the remainder of the course. These five problem In addiion to the problems and solved exercises the book has a number of are interrelated in the sense that they are all variations and/or special cases furthcr pedagogical features, as well as additional supplements to facilitate its of the Independent Sct Problem; but onc is solvable by a greedy algorithm usc for tcaching one by dynamic programming, one by network flow, one [the independent As noted carlier, a large number of the sections in the book are devoted Set PToblem itself)is NP-complete, and one is PSPACE-complete. Tbe fact that to the formuiation of an algorithmic problem-including its background and closely related problems can vary greatly in complexity is an imporlant theme underlying motivation-and the design and analysis of an algorithm for this of the book, and these five problens serve as nileslolles Lai reappear as he problen. To reflect this style, these sections are consistently structured around a sequence of subsections: The Probiem, where the problem is described Chapters 2 and 3 cover the interface to the CS1/ CS2 course sequence and a precise formulation is worked out; "Designing the Algorithm, "where ihie appropriate design technique is employed to develop an algorithm;and mentioned earlier. Chapter 2 introduces the key mathematical definitions and Analyzing the Algorithm, which proves properties of the algorithm and otations used for analyzing algorithrms, as well as the motivating principles eIn. It begins with an informal overview o: what it means for a prob analyzes its efficiency. These subsections are hig icon depicting a feather. In cases where extensions to the problem or further len to be computationally tractable, together with the concept of polynomial analysis of the algorithm is pursued, there are additional subsections devoted timc as a formal notion of efficiency. It then discusses growTh rates of func- ons and asyinpiatic analysis more formally and offers a guide to commonly to these issues. The goal of this structure is to affer a relatively uniform style occurring functions in algorithm analysis, together with standard applications of presentation that moves from the initial discussion of a problem arising in a through to the detailed primitives needled for working with gi ith graphs, which are central to so number of supplemenTs are available in support of the book itself. An the problens in the book. A nunber of basic graph algorithIns are often iT instructor's manual works through all the problems, providing full solutions to plemented by students late in thc CSl/CS2 coursc scqucnce, but it is valuable each. A set or lecture slides, developed by Kevin Wayne of Princeton Universi to present the material here in a broader algorithm design context. In pa is also available, these slides follow the order of the books sections and can thus be used as the foundation for lectures in a course based on the book These ticular, we discuss basic graph definitions, graph traversal techniques such as breadth-first search and dcpth first scarch, and directed graph concepts files are avaiiable at wuv aw For instructions on obtaining a professor including strong connectivity and topological ordering Chapters 2 and 3 also present many of the basic data structures thai will find this is a valuable way to emphasize that intractability doesa' t end at be used for implementing algorithms throughout the book; more advanced NP-completeness, and PSPACE-conpletenless also forms the underpinning for data structures are presented in subsequent chapters. Our approach to structures is to introduce them as they are needed for the implementation of some central notions from artificial intelligence-.planning and gamc playing- that would otherwise not find a place in the algorithmic landscape we are the algorithns being developed in the book. Thus, although many of the dala d here will be familia to students fiom the CSl/Cs our focus is on these data structures in the broader context of algorithm design Chapters 10 through 12 cover three major techniques for dealing with com and analy putationally intractable problems: identification of structured spccial cases approximation algorithms, and local search heuristics. Our chapter on tractable Chapters 4 through 7 cover four major algorithm design techniques: greedy special cases emphasizes that instances of NP-complete problems arising algorithms, divide and conquer, dynamic programming, and network flow practice may not be nearly as hard as worst-case instances, because they often With greedy algorithms, the challenge is to recognize when they work and contain sone structure that can be exploited in the design of an efficient algo Then they don'l; our coverage of this topic is centered around a way of clas- rithm. We illustrate how NP-complete problems are often efficiently solvable sifying the kinds of arguments used to prove greedy algorithms correct. This whcn restricted to tree-structured inputs, and we conclude with an extended chapter concludes with some of the main applications of greedy algorithms discussion of tree decompositions of graphs. While this opic is imore suit- for shortest paths, undirected and directed spanning trees clustering, and able for a graduate course than for an undergraduate one, it is a technic compression For divide and conquer, we begin with a discussion of strategies with considerable practical utility for which it is hard to find an existing ence relations as bounds or running times we then shi how familiarity wilh these recurrences can guice The design of algorithms that discusses both the process of designing effective algorithms and the task of irnprove over straightforward approaches to a number of basic problems, in- undcrstanding the optimai solution well enough to obtain good bounds on it cluding the comparison of rankings, the computation of closest pairs of points design techniques for approximation algorithms, we focus on greedy algo in the plane, and the Fast Fourier Transform. Next we develop dynamic pro anda third method we refer lo as "pricing, " which gramming by starting with the recursive intuition belind it, and subsequently orporates ideas from each of the first two. Finally, we discuss local search bnilding up more and more expressive recurrence formulations through appli heuristics, including the Metropolis algorithm and simulated annealing. TI cations in which they naturally arise. This chapter concludes with extended topic is often missing from undergraduate algorithms courses, hecause very di ons of the dynarnic programming approach to two fundamental prob little is known in the way of provable guarantees for these algorithms; how ms:sequence alignment, with applications in commpuialional biology; and ever,given their widespread use in practice, we feel it is valuable for students shortest paths in grap nections to Internet routing protocols. Fi to know something about them, and we also include some cases in which ly, we cover algorithms for network flow problems, devoting much of our focus in this ch lo the extent that network flow is covered in algorithms courses, students p Chapter 13 covers the use of randomization in Lhe design of algorithn This is a topic on which several nice graduate-level books have beer written often left wit n appreciation for the wide range of problems to which it Our goal hcrc is to provide a more compact introduction to some of the can be applicd; we ury to do justice to its versatility by presenting applications ply randomized techn iqt to load balancing, scheduling, inage segmentation, and a number of other background in probability one typically gains from an undergraduate discrete probler apters 8 and 9 cover computational intractability. We devote most o our attention to NP completeness, organizing the basic NP-complete problems of the book thematically to help students rec ognize candidates for reductions when they The book is primarily designed for use in a first undergraduate course on encounter new problems. We build up to sone fairly complex proofs of NP algorithms, but it can also be used as the basis for an introductory graduate completeness, with guidance on how one goes about constructing a difficult reduction. We also consider types of comp: stational hardness beyond N ompleteness, particularly through the topic of PSPACE-coInplctcness. We When we use the book at the undergraduate level, we spend mughly ne lecture per numbered sectioN; in cases where there is more than one

...展开详情
试读 127P 算法设计pdf电子书
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    算法设计pdf电子书 25积分/C币 立即下载
    1/127
    算法设计pdf电子书第1页
    算法设计pdf电子书第2页
    算法设计pdf电子书第3页
    算法设计pdf电子书第4页
    算法设计pdf电子书第5页
    算法设计pdf电子书第6页
    算法设计pdf电子书第7页
    算法设计pdf电子书第8页
    算法设计pdf电子书第9页
    算法设计pdf电子书第10页
    算法设计pdf电子书第11页
    算法设计pdf电子书第12页
    算法设计pdf电子书第13页
    算法设计pdf电子书第14页
    算法设计pdf电子书第15页
    算法设计pdf电子书第16页
    算法设计pdf电子书第17页
    算法设计pdf电子书第18页
    算法设计pdf电子书第19页
    算法设计pdf电子书第20页

    试读已结束,剩余107页未读...

    25积分/C币 立即下载 >