Suchen und Finden
Front Cover
1
Algorithms and Complexity
4
Copyright Page
5
Table of Contents
10
Preface
6
List of Contributors to Volume A
8
CHAPTER 1. Machine Models and Simulations
16
1. Introduction
18
2. Sequential machine models
31
3. The second machine class
53
4. Parallel machine models outside the second machine class
69
Acknowledgment
75
References
76
CHAPTER 2. A Catalog of Complexity Classes
82
1. Preliminaries
84
2. Presumably intractable problems
98
3. Provably intractable problems
116
4. Classes that count
121
5. Inside P
140
6. New developments, tables and figures
158
References
167
CHAPTER 3. Machine-Independent Complexity Theory
178
1. Introduction
180
2. Simple Turing machines and space complexity
180
3. Recursion, padding and compression
182
4. Gaps and arbitrary speed-up
186
5. Effective speed-up
190
6. Fundamental Theorem for STM space
192
7. Machine independence
193
Acknowledgment
200
References
200
CHAPTER 4. Kolmogorov Complexity and its Applications
202
1. Introduction
204
2. Mathematical theory
211
3. Applications of compressibility
229
4. Example of an application in mathematics: weak prime number theorems
236
5. Applications of incompressibility: proving lower bounds
237
6. Resource-bounded Kolmogorov complexity and its applications
251
7. Conclusion
262
Acknowledgment
262
References
263
CHAPTER 5. Algorithms for Finding Patterns in Strings
270
1. Introduction
272
2. Notations for patterns
273
3. Matching keywords
277
4. Matching sets of keywords
288
5. Matching regular expressions
297
6. Related problems
303
7. Concluding remarks
310
Acknowledgment
310
References
310
CHAPTER 6. Data Structures
316
1. Introduction
318
2. The dictionary problem
320
3. The weighted dictionary problem and self-organizing data structures
334
4. Persistence
338
5. The Union-Split-Find problem
339
6. Priority queues
341
7. Nearest common ancestors
343
8. Selection
344
9. Merging
346
10. Dynamization techniques
347
References
349
CHAPTER 7. Computational Geometry
358
1. Introduction
360
2. Techniques and paradigms
360
3. Convex hulls
363
4. Voronoi diagrams
367
5. Proximity problems
371
6. Linear programming
375
7. Triangulation and decomposition
379
8. Planar point location
381
9. Multidimensional trees
383
10. Range search
385
11. Visibility computations
389
12. Combinatorial geometry
391
13. Other topics
393
14. Conclusion
395
References
395
CHAPTER 8. Algorithmic Motion Planning in Robotics
406
1. Introduction
408
2. Statement of the problem
409
3. Motion planning in static and known environments
412
4. Variants of the motion planning problem
430
5. Results in computational geometry relevant to motion planning
436
Acknowledgment
440
References
440
CHAPTER 9. Average-Case Analysis of Algorithms and Data Structures
446
0. Introduction
448
1. Combinatorial enumerations
451
2. Asymptotic methods
460
3. Sorting algorithms
473
4. Recursive decompositions and algorithms on trees
488
5. Hashing and address computation techniques
507
6. Dynamic algorithms
526
Acknowledgment
535
References
535
CHAPTER 10. Graph Algorithms
540
Prelude
542
1. Representation of graphs
542
2. Basic structure algorithms
566
3. Combinatorial optimization on graphs
594
References
627
CHAPTER 11. Algebraic Complexity Theory
648
1. Introduction
650
2. Addition chains
652
3. Computation sequences
652
4. Substitution
653
5. Degree of transcendency
655
6. Geometric degree
656
7. Derivatives
659
8. Branching
660
9. Complexity classes
663
10. Matrix multiplication and bilinear complexity
665
11. Degeneration and asymptotic spectrum
668
12. Lower bounds for rank and border rank
671
13. Fourier transform
675
14. Complete problems
676
15. Conclusion
679
References
679
CHAPTER 12. Algorithms in Number Theory
688
1. Introduction
690
2. Preliminaries
692
3. Algorithms for finite abelian groups
700
4. Factoring integers
712
5. Primality testing
721
Acknowledgment
727
References
727
CHAPTER 13. Cryptography
732
1. Introduction
734
2. Basics
734
3. The goals and tools of cryptology
737
4. Mathematical preliminaries
738
5. Complexity-theoretic foundations of cryptography
740
6. Privacy
743
7. Generating random or pseudo-random sequences and functions
750
8. Digital signatures
754
9. Two-party protocols
757
10. Multi-party protocols
761
11. Cryptography and complexity theory
763
Acknowledgment
764
References
765
CHAPTER 14. The Complexity of Finite Functions
772
1. Introduction
774
2. General circuits
775
3. Bounded-depth circuits
780
4. Monotone circuits
795
5. Formulas
801
6. Branching programs
811
7. Conclusion
814
Acknowledgment
815
References
815
CHAPTER 15. Communication Networks
820
1. Introduction
822
2. Communication problems
824
3. The Ajtai, Komlós and Szemerédi Theorem
835
Acknowledgment
846
References
846
CHAPTER 16. VLSI Theory
850
1. Introduction
852
2. VLSI complexity measures
854
3. The VLSI model
857
4. The basic lower bound argument
859
5. A geometric separator theorem
860
6. The communication complexity of Boolean predicates
861
7. The communication complexity of Boolean functions with many outputs
868
8. A lower bound on the switching energy of VLSI chips
872
9. Upper bounds on the AT2 -complexity of VLSI chips
877
Acknowledgment
880
References
880
CHAPTER 17. Parallel Algorithmsfor Shared-Memory Machines
884
1. Introduction
886
2. Efficient PRAM algorithms
888
3. Models of parallel computation
909
4. NC-algorithms and P-complete problems
921
5. Conclusion
946
Acknowledgment
947
References
947
CHAPTER 18. General Purpose Parallel Architectures
958
1. Introduction
960
2. Some networks
961
3. Routing
965
4. Universality
974
Acknowledgment
983
References
984
Subject Index
988
Alle Preise verstehen sich inklusive der gesetzlichen MwSt.