Suchen und Finden
The Algorithm Design Manual
von: Steven S. Skiena.
Springer Verlag London Limited, 2008
ISBN: 9781848000704 , 742 Seiten
2. Auflage
Format: PDF, OL
Kopierschutz: Wasserzeichen
Preis: 63,06 EUR
Preface
5
Contents
10
I Practical Algorithm Design
16
Introduction to Algorithm Design
17
Robot Tour Optimization
19
Selecting the Right Jobs
23
Reasoning about Correctness
25
Modeling the Problem
33
About the War Stories
36
War Story: Psychic Modeling
37
Exercises
41
Algorithm Analysis
45
The RAM Model of Computation
45
The Big Oh Notation
48
Growth Rates and Dominance Relations
51
Working with the Big Oh
54
Reasoning About Efficiency
55
Logarithms and Their Applications
60
Properties of Logarithms
64
War Story: Mystery of the Pyramids
65
Advanced Analysis (*)
68
Exercises
71
Data Structures
79
Contiguous vs. Linked Data Structures
80
Stacks and Queues
85
Dictionaries
86
Binary Search Trees
91
Priority Queues
97
War Story: Stripping Triangulations
99
Hashing and Strings
103
Specialized Data Structures
107
War Story: String 'em Up
108
Exercises
112
Sorting and Searching
117
Applications of Sorting
118
Pragmatics of Sorting
121
Heapsort: Fast Sorting via Data Structures
122
War Story: Give me a Ticket on an Airplane
132
Mergesort: Sorting by Divide-and-Conquer
134
Quicksort: Sorting by Randomization
137
Distribution Sort: Sorting via Bucketing
143
War Story: Skiena for the Defense
145
Binary Search and Related Algorithms
146
Divide-and-Conquer
149
Exercises
153
Graph Traversal
159
Flavors of Graphs
160
Data Structures for Graphs
165
War Story: I was a Victim of Moore's Law
169
War Story: Getting the Graph
172
Traversing a Graph
175
Breadth-First Search
176
Applications of Breadth-First Search
180
Depth-First Search
183
Applications of Depth-First Search
186
Depth-First Search on Directed Graphs
192
Exercises
198
Weighted Graph Algorithms
205
Minimum Spanning Trees
206
War Story: Nothing but Nets
216
Shortest Paths
219
War Story: Dialing for Documents
226
Network Flows and Bipartite Matching
231
Design Graphs, Not Algorithms
236
Exercises
239
Combinatorial Search and Heuristic Methods
244
Backtracking
245
Search Pruning
252
Sudoku
253
War Story: Covering Chessboards
258
Heuristic Search Methods
261
War Story: Only it is Not a Radio
274
War Story: Annealing Arrays
277
Other Heuristic Search Methods
280
Parallel Algorithms
281
War Story: Going Nowhere Fast
282
Exercises
284
Dynamic Programming
287
Caching vs. Computation
288
Approximate String Matching
294
Longest Increasing Sequence
303
War Story: Evolution of the Lobster
305
The Partition Problem
308
Parsing Context-Free Grammars
312
Limitations of Dynamic Programming: TSP
315
War Story: What's Past is Prolog
318
War Story: Text Compression for Bar Codes
321
Exercises
324
Intractable Problems and Approximation Algorithms
330
Problems and Reductions
331
Reductions for Algorithms
333
Elementary Hardness Reductions
337
Satisfiability
342
Creative Reductions
344
The Art of Proving Hardness
348
War Story: Hard Against the Clock
351
War Story: And Then I Failed
353
P vs. NP
355
Dealing with NP-complete Problems
358
Exercises
364
How to Design Algorithms
370
II The Hitchhiker's Guide to Algorithms
375
A Catalog of Algorithmic Problems
376
Data Structures
379
Dictionaries
380
Priority Queues
386
Suffix Trees and Arrays
390
Graph Data Structures
394
Set Data Structures
398
Kd-Trees
402
Numerical Problems
406
Solving Linear Equations
408
Bandwidth Reduction
411
Matrix Multiplication
414
Determinants and Permanents
417
Constrained and Unconstrained Optimization
420
Linear Programming
424
Random Number Generation
428
Factoring and Primality Testing
433
Arbitrary-Precision Arithmetic
436
Knapsack Problem
440
Discrete Fourier Transform
444
Combinatorial Problems
447
Sorting
449
Searching
454
Median and Selection
458
Generating Permutations
461
Generating Subsets
465
Generating Partitions
469
Generating Graphs
473
Calendrical Calculations
478
Job Scheduling
481
Satisfiability
485
Graph Problems: Polynomial-Time
488
Connected Components
490
Topological Sorting
494
Minimum Spanning Tree
497
Shortest Path
502
Transitive Closure and Reduction
508
Matching
511
Eulerian Cycle/Chinese Postman
515
Edge and Vertex Connectivity
518
Network Flow
522
Drawing Graphs Nicely
526
Drawing Trees
530
Planarity Detection and Embedding
533
Graph Problems: Hard Problems
536
Clique
538
Independent Set
541
Vertex Cover
543
Traveling Salesman Problem
546
Hamiltonian Cycle
551
Graph Partition
554
Vertex Coloring
557
Edge Coloring
561
Graph Isomorphism
563
Steiner Tree
568
Feedback Edge/Vertex Set
572
Computational Geometry
575
Robust Geometric Primitives
577
Convex Hull
581
Triangulation
585
Voronoi Diagrams
589
Nearest Neighbor Search
593
Range Search
597
Point Location
600
Intersection Detection
604
Bin Packing
608
Medial-Axis Transform
611
Polygon Partitioning
614
Simplifying Polygons
617
Shape Similarity
620
Motion Planning
623
Maintaining Line Arrangements
627
Minkowski Sum
630
Set and String Problems
633
Set Cover
634
Set Packing
638
String Matching
641
Approximate String Matching
644
Text Compression
650
Cryptography
654
Finite State Machine Minimization
659
Longest Common Substring/Subsequence
663
Shortest Common Superstring
667
Algorithmic Resources
670
Software Systems
670
Data Sources
676
Online Bibliographic Resources
676
Professional Consulting Services
677
Bibliography
678
Index
721
Alle Preise verstehen sich inklusive der gesetzlichen MwSt.