算法設(shè)計與分析

前言

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.

內(nèi)容概要

跳過高深的理論和數(shù)學(xué)公式，直擊現(xiàn)實世界中的數(shù)字設(shè)計和測試工作。了解使用策略，滿足對品質(zhì)、可靠性及成本控制的業(yè)務(wù)需求，使你能在典型的高壓力環(huán)境下按期完成任務(wù)。本書將幫助你優(yōu)化設(shè)計，在工程上權(quán)衡某些資源（如硅片面積、工作頻率和功率消耗）間的關(guān)系；在整體上實現(xiàn)的測試成本、面市時間和量產(chǎn)時間的平衡。此外，還將通過特定的自動化測試仿真生成工具提升你的效率。
書中包括的索引使你能夠根據(jù)自己的需要，直接閱讀你所關(guān)注的內(nèi)容。主要內(nèi)容包括：
●設(shè)計核心，關(guān)注嵌入核心和嵌入存儲器
●系統(tǒng)集成和超大規(guī)模集成電路的設(shè)計問題
●AC掃描、正常速度掃描和嵌入式可測試性設(shè)計
●內(nèi)建、自測試、含內(nèi)存BIST、邏輯BIST及掃描BIST
●虛擬測試套接字和隔離測試
●重用設(shè)計，包括重用向量和重用核心
●用VSIA和IEEE P1500標(biāo)準處理測試問題
    書中穿插的整幅圖解直接來自作者的教學(xué)材料。通過為書中的每一部分列出流程圖、工程圖表和內(nèi)容摘要，使得讀者能夠更快更容易地學(xué)習(xí)和查找。本書是與設(shè)計和測試工作相關(guān)的工程師和管理員所必備的資料書籍。

作者簡介

Alfred V.Aho,朗訊科技貝爾實驗室的研發(fā)副總裁。Aho獲得了加拿大多倫多大學(xué)的學(xué)士學(xué)位和美國普林斯頓大學(xué)的碩士和博士學(xué)位。Aho是美國國家工程院院士，ACM、IEEE、AAAS的Fellow，并且擔(dān)任ACM自動控制與可計算性理論特別興趣組的副主席和美國國家科學(xué)基金會計算機與信息技術(shù)顧問委員會主席。John E.Hopcroft,美國康乃爾大學(xué)的教授、工程院院長他獲得了美國斯坦福大學(xué)的碩士和博士學(xué)位Hopcroft是美國國家工程院院士，ACM、IEEE、AAAS的Fellow，并且獲得了1986年度ACM圖靈獎，他還是多個國際著名刊物的主編。Jeffrev D.UIlman,美國斯坦福大學(xué)計算機科學(xué)系的教授他獲得了美國哥倫比亞大學(xué)的學(xué)士學(xué)位和普林斯頓大學(xué)的博士學(xué)位、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

章節(jié)摘錄

插圖：

編輯推薦

《算法設(shè)計與分析(影印版)》適用于本科生和研究生的算法設(shè)計課程每章后面提供了大量的練習(xí)練習(xí)根據(jù)難度進行了分級，讀者可以根據(jù)不同的需要選擇。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    算法設(shè)計與分析 PDF格式下載

---