算法设计手册(第2版)(大学计算机教育国外著名教材系列(影印版))(The Algorithm Design Manual Second Edition)

基本信息·出版社：清华大学出版社

·页码：707 页

·出版日期：2009年09月

·ISBN：9787302207276

·条形码：9787302207276

·包装版本：第2版

·装帧：平装

·开本：16

·正文语种：英语

·丛书名：大学计算机教育国外著名教材系列(影印版)

·外文书名：The Algorithm Design Manual Second Edition

产品信息有问题吗？请帮我们更新产品信息。

内容简介《算法设计手册(第2版)》是算法设计畅销书的最新版本，是设计实用且高效算法的最全面指导书。《算法设计手册(第2版)》揭密了算法的设计与分析，以简单易懂的写作风格，介绍了各种算法技术，着重强调了算法分析，全书包括两大部分，“技术”部分介绍了设计和分析计算机算法的各种方法，“资源”部分给出了大量的参考资源，以及算法实现的各种资源，此外，在作者的个人网址http：／／www．CS．sunysb．edu／～algorith／I-还提供了各种教学资源和参考材料，这些资源对读者很有参考价值。

《算法设计手册(第2版)》可以作为算法设计课程的主教材，也是程序人员、研究人员和学生的常备参考书。

编辑推荐《算法设计手册(第2版)》：大学计算机教育国外著名教材系列(影印版)

目录

Ⅰ Practical Algorithm Design

1 Introduction to Algorithm Design

1.1 Robot Tour Optimization

1.2 Selecting the Right Jobs

1.3 Reasoning about Correctness

1.4 Modeling the Problem

1.5 About the Wax Stories

1.6 War Story: Psychic Modeling

1.7 Exercises

2 Algorithm Analysis

2.1 The RAM Model of Computation

2.2 The Big Oh Notation

2.3 Growth Rates and Dominance Relations

2.4 Working with the Big Oh

2.5 Reasoning About Efficiency

2.6 Logarithms and Their Applications

2.7 Properties of Logarithms

2.8 War Story: Mystery of the Pyramids

2.9 Advanced Analysis (*)

2.10 Exercises

3 Data Structures

3.1 Contiguous vs. Linked Data Structures

3.2 Stacks and Queues

3.3 Dictionaries

3.4 Binary Search Trees

3.5 Priority Queues

3.6 War Story: Stripping Triangulations

3.7 Hashing and Strings

3.8 Specialized Data Structures

3.9 War Story: String'em Up

3.10 Exercises

4 Sorting and Searching

4.1 Applications of Sorting

4.2 Pragmatics of Sorting

4.3 Heapsort: Fast Sorting via Data Structures

4.4 War Story: Give me a Ticket on an Airplane

4.5 Mergesort: Sorting by Divide-and-Conquer

4.6 Quicksort: Sorting by Randomization

4.7 Distribution Sort: Sorting via Bucketing

4.8 War Story: Skiena for the Defense

4.9 Binary Search and Related Algorithms

4.10 Divide-and-Conquer

4.11 Exercises

5 Graph Traversal

5.1 Flavors of Graphs

5.2 Data Structures for Graphs

5.3 War Story: I was a Victim of Moore's Law

5.4 War Story: Getting the Graph

5.5 Traversing a Graph

5.6 Breadth-First Search

5.7 Applications of Breadth-First Search

5.8 Depth-First Search

5.9 Applications of Depth-First Search

5.10 Depth-First Search on Directed Graphs

5.11 Exercises

6 Weighted Graph Algorithms

6.1 Minimum Spanning Trees

6.2 War Story: Nothing but Nets

6.3 Shortest Paths

6.4 War Story: Dialing for Documents

6.5 Network Flows and Bipartite Matching

6.6 Design Graphs, Not Algorithms

6.7 Exercises

7 Combinatorial Search and Heuristic Methods

7.1 Backtracking

7.2 Search Pruning

7.3 Sudoku

7.4 War Story: Covering Chessboards

7.5 Heuristic Search Methods

7.6 War Story: Only it is Not a Radio

7.7 War Story: Annealing Arrays

7.8 Other Heuristic Search Methods

7.9 Parallel Algorithms

7.10 War Story: Going Nowhere Fast

7.11 Exercises

8 Dynamic Programming

8.1 Caching vs. Computation

8.2 Approximate String Matching

8.3 Longest Increasing Sequence

8.4 War Story: Evolution of the Lobster

8.5 The Partition Problem

8.6 Parsing Context-Free Grammars

8.7 Limitations of Dynamic Programming: TSP

8.8 War Story: What's Past is Prolog

8.9 War Story: Text Compression for Bar Codes

8.10 Exercises

9 Intractable Problems and Approximation Algorithms

9.1 Problems and Reductions

9.2 Reductions for Algorithms

9.3 Elementary Hardness Reductions ..

9.4 Satisfiability

9.5 Creative Reductions

9.6 The Art of Proving Hardness

9.7 War Story: Hard Against the Clock

9.8 War Story: And Then I Failed

9.9 P vs. NP

