算法设计与分析

章节摘录

插图：

前言

The study of algorithms is at the very heart of computer science. In recent years a number of significant advances in the field of algorithms have been made. These advances have ranged from the development of faster algorithms, such as the fast Fourier transform, to the startling discovery of certain natural problems for which all algorithms are inefficient. These results have kindled considerable interest in the study of algorithms, and the area of algorithm design and analysis has blossomed into a field of intense interest. The intent of this book is to bring together the fundamental results in this area, so the unifying principles and underlying concepts of algorithm design may more easily be taught.THE SCOPE OF THE BOOKTo analyze the performance of an algorithm some model of a computer is necessary. Our book begins by formulating several computer models which are simple enough to establish analytical results but which at the same time accurately reflect the salient features of real machines. These models include the random access register machine, the random access stored program machine, and some specialized variants of these. The Turing machine is introduced in order to prove the exponential lower bounds on efficiency in Chapters 10 and 11. Since the trend in program design is away from machine language, a high-level language called Pidgin ALGOL is introduced as the main vehicle for describing algorithms. The complexity of a Pidgin ALGOL program is related to the machine models.The second chapter introduces basic data structures and programming techniques often used in efficient algorithms. It covers the use of lists, pushdown stores, queues, trees, and graphs. Detailed explanations of recursion, divide-and-conquer, and dynamic programming are given, along with examples of their use.Chapters 3 to 9 provide a sampling of the diverse areas to which the fundamental techniques of Chapter 2 can be applied. Our emphasis in these chapters is on developing algorithms that are asymptotically the most efficient known. Because of this emphasis, some of the algorithms presented are suitable only for inputs whose size is much larger than what is currently encountered in practice. This is particularly true of some of the matrix multiplication algorithms in Chapter 6, the Schonhage-Strassen integer-multiplication algorithm of Chapter 7, and some of the polynomial and integer algorithms of Chapter 8.On the other hand, most of the sorting algorithms of Chapter 3, the searching algorithms of Chapter 4, the graph algorithms of Chapter 5, the fast Fourier transform of Chapter 7, and the string-matching algorithms of Chapter 9 are widely used, since the sizes of inputs for which these algorithms are efficient are sufficiently small to be encountered in many practical situations.Chapters 10 through 12 discuss lower bounds on computational complexity. The inherent computational difficulty of a problem is of universal interest, both to program design and to an understanding of the nature of computation. In Chapter 10 an important class of problems, the NP-complete problems, is studied. All problems in this class are equivalent in computational difficulty, in that if one problem in the class has an efficient （polynomial time-bounded） solution, then all problems in the class have efficient solutions. Since this class of problems contains many practically important and wellstudied problems, such as the integer-programming problem and the traveling salesman problem, there is good reason to suspect that no problem in this class can be solved efficiently. Thus, if a program designer knows that the problem for which he is trying to find an efficient algorithm is in this class, then he may very well be content to try heuristic approaches to the problem. In spite of the overwhelming empirical evidence to the contrary, it is still an open question whether NP-complete problems admit of efficient solutions.In Chapter 11 certain problems are defined for which we can actually prove that no efficient algorithms exist. The material in Chapters 10 and 11 draws heavily on the concept of Turing machines introduced in Sections 1.6 and 1.7.In the final chapter of the book we relate concepts of computational difficulty to notions of linear independence in vector spaces. The material in this chapter provides techniques for proving lower bounds for much simpler problems than those considered in Chapters 10 and 11.THE USE OF THE BOOK This book is intended as a first course in the design and analysis of algorithms. The emphasis is on ideas and ease of understanding rather than implementation details or programming tricks. Informal, intuitive explanations are often used in place of long tedious proofs. The book is self-contained and assumes no specific background in mathematics or programming languages. However, a certain amount of maturity in being able to handle mathematical concepts is desirable, as is some exposure to a higher-level programming language such as FORTRAN or ALGOL. Some knowledge of linear algebra is needed for a full understanding of Chapters 6, 7, 8, and 12.This book has been used in graduate and undergraduate courses in algorithm design. In a one-semester course most of Chapters 1-5 and 9-10 were covered, along with a smattering of topics from the remaining chapters. In introductory courses the emphasis was on material from Chapters 1-5, but Sections 1.6, 1.7, 4.13, 5.11, and Theorem 4.5 were generally not coyered. The book can also be used in more advanced courses emphasizing the theory of algorithms. Chapters 6-12 could serve as the foundation for such a course.Numerous exercises have been provided at the end of each chapter to provide an instructor with a wide range of homework problems. The exercises are graded according to difficulty. Exercises with no stars are suitable for introductory courses, singly starred exercises for more advanced courses, and doubly starred exercises for advanced graduate courses. The bibliographicnotes at the end of every chapter attempt to point to a published source for each of the algorithms and results contained in the text and the exercises.ACKNOWLEDGMENTSThe mateRIal in this book has been derived from class notes for courses taught by the authors at Cornell, Princeton, and Stevens Institute of Technology. The authors would like to thank the many people who have critically read various portions of the manuscript and offered many helpful suggestions. In particular we would like to thank Kellogg Booth, Stan Brown, Steve Chen, Allen Cypher,Arch Davis, Mike Fischer, Hania Gajewska, Mike Garey, Udai Gupta,Mike Harrison, Matt Hecht, Harry Hunt, Dave Johnson, Marc Kaplan, Don Johnson, Steve Johnson, Brian Kernighan, Don Knuth, Richard Ladner, Anita LaSalle, Doug Mcllroy, Albert Meyer, Christos Papadimitriou, BillPlauger, John Savage, Howard Siegel, Ken Steiglitz, Larry Stockmeyer, Tom Szymanski, and Theodore Yen.Special thanks go to Gemma Carnevale, Pauline Cameron, Hannah Kresse, Edith Purser, and Ruth Suzuki for their cheerful and careful typing of the manuscript.The authors are also grateful to Bell Laboratories and Cornell, Princeton, and the University of California at Berkeley for providing facilities for the preparation of the manuscript.

内容概要

Alfred V.Aho,朗讯科技贝尔实验室的研发副总裁。Aho获得了加拿大多伦多大学的学士学位和美国普林斯顿大学的硕士和博士学位。Aho是美国国家工程院院士，ACM、IEEE、AAAS的Fellow，并且担任ACM自动控制与可计算性理论特别兴趣组的副主席和美国国家科学基金会计算机与信息技术顾问委员会主席。John E.Hopcroft,美国康乃尔大学的教授、工程院院长他获得了美国斯坦福大学的硕士和博士学位Hopcroft是美国国家工程院院士，ACM、IEEE、AAAS的Fellow，并且获得了1986年度ACM图灵奖，他还是多个国际著名刊物的主编。Jeffrev D.UIlman,美国斯坦福大学计算机科学系的教授他获得了美国哥伦比亚大学的学士学位和普林斯顿大学的博士学位、UlIman是美国国家工程院院士，ACM的Fellow他获得1998年度ACM Karl V.Karlstrom的杰出教育成就奖和2000年度的Knuth奖金。

书籍目录

1 Models of Computation1.1 Algorithms and their complexity1.2 Random access machines1.3 Computational complexity of RAM programs1.4 A stored program model1.5 Abstractions of the RAM1.6 A primitive model of computation: the Turing machine1.7 Relationship between the Turing machine and RAM models1.8 Pidgin ALGOL-a high-level language2 Design of Emcient Algorithms2.1 Dam structures: lists, queues, and stacks2.2 Set representations2.3 Graphs2.4 Trees2.5 Recursion2.6 Divide-and-conquer2.7 Balancing2.8 Dynamic programming2.9 Epilogue3 Sorting and Order Statistics3.1 The sorting problem3.2 Radix sorting3.3 Sorting by comparisons3.4 Heapsort-an O（n log n） comparison sort3.5 Quicksoft-an O(n log n） expected time sort3.6 Order statistics3.7 Expected time for order statistics4 Data Structures for Set Manipulation Problems4.1 Fundamental operations on sets4.2 Hashinn4.3 Binary search4.4 Binary search trees4.5 Optimal binary search trees4.6 A simple disjoint-set union algorithm4.7 Tree structures for the UNION-FIND problem4.8 Applications and extensions of the UNION-FIND algorithm4.9 Balanced tree schemes4.10 Dictionaries and priority queues4.11 Mergeable heaps4.12 Concatenable queues4.13 Partitioning4.14 Chapter summary5 Algorithms on GraphsS. 1 Minimum-cost spanning trees5,2 Depth-first search5.3 Biconnectivity5.4 Depth-first search of a directed graph5.5 Strong connectivity5.6 Path-finding problems5.7 A transitive closure algorithm5.8 A shortest-path algorithm z5.9 Path problems and matrix multiplication5.10 Single-source problems5.11 Dominators in a directed acyclic graph: putting the concepts together6 Matrix Multiplication and Related Operations6.1 Basics6.2 Strassen's matrix-multiplication algorithm6.3 Inversion of matrices6.4 LU P decomposition of matrices6.5 Applications of LUP decomposition6.6 Boolean matrix multiplication7 The Fast Fourier Transform and its Applications7.1 The discrete Fourier transform and its inverse7.2 The fast Fourier transform algorithm7.3 The FFT using bit operations7.4 Products of polynomials7.5 The Schonhage-Strassen integer-multiplication algorithm8 Integer and Polynomial Aritlunetic8.1 The similarity between integers and polynomials8.2 Integer multiplication and division8.3 Polynomial multiplication and division8.4 Modular arithmetic8.5 Modular polynomial arithmetic and polynomial evaluation8.6 Chinese remaindering8.7 Chinese remaindering and interpolation of polynomials8.8 Greatest common divisors and Euclid's algorithm8.9 An asymptotically fast algorithm for polynomial GCD's8.10 Integer GCD's8.11 Chinese remaindering revisited8.12 Sparse polynomials9 Pattern-Matchino Algorithms9.1 Finite automata and regular expressions9.2 Recognition of regular expression patterns9.3 Recognition of substrings9.4 Two-way deterministic pushdown automata9.5 Position trees and substring identifiers10 NP-Complete Problems10.1 Nondeterministic Turing machines10.2 The classes P and NP10.3 Languages and problems10.4 NP-completeness of the satisfiability problem10.5 Additional NP-complete problems10.6 Polynomial-space-bounded problems11 Some Provably Intractable Problems11.1 Complexity hierarchies11.2 The space hierarchy for deterministic Turing machines11.3 A problem requiring exponential time and space11.4 A nonelementary problem12 Lower Bounds on Numbers of Arithmetic Operations12.1 Fields12.2 Straight-line code revisited12.3 A matrix formulation of problems12.4 A row-oriented lower bound on multiplications12.5 A coluum-oricnted lower bound on multiplications12.6 A row-and-column-oriented bound on multiplications12.7 PreconditioningBibliographyIndex

编辑推荐

《算法设计与分析(影印版)》适用于本科生和研究生的算法设计课程每章后面提供了大量的练习练习根据难度进行了分级，读者可以根据不同的需要选择。

作者简介

《算法设计与分析(影印版)》的重点在于理解算法的思想过程而不是实现细节和编程技巧，非正式的、直觉性的解释经常被用来代替冗长单调的证明《算法设计与分析(影印版)》是自包含的，并假设读者没有任何数学和编程语言方面的专业背景。算法研究是整个计算机科学的核心。近年来算法领域取得了大量的重要突破这些突破包括更快速算法的发现，如快速博里叶变换，也包括很令人吃惊的发现，即对一些自然问题，所有的算法都是无效的这些突破引起了人们对算法研究的浓厚兴趣《算法设计与分析(影印版)》的目的是将该领域的基础研究结果结合在一起，这些统一的原理和概念将使算法设计课程更加易于教授。

《算法设计与分析(影印版)》的主要内容包括：第1章简要阐述了几种计算机模型，以帮助建立可分析的结果，从而准确地反映出真实机器的突出特性：第2章介绍了一些高效算法中常用的基本数据结构和编程技术；第3章至第9章提供了将第2章中的基础技术应用于不同领域的示例，这几章的重点是不断开发算法，使之接近最高效；第10章至第12章讨论了与计算复杂性有关的问题？

图书封面

---

 算法设计与分析下载

---