书籍详情
算法设计与分析（影印版）
作者：（美）Aho等著
出版社：中国电力出版社
出版时间：2003-11-01
ISBN：9787508318042
定价：¥55.00
购买这本书可以去
内容简介
算法研究是整个计算机科学的核心—近年来算法领域取得了大量的重要突破，这些突破包括更快速算法的发观，如快速傅里叶变换，也包括很令人吃惊的发现，即对一些自然问题，所有的算法都是无效的。这些突破引起了人们对算法研究的浓厚兴趣本书的目的是将该领域的基础研究结果结合在一起，这些统一的原理和概念将使算法设计课程更加易于教授：本书的主要内容包括：第1章简要阐述了几种计算机模型，以帮助建立可分析的结果，从而；隹确地反映出真实机器的突出特性；第2章介绍了一些高效算法中常用的基本数据结构和编程技术；第3章至第9章提供了将第2章中的基础技术应用于不同领域的示例，这几章的重点是不断开发算法，使之接近最高效：第10章至第？2章讨论了与计算复杂性有关的问题：本书的重点在于理解算法的思想过程而不是实观细节和编程技巧。非正式的、直觉性的解释经常被用来代替冗长单调的证明：本书是自包含的，并假设读者没有任何数学和编程语言方面的专业背景本书适用于本科生和研究生的算法设计课程—每章后面提供了大量的练习—练习根据难度进行了分级，读者可以根据不同的需要选择：AlfredV．Aho是朗讯科技贝尔实验室的研发副总裁Aho获得了加拿大多伦多大学的学士学位和美国普林斯顿大学的硕士和博士学位：Aho是美国国家工程院院士，ACM、IEEE、AAAS的Fellow，并且担任ACM自动控制与可计算性理论特别兴趣组的副主席和美国国家科学基金会计算机与信息技术顾问委员会主席JohnE，Hopcroft是美国康乃尔大学的教授、工程院院长：他获得了美国斯坦福大学的硕士和博士学位。Hopcroft是美国国家工程院院士，ACM、IEEE、AAAS的Fellow，并且获得了1986年度ACM图灵奖他还是多个国际著名刊物的主编。JeffreyD．Ullman是美国斯坦福大学计算机科学系的教授—他获得了美国哥伦比亚大学的学士学位和普林斯顿大学的博士学位：UIIman是美国国家工程院院士，ACM的Fellow—他获得1998年度ACMKarlV．Karlstrom的杰出教育成就奖和2000年度的Knuth奖金。
作者简介
Alfred V．Aho是朗讯科技贝尔实验室的研发副总裁Aho获得了加拿大多伦多大学的学士学位和美国普林斯顿大学的硕士和博士学位：Aho是美国国家工程院院士，ACM、IEEE、AAAS的Fellow，并且担任ACM自动控制与可计算性理论特别兴趣组的副主席和美国国家科学基金会计算机与信息技术顾问委员会主席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
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
猜您喜欢