9.10 Dealing with NP-complete Problems

9.11 Exercises

10 How to Design Algorithms

Ⅱ The Hitchhiker's Guide to Algorithms

11 A Catalog of Algorithmic Problems

12 Data Structures

12.1 Dictionaries

12.2 Priority Queues

12.3 Suffix Trees and Arrays

12.4 Graph Data Structures

12.5 Set Data Structures

12.6 Kd-Trees

13 Numerical Problems

13.1 Solving Linear Equations

13.2 Bandwidth Reduction

13.3 Matrix Multiplication

13.4 Determinants and Permanents

13.5 Constrained and Unconstrained Optimization

13.6 Linear Programming

13.7 Random Number Generation

13.8 Factoring and Primality Testing

13.9 Arbitrary-Precision Arithmetic

13.10 Knapsack Problem

13.11 Discrete Fourier Transform

14 Combinatorial Problems

14.1 Sorting

14.2 Searching

14.3 Median and Selection

14.4 Generating Permutations

14.5 Generating Subsets

14.6 Generating Partitions

14.7 Generating Graphs

14.8 Calendrical Calculations

14.9 Job Scheduling

14.10 Satisfiability

15 Graph Problems: Polynomial-Time

15.1 Connected Components

15.2 Topological Sorting

15.3 Minimum Spanning Tree

15.4 Shortest Path

15.5 Transitive Closure and Reduction

15.6 Matching

15.7 Eulerian Cycle/Chinese Postman

15.8 Edge and Vertex Connectivity

15.9 Network Flow

15.10 Drawing Graphs Nicely

15.11 Drawing Trees

15.12 Planarity Detection and Embedding

16 Graph Problems: Hard Problems

16.1 Clique

16.2 Independent Set

16.3 Vertex Cover

16.4 Traveling Salesman Problem

16.5 Hamiltonian Cycle

16.6 Graph Partition

16.7 Vertex Coloring

16.8 Edge Coloring

16.9 Graph Isomorphism

16.10 Steiner Tree

16.11 Feedback Edge/Vertex Set

17 Computational Geometry

17.1 Robust Geometric Primitives

17.2 Convex Hull

17.3 Triangulation

17.4 Voronoi Diagrams

17.5 Nearest Neighbor Search

17.6 Range Search

17.7 Point Location

17.8 Intersection Detection

17.9 Bin Packing

17.10 Medial-Axis Transform

17.11 Polygon Partitioning

17.12 Simplifying Polygons

17.13 Shape Similarity

17.14 Motion Planning

17.15 Maintaining Line Arrangements

17.16 Minkowski Sum

18 Set and String Problems

18.1 Set Cover

18.2 Set Packing

18.3 String Matching

18.4 Approximate String Matching

18.5 Text Compression

18.6 Cryptography

18.7 Finite State Machine Minimization

18.8 Longest Common Substring/Subsequence

18.9 Shortest Common Superstring

19 Algorithmic Resources

19.1 Software Systems

19.2 Data Sources

19.3 Online Bibliographic Resources

19.4 Professional Consulting Services

Bibliography

……[看更多目录]

序言Most professional programmers that I've encountered are not well prepared to tackle algorithm design problems. This is a pity, because the techniques of algorithm design form one of the core practical technologies of computer science. Designing correct, efficient, and implementable algorithms for real-world problems requires access to two distinct bodies of knowledge:Techniques - Good algorithm designers understand several fundamental al-gorithm design techniques, including data structures, dynamic programming,depth-first search, backtracking, and heuristics. Perhaps the single most im-portant design technique is modeling, the art of abstracting a messy real-worldapplication into a clean problem suitable for algorithmic attack.Resources - Good algorithm designers stand on the shoulders of giants. Rather than laboring from scratch to produce a new algorithm for every task, they can figure out what is known about a particular problem. Rather than re-implementing popular algorithms from scratch, they seek existing imple- mentations to serve as a starting point. They are familiar with many classic algorithmic problems, which provide sufficient source material to model most any application.This book is intended as a manual on algorithm design, providing access tocombinatorial algorithm technology for both students and computer professionals.It is divided into two parts: Techniques and Resources, The former is a generalguide to techniques for the design and analysis of computer algorithms. The Re-sources section is intended for browsing and reference, and comprises the catalogof algorithmic resources, implementations, and an extensive bibliography.

文摘插图：

3.7.2 Efficient String Matching via Hashing

Strings are sequences of characters where the order of the characters matters, sinceALGORITHM is different than LOGARITHM. Text strings are fundamental to ahost of computing applications, from programming language parsing/compilation,to web search engines, to biological sequence analysis.

The primary data structure for representing strings is an array of characters.This allows us constant-time access to the ith character of the string. Some auxiliaryinformation must be maintained to mark the end of the stringeither a specialend-of-string character or （perhaps more usefully） a count of the n characters inthe string.

The most fundamental operation on text strings is substring search, namely:Problem: Substring Pattern MatchingInput: A text string t and a pattern string p.Output: Does t contain the pattern p as a substring, and if so where？