Alfred V．Aho是朗訊科技貝爾實驗室的研發(fā)副總裁Aho獲得了加拿大多倫多大學的學士學位和美國普林斯頓大學的碩士和博士學位：Aho是美國國家工程院院士，ACM、IEEE、AAAS的Fellow，并且擔任ACM自動控制與可計算性理論特別興趣組的副主席和美國國家科學基金會計算機與信息技術(shù)顧問委員會主席JohnE，Hopcroft是美國康乃爾大學的教授、工程院院長：他獲得了美國斯坦福大學的碩士和博士學位。Hopcroft是美國國家工程院院士，ACM、IEEE、AAAS的Fellow，并且獲得了1986年度ACM圖靈獎 他還是多個國際著名刊物的主編。 Jeffrey D．Ullman是美國斯坦福大學計算機科學系的教授—他獲得了美國哥倫比亞大學的學士學位和普林斯頓大學的博士學位：UIIman是美國國家工程院院士，ACM的Fellow—他獲得1998年度ACM KarlV．Karlstrom的杰出教育成就獎和2000年度的Knuth獎金。
圖書目錄
1 Models of Computation 1.1 Algorithms and their complexity 1.2 Radom access machines 1.3 Computational complexity of RAM programs 1.4 A stored program model 1.5 Abstractions of the RAM 1.6 A primitive model of computatoin:the Turing machine 1.7 Relationship between the Turing machine and RAM models 1.8 Pidgin ALGOL-a high-level language 2 Desigh of Efficient Algorithms 2.1 Data structures:lists, queues,and stacks 2.2 Set representatoins 2.3 Graphs 2.4 Trees 2.5 Recursion 2.6 Deivde-and-comquer 2.7 Balancing 2.8 Dynamic programming 2.9 Epilogue 3 Sorting and Order Statistics 3.1 The sorting problem 3.2 Radix sorting 3.3 Sorting by comparisons 3.4 Heapsort-an O(n log n)comparison sort 3.5 Quicksort-an O(n log n)expected time sort 3.6 Order staistics 3.7 Expected time for order statistics 4 Data Structures for Set Manipulation Problems 4.1 Fundamental operatoins on sets 4.2 hashing 4.3 binary search 4.4 Binary search trees 4.5 Optimal binary serch trees 4.6 A simple disjoint-set union algorithm 4.7 Tree structures for the UNION-FIND problem 4.8 Applications and extensions of the UNION-FIND algorithm 4.9 Balanced tree schemes 4.10 Dictionaries and priority queues 4.11 Mergeable heaps 4.12 Concatenable queues 4.13 Partitioning 4.14 Chapter summary 5 Algorithms on Graphs 5.1 Minimum-cost spanning trees 5.2 Depth-first search 5.3 Biconnectivity 5.4 Depth-first search of a directed graph 5.5 Strong Connectivity 5.6 Path-finding problems 5.7 A transitive closure algorithm 5.8 A shortest-path algorithm 5.9 Path problems and matrix multiplication 5.10 Single-source problems 5.11 Dominators in a directed acyclic graph:putting the concepts together 6 Matrix Multiplication and Related Operations 6.1 Basics 6.2 Strassen's matrix-multiplication algorithm 6.3 Inversion of matrices 6.4 LUP decomposition of matrices 6.5 Applications of LUP decomposition 6.6 Boolean matrix multiplication 7 The Fast Fourier Transform and its Applications 7.1 The discrete Fourier transform and its iverse 7.2 The fast Fourier transform algorithm 7.3 The FFT using bit operations 7.4 Products of polynomials 7.5 The Schonhage-Strassen integer-multiplication algorithm 8 Integer and Polynomial Arithmetic 8.1 The similarity between integers and polynomials 8.2 Integer multiplication and division 8.3 Polynomial multiplication and division 8.4 Modular arithmetic 8.5 Modular polynomial arithmetic and polynomial evaluation 8.6 Chinese remaindering 8.7 Chinese remaindering and interpolation of polynomials 8.8 Greatest common divisors and Euclid's algorithm 8.9 An asymptotically fast algorithm for polynomial GCD's 8.10 Integer GCD's 8.11 Chinese remaindering revisited 8.12 Sparse polynomials 9 Pattern-Matching Algorithms 9.1 Finite automata and regular expressions 9.2 Recognition of regular expression patterns 9.3 Recognition of substrings 9.4 Two-way deterministic pushdown automata 9.5 Position trees and substring identifiers 10 NP-Complete Problems 10.1 Nondterministic Turing machines 10.2 The classes P and NP 10.3 Languages and problems 10.4 NP-completeness of the satisfiability problem 10.5 Additional NP-complete problems 10.6 Polynomial-space-bounded problems 11 Some Provably Intractable Problems 11.1 Complexity hierarchies 11.2 The space hierarchy for deterministic Turing machines 11.3 A problem requiring exponential time and space 11.4 A nonelementary problem 12 Lower Bounds on Numbers of Arithmetic Operations 12.1 Fields 12.2 Straight-light code revisited 12.3 A matrix formulation of problems 12.4 A row-orented lower bound on multiplications 12.5 A column-oriented lower bound on multiplications 12.6 A row-and-column-oriented bound on multiplications 12.7 Preconditioning Bibliography Index
鄂公網(wǎng)安備 42010302001612號 