算法设计与分析基础 (影印版)(第3版) PDF 高清电子书 免费下载 完整版 在线阅读- 高飞网
现在已经04点48分了,请注意休息
算法设计与分析基础 (影印版)

算法设计与分析基础 (影印版)(第3版)

Anany Levitin
算法
读者:                   ...
  《算法设计与分析基础 (第3版)(影印版)》在讲述算法设计技术时采用了新的分类方法,在讨论分析方法时条分缕析,形成了连贯有序、耳目一新的风格。为便于学生掌握,本书涵盖算法入门课程的全部内容,更注重对概念(而非形式)的理解。书中通过一些流行的谜题来激发学生的兴趣,帮助他们加强和提高解决算法问题的能力。每章小结、习题提示和详细解答,形成了非常鲜明的教学特色。

New to the Third Edition xvii   
Preface xix   
1Introduction   
1.1 What Is an Algorithm?   
Exercises 1.1   
1.2 Fundamentals of Algorithmic Problem Solving   
Understanding the Problem   
Ascertaining the Capabilities of the Computational Device   
Choosing between Exact and Approximate Problem Solving   
Algorithm Design Techniques   
Designing an Algorithm and Data Structures   
Methods of Specifying an Algorithm   
Proving an Algorithm's Correctness   
Analyzing an Algorithm   
Coding an Algorithm   
Exercises 1.2   
1.3 Important Problem Types   
Sorting   
Searching   
String Processing   
Graph Problems   
Combinatorial Problems   
Geometric Problems   
Numerical Problems   
Exercises 1.3   
1.4 Fundamental Data Structures   
Linear Data Structures   
Graphs   
Trees   
Sets and Dictionaries   
Exerises 1.4   
2 Fundamentals of the Analysis of Algorithm Efficiency   
2.1 The Analysis Framework   
Measuring an Input's Size   
Units for Measuring Running Time   
Orders of Growth   
Worst-Case, Best-Case, and Average-Case Efficiencies   
Recapitulation of the Analysis Framework   
Exercises 2.1   
2.2 Asymptotic Notations and Basic Efficiency Classes   
Informal Introduction   
O   
Useful Property Involving the Asymptotic Notations   
Using Limits for Comparing Orders of Growth   
Basic Efficiency Classes   
Exercises 2.2   
2.3 Mathematical Analysis of Nonrecursive Algorithms   
Exercises 2.3   
2.4 Mathematical Analysis of Recursive Algorithms   
Exercises 2.4   
2.5 Example: Computing the nth Fibonacci Number   
Exercises 2.5   
2.6 Empirical Analysis of Algorithms   
Exercises 2.6   
2.7 Algorithm Visualization   
3 Brute Force and Exhaustive Search   
3.1 Selection Sort and Bubble Sort   
Selection Sort   
Bubble Sort   
Exercises 3.1   
3.2 Sequential Search and Brute-Force String Matching   
Sequential Search   
Brute-Force String Matching   
Exercises 3.2   
3.3 Closest-Pair and Convex-Hull Problems by Brute Force   
Closest-Pair Problem   
Exercises 3.3   
3.4 Exhaustive Search   
Exercises 3.4   
3.5 Depth-First Search and Breadth-First Search   
Depth-First Search   
Breadth-First Search   
Exercises 3.5   
4 Decrease-and-Conquer   
4.1 Insertion Sort   
Exercises 4.1   
4.2 Topological Sorting   
Exercises 4.2   
4.3 Algorithms for Generating Combinatorial Objects   
Generating Permutations   
Generating Subsets   
Exercises 4.3   
4.4 Decrease-by-a-Constant-Factor Algorithms   
Binary Search   
Fake-Coin Problem   
Russian Peasant Multiplication   
Josephus Problem   
Exercises 4.4   
4.5 Variable-Size-Decrease Algorithms   
Computing a Median and the Selection Problem   
Interpolation Search   
Searching and Insertion in a Binary Search Tree   
The Game of Nim   
Exercises 4.5   
5 Divide-and-Conquer   
5.1 Mergesort   
Exercises 5.1   
5.2 Quicksort   
Exercises 5.2   
5.3 Binary Tree Traversals and Related Properties   
Exercises 5.3   
5.4 Multiplication of Large Integers and   
Multiplication of Large Integers   
Exercises 5.4   
5.5 The Closest-Pair and Convex-Hull Problems   
by Divide-and-Conquer   
The Closest-Pair Problem   
Exercises 5.5   
6 Transform-and-Conquer   
6.1 Presorting   
Exercises 6.1   
6.2 Gaussian Elimination   
LU Decomposition   
Computing a Matrix Inverse   
Computing a Determinant   
Exercises 6.2   
6.3 Balanced Search Trees   
AVL Trees   
2-3 Trees   
Exercises 6.3   
6.4 Heaps and Heapsort   
Notion of the Heap   
Heapsort   
Exercises 6.4   
6.5 Horner's Rule and Binary Exponentiation   
Horner's Rule   
Binary Exponentiation   
Exercises 6.5   
6.6 Problem Reduction   
Computing the Least Common Multiple   
Counting Paths in a Graph   
Reduction of Optimization Problems   
Linear Programming   
Reduction to Graph Problems   
Exercises 6.6   
7 Space and Time Trade-Offs   
7.1 Sorting by Counting   
Exercises 7.1   
7.2 Input Enhancement in String Matching   
Horspool's Algorithm   
Boyer-Moore Algorithm   
Exercises 7.2   
7.3 Hashing   
Open Hashing (Separate Chaining)   
Closed Hashing (Open Addressing)   
Exercises 7.3   
7.4 B-Trees   
Exercises 7.4   
8 Dynamic Programming   
8.1 Three Basic Examples   
Exercises 8.1   
8.2 The and Memory Functions   
Memory Functions   
Exercises 8.2   
8.3 Optimal Binary Search Trees   
Exercises 8.3   
8.4 Warshall's and Floyd's Algorithms   
Warshall's Algorithm   
Floyd's Algorithm for the All-Pairs Shortest-Paths Problem   
Exercises 8.4   
9 Greedy Technique   
9.1 Prim's Algorithm   
Exercises 9.1   
9.2 Kruskal's Algorithm   
Disjoint Subsets and Union-Find Algorithms   
Exercises 9.2   
9.3 Dijkstra's Algorithm   
Exercises 9.3   
9.4 Huffman Trees and Codes   
Exercises 9.4   
10 Iterative Improvement   
10.1 The Simplex Method   
Geometric Interpretation of Linear Programming   
An Outline of the Simplex Method   
Further Notes on the Simplex Method   
Exercises 10.1   
10.2 The Maximum-Flow Problem   
Exercises 10.2   
10.3 Maximum Matching in Bipartite Graphs   
Exercises 10.3   
10.4 The Stable Marriage Problem   
Exercises 10.4   
11 Limitations of Algorithm Power   
11.1 Lower-Bound Arguments   
Trivial Lower Bounds   
Information-Theoretic Arguments   
Adversary Arguments   
Problem Reduction   
Exercises 11.1   
11.2 Decision Trees   
Decision Trees for Sorting   
Decision Trees for Searching a Sorted Array   
Exercises 11.2   
11.3 P, NP, and NP-Complete Problems   
P and NP Problems   
NP-Complete Problems   
Exercises 11.3   
11.4 Challenges of Numerical Algorithms   
Exercises 11.4   
12 Coping with the Limitations of Algorithm Power   
12.1 Backtracking   
n-Queens Problem   
Hamiltonian Circuit Problem   
Subset-Sum Problem   
General Remarks   
Exercises 12.1   
12.2 Branch-and-Bound   
Exercises 12.2   
12.3 Approximation Algorithms for NP-Hard Problems   
Approximation Algorithms for the   
Approximation Algorithms for the   
Exercises 12.3   
12.4 Algorithms for Solving Nonlinear Equations   
Bisection Method   
Method of False Position   
Newton's Method   
Exercises 12.4   
Epilogue   
APPENDIX A   
Useful Formulas for the Analysis of Algorithms   
Properties of Logarithms   
Combinatorics   
Important Summation Formulas   
Sum Manipulation Rules   
Approximation of a Sum by a Definite Integral   
Floor and Ceiling Formulas   
Miscellaneous   
APPENDIX B   
Short Tutorial on Recurrence Relations   
Sequences and Recurrence Relations   
Methods for Solving Recurrence Relations   
Common Recurrence Types in Algorithm Analysis   
References   
Hints to Exercises   
Index