书籍详情
计算机算法的设计与分析（英文版）
作者：（美）阿霍
出版社：机械工业出版社
出版时间：2005-11-01
ISBN：9787111177753
定价：¥48.00
购买这本书可以去
内容简介
《计算机算法的设计与分析（英文版）》是一部经典著作，着重介绍了计算机算法设计领域的统一原则和基本概念。书中深入分析了一些计算机模型上的算法，介绍了一些有效算法常用的数据结构和编程技术，为读者提供了有关递归方法、分治方法和动态规划方面的详细实例和实际应用，并致力于更有效算法的设计和开发。同时，对NP完全等问题能否有效求解进行了分析，并探索了应用启发算法解决问题的途径。另外，本书还提供了大量富有指导意义的习题。《计算机算法的设计与分析（英文版）》可以作为高等院校计算机专业本科生和研究生算法设计课程的教材，也可以作为计算机算法理论中更高级课程的教材。
作者简介
阿霍AlfredV.Aho于普林斯顿大学获得博士学位，现任贝尔实验室基础科学研究院副院长、计算机科学研究中心主任、ACM自动控制与可计算性理论特别兴趣组副主席以及美国国家科学基金会计算机与信息技术顾问委员会主席。
目录
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 Efficient Algorithms
2.1 Data 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 Quicksort-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 Hashing
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
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 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 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 Noncleterministic Turing machines
10.2 The classes and
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
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 Efficient Algorithms
2.1 Data 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 Quicksort-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 Hashing
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
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 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 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 Noncleterministic Turing machines
10.2 The classes and
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
猜您喜欢
