算法设计 Jon_Kleinberg英文原版

所需积分/C币:50 2018-10-26 11:26:58 15.47MB PDF
收藏 收藏 1
举报

英文原版,带有完整书签。本书以各种算法设计技术(如贪心法、分支策略、动态规划、网络流、近似算法、随机算法等)为主线来组织素材,突出了算法设计的思想和分析的基本原则,为从事实际问题的算法设计与分析工作提供了清晰的、整体的思路和方法
图 JoN KLEINBERG o EVA TARDOS 〔 oriel| University EARSO Addison B New York London Toronto Sydney Tokyo Singapore Madrid Mexico City Munich Paris Cape Town Hong Kong Montreal Acquisitions Editor: Matt goldstein Project editor: Maite Suarez-Rivas Production Supervisor: Marilyn Lloyd Marketing Manager: Michelle brown Marketing Coordinator: Jake Zavracky Project Management: windfall software Composition: Windfall Software, using ZzlE> Copyeditor: Carol leyba Technical Illustration: Dartmouth Publishing Proofreader: Jennifer mcclain Indexer: Ted Laux Cover Design: Joyce Cosentino wells Cover PhotO: G 2005 Tim Laman/ National Geographic. A pair of weaverbirds work together on their Afr Prepl Caroline fell Printer: Courier Westford Access the latest info Addison-Wesley titles from our World Wide Web sitehttp://www.aw-bc.com/computin Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and Addison-Wesley was aware of a trademark claim, the designations have been printed in initial caps or all caps The programs and applications presented in this book have been included for their instructional value. They have been tested with care, but are not guaranteed for any particular purpose. The publisher does not offer any warranties or representations,nor does it accept any liabilities with respect to the programs or applications Library of Congress Cataloging-in-Publication Data Klein berg, Jon Algorithm design/ Jon Kleinberg, Eva Tardos .--1st ed P. CIIL. Includes bibliographical references and index IsBN 0-3Z1-29535-8(alk. paper) 1. Computer algorithms. 2. Data structures(Computer science) I. Tardos, Eva II. Title QAz6.9A43K542005 005.1-dc22 2005000401 Copyright o 2006 by Pearson Education, In For information on obtaining permission for use of material in this work, please submit a written request to Pearson Education, Inc, Rights and Contract Department, 75 Arlington Street, Suite 300, Boston, MA O2116 or fax your request to(617)848-7047 All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical photocopying, recording, or any toher media embodiments now known or hereafter to become known, without the prior written permission of the publisher. Printed in the United States of america ISBN0-321-29535-8 23456789i0CRW-08070605 About the authors Jon Kleinberg is a professor of Computer Science at Cornell university He received his Ph D. from M.I.T in 1996. He is the recipient of an NSF Career Award, an ONR Young Investigator Award, an IBM Outstand ing Innovation Award, the National Academy of Sci ences award for Initiatives in Research, research fel lowships from the packard and Sloan Foundations and teaching awards from the Cornell Engineering College and Computer Science Department Kleinberg's research is centered around algorithms, particularly those con cerned with the structure of networks and information, and with applications to information science, optimization, data mining, and computational biol ogy. His work on network analysis using hubs and authorities helped form the foundation for the current generation of Internet search engines Eva Tardos is a professor of Computer Science at Cor- nell University. She received her ph. D. from Eotvos University in Budapest, Hungary in 1984. She is member of the american academy of Arts and Sci- ences, and an ACM Fellow; she is the recipient of an NSF Presidential Young Investigator Award, the Fulk erson Prize, research fellowships from the guggen heim, Packard, and Sloan Foundations, and teach- ing awards from the Cornell Engineering College and Computer Science department Tardos's research interests are focused on the design and analysis of algorithms for problems on graphs or networks. She is most known for her work on network-flow algorithms and approximation algorithms for network problems. Her recent work focuses on algorithmic game theory, an emerging area concerned with designing systems and algorithms for selfish users Contents About the Authors Preface viI1 I Introduction: Some Representative Problems 1.1 A First Problem: Stable Matching 1 1.2 Five Representative Problems 12 Solved Exercises 19 Exercises 22 Notes and Further reading 28 2 Basics of Algorithm Analysis 29 2.1 Computational Tractability 29 2.2 Asymptotic Order of growth 35 2.3 Implementing the Stable Matching Algorithm Using Lists and arrays 42 2.4 A Survey of Common Running Times 47 2.5 A More Complex Data Structure: Priority Queues 57 Solved exercises 65 Exercises 67 Notes and Further Reading 3 graphs 73 Basic Definitions and Applications 73 3.2 Graph Connectivity and Graph Traversal 78 3.3 Implementing Graph Traversal Using Queues and Stacks 87 3.4 Testing Bipartiteness: An Application of Breadth-First Search 94 3.5 Connectivity in Directed Graphs 97 Contents 3.6 Directed Acyclic Graphs and Topological Ordering 99 Solved exercises 104 Exercises 107 Notes and Further Reading 112 4 Greedy algorithms 4.1 Interval scheduling The Greedy algorithm Stays Ahead 4.2 Scheduling to Minimize Lateness: An Exchange argument 125 4.3 Optimal Caching: A More Complex Exchange Argument 131 4.4 Shortest Paths in a graph 137 4.5 The Minimum Spanning Tree Problem 142 4.6 Implementing Kruskal's Algorithm: The Union-Find Data Structure 51 4.7 Clustering 157 4.8 Huffman Codes and Data Compression 161 4.9 Minimum-Cost Arborescences: A Multi-Phase greedy Algorithm 177 Solved Exercises 183 Exercises 188 Notes and Further Reading 205 s Divide and conquer 209 5.1 A First Recurrence: The Mergesort Algorithm 210 5.2 Further Recurrence relations 214 5. 3 Counting i g nversions 221 5.4 Finding the Closest Pair of Points 225 5.5 Integer Multiplication 231 5.6 Convolutions and the Fast Fourier transform 234 Solved Exercises 242 Exercises 246 Notes and Further Reading 249 6 Dynamic Programming 251 6.1 Weighted interval Scheduling: A Recursive procedure 252 6.2 Principles of dynamic Programming: Memoization or Iteration over Subproblems 258 6.3 Segmented Least Squares: Multi-way Choices 261 The star indicates an optional section (See the Preface for more information about the relationships among the chapters and sections .) Contents 6.4 Subset Sums and Knapsacks: Adding a Variable 266 6.5 RNA Secondary Structure: Dynamic Programming over Intervals 272 6.6 Sequence Alignment 278 6.7 Sequence alignment in Linear space via Divide and Conquer 284 6.8 Shortest Paths in a Graph h290 6.9 Shortest Paths and Distance vector Protocols 297 6. 10 Negative Cycles in a Graph 301 Solved exercises 307 Exercises 312 Notes and Further Reading 335 7 Network Flow 337 7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm 338 7.2 Maximum Flows and Minimum Cuts in a Network 346 7.3 Choosing Good Augmenting Paths 352 7 he preflow-Push Maximum-Flow Algorithm: 357 7.5 A First Application: The Bipartite Matching Problem 367 7.6 Disjoint Paths in Directed and Undirected Graphs 373 7.7 Extensions to the maximum-Flow problem 378 7.8 Survey design 384 7.9 Airline Scheduling 387 7.10 Image Segmentation 391 7. 11 Project Selection 396 7.12 Baseball elimination 400 *7. 13 A Further Direction: Adding Costs to the Matching Problemly404 Solved exercises 411 Exercises 415 Notes and Further Reading 448 8 N and Computational Intractability 451 8. 1 Polynomial-Time Reductions 452 Reductions via"Gadgets": The Satisfiability problem 459 8.3 Efficient Certification and the definition of np 463 NP-Complete Problems 466 8.5 Sequencing Problems 473 8.6 Partitioning Problems 481 8.7 Graph Coloring 485 Contents 8.8 Numerical Problems 490 8.9 Co-NP and the asymmetry of NP 495 8.10 A Partial Taxonomy of Hard Problems 497 Solved exercises 500 Exercises 505 otes and Further Reading 529 9 PSPACE: A Class of Problems beyond NP 531 9.1 PSPAce 531 9.2 Some hard Problems in PSPACe 533 9.3 Solving Quantified Problems and games in Polynomial Space 536 9. 4 Solving the planning Problem in Polynomial Space 538 9.5 Proving Problems PSPACE-Complete 543 Solved exercises 547 Exercises 550 Notes and Further Reading 551 10 Extending the limits of Tractability 553 10.1 Finding Small Vertex Covers 554 10.2 Solving NP-Hard Problems on Trees 558 10.3 Coloring a Set of circular Arcs 563 *10.4 Tree Decompositions of Graphs 572 10.5 Constructing a Tree Decomposition 584 591 Exercis 594 Notes and Further Reading 598 11 Approximation algorithms 599 11.1 Greedy Algorithms and Bounds on the Optimum: A Load Balancing proble 11.2 The Center Selection problem 606 11.3 Set Cover: A General greedy heuristic 612 11. 4 The Pricing Method Vertex Cov 11.5 Maximization via the Pricing Method: The Disjoint Paths Proble 624 11.6 Linear Programming and Rounding: An Application to Vertex Cor 630 11. 7 Load Balancing Revisited: A More Advanced Lp application 637

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

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

    50积分/C币 立即下载 >