算法设计与分析（影印版）

　　1 Models of Computation
　　1.1 Algorithms and their complexity
　　1.2 Random 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 computation: the Turing machine
　　1.7 Relationship between the Turing machine and RAM models
　　1.8 Pidgin ALGOL-a high-level language
　　2 Design of Emcient Algorithms
　　2.1 Dam structures: lists, queues, and stacks
　　2.2 Set representations
　　2.3 Graphs
　　2.4 Trees
　　2.5 Recursion
　　2.6 Divide-and-conquer
　　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 Quicksoft-an O(n log n） expected time sort
　　3.6 Order statistics
　　3.7 Expected time for order statistics
　　4 Data Structures for Set Manipulation Problems
　　4.1 Fundamental operations on sets
　　4.2 Hashinn
　　4.3 Binary search
　　4.4 Binary search trees
　　4.5 Optimal binary search 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
　　S. 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 z
　　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 Strassens matrix-multiplication algorithm
　　6.3 Inversion of matrices
　　6.4 LU P 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 inverse
　　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 Aritlunetic
　　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 Euclids algorithm
　　8.9 An asymptotically fast algorithm for polynomial GCDs
　　8.10 Integer GCDs
　　8.11 Chinese remaindering revisited
　　8.12 Sparse polynomials
　　9 Pattern-Matchino 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 Nondeterministic 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-line code revisited
　　12.3 A matrix formulation of problems
　　12.4 A row-oriented lower bound on multiplications
　　12.5 A coluum-oricnted lower bound on multiplications
　　12.6 A row-and-column-oriented bound on multiplications
　　12.7 Preconditioning
　　Bibliography
　　Index

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