Luisa Algorithms and Complexity

1. Auflage 2014
ISBN: 978-0-08-093391-7
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band Volume A, 260 Seiten, Web PDF

Reihe: Handbook of Theoretical Computer Science

This first part presents chapters on models of computation, complexity theory, data structures, and efficient computation in many recognized sub-disciplines of Theoretical Computer Science.

Autoren/Hrsg.

Luisa, Bozzano G

Inhaltsverzeichnis

1;Front Cover;1
2;Algorithms and Complexity;4
3;Copyright Page;5
4;Table of Contents;10
5;Preface;6
6;List of Contributors to Volume A;8
7;CHAPTER 1. Machine Models and Simulations;16
7.1;1. Introduction;18
7.2;2. Sequential machine models;31
7.3;3. The second machine class;53
7.4;4. Parallel machine models outside the second machine class;69
7.5;Acknowledgment;75
7.6;References;76
8;CHAPTER 2. A Catalog of Complexity Classes;82
8.1;1. Preliminaries;84
8.2;2. Presumably intractable problems;98
8.3;3. Provably intractable problems;116
8.4;4. Classes that count;121
8.5;5. Inside P;140
8.6;6. New developments, tables and figures;158
8.7;References;167
9;CHAPTER 3. Machine-Independent Complexity Theory;178
9.1;1. Introduction;180
9.2;2. Simple Turing machines and space complexity;180
9.3;3. Recursion, padding and compression;182
9.4;4. Gaps and arbitrary speed-up;186
9.5;5. Effective speed-up;190
9.6;6. Fundamental Theorem for STM space;192
9.7;7. Machine independence;193
9.8;Acknowledgment;200
9.9;References;200
10;CHAPTER 4. Kolmogorov Complexity and its Applications;202
10.1;1. Introduction;204
10.2;2. Mathematical theory;211
10.3;3. Applications of compressibility;229
10.4;4. Example of an application in mathematics: weak prime number theorems;236
10.5;5. Applications of incompressibility: proving lower bounds;237
10.6;6. Resource-bounded Kolmogorov complexity and its applications;251
10.7;7. Conclusion;262
10.8;Acknowledgment;262
10.9;References;263
11;CHAPTER 5. Algorithms for Finding Patterns in Strings;270
11.1;1. Introduction;272
11.2;2. Notations for patterns;273
11.3;3. Matching keywords;277
11.4;4. Matching sets of keywords;288
11.5;5. Matching regular expressions;297
11.6;6. Related problems;303
11.7;7. Concluding remarks;310
11.8;Acknowledgment;310
11.9;References;310
12;CHAPTER 6. Data Structures;316
12.1;1. Introduction;318
12.2;2. The dictionary problem;320
12.3;3. The weighted dictionary problem and self-organizing data structures;334
12.4;4. Persistence;338
12.5;5. The Union-Split-Find problem;339
12.6;6. Priority queues;341
12.7;7. Nearest common ancestors;343
12.8;8. Selection;344
12.9;9. Merging;346
12.10;10. Dynamization techniques;347
12.11;References;349
13;CHAPTER 7. Computational Geometry;358
13.1;1. Introduction;360
13.2;2. Techniques and paradigms;360
13.3;3. Convex hulls;363
13.4;4. Voronoi diagrams;367
13.5;5. Proximity problems;371
13.6;6. Linear programming;375
13.7;7. Triangulation and decomposition;379
13.8;8. Planar point location;381
13.9;9. Multidimensional trees;383
13.10;10. Range search;385
13.11;11. Visibility computations;389
13.12;12. Combinatorial geometry;391
13.13;13. Other topics;393
13.14;14. Conclusion;395
13.15;References;395
14;CHAPTER 8. Algorithmic Motion Planning in Robotics;406
14.1;1. Introduction;408
14.2;2. Statement of the problem;409
14.3;3. Motion planning in static and known environments;412
14.4;4. Variants of the motion planning problem;430
14.5;5. Results in computational geometry relevant to motion planning;436
14.6;Acknowledgment;440
14.7;References;440
15;CHAPTER 9. Average-Case Analysis of Algorithms and Data Structures;446
15.1;0. Introduction;448
15.2;1. Combinatorial enumerations;451
15.3;2. Asymptotic methods;460
15.4;3. Sorting algorithms;473
15.5;4. Recursive decompositions and algorithms on trees;488
15.6;5. Hashing and address computation techniques;507
15.7;6. Dynamic algorithms;526
15.8;Acknowledgment;535
15.9;References;535
16;CHAPTER 10. Graph Algorithms;540
16.1;Prelude;542
16.2;1. Representation of graphs;542
16.3;2. Basic structure algorithms;566
16.4;3. Combinatorial optimization on graphs;594
16.5;References;627
17;CHAPTER 11. Algebraic Complexity Theory;648
17.1;1. Introduction;650
17.2;2. Addition chains;652
17.3;3. Computation sequences;652
17.4;4. Substitution;653
17.5;5. Degree of transcendency;655
17.6;6. Geometric degree;656
17.7;7. Derivatives;659
17.8;8. Branching;660
17.9;9. Complexity classes;663
17.10;10. Matrix multiplication and bilinear complexity;665
17.11;11. Degeneration and asymptotic spectrum;668
17.12;12. Lower bounds for rank and border rank;671
17.13;13. Fourier transform;675
17.14;14. Complete problems;676
17.15;15. Conclusion;679
17.16;References;679
18;CHAPTER 12. Algorithms in Number Theory;688
18.1;1. Introduction;690
18.2;2. Preliminaries;692
18.3;3. Algorithms for finite abelian groups;700
18.4;4. Factoring integers;712
18.5;5. Primality testing;721
18.6;Acknowledgment;727
18.7;References;727
19;CHAPTER 13. Cryptography;732
19.1;1. Introduction;734
19.2;2. Basics;734
19.3;3. The goals and tools of cryptology;737
19.4;4. Mathematical preliminaries;738
19.5;5. Complexity-theoretic foundations of cryptography;740
19.6;6. Privacy;743
19.7;7. Generating random or pseudo-random sequences and functions;750
19.8;8. Digital signatures;754
19.9;9. Two-party protocols;757
19.10;10. Multi-party protocols;761
19.11;11. Cryptography and complexity theory;763
19.12;Acknowledgment;764
19.13;References;765
20;CHAPTER 14. The Complexity of Finite Functions;772
20.1;1. Introduction;774
20.2;2. General circuits;775
20.3;3. Bounded-depth circuits;780
20.4;4. Monotone circuits;795
20.5;5. Formulas;801
20.6;6. Branching programs;811
20.7;7. Conclusion;814
20.8;Acknowledgment;815
20.9;References;815
21;CHAPTER 15. Communication Networks;820
21.1;1. Introduction;822
21.2;2. Communication problems;824
21.3;3. The Ajtai, Komlós and Szemerédi Theorem;835
21.4;Acknowledgment;846
21.5;References;846
22;CHAPTER 16. VLSI Theory;850
22.1;1. Introduction;852
22.2;2. VLSI complexity measures;854
22.3;3. The VLSI model;857
22.4;4. The basic lower bound argument;859
22.5;5. A geometric separator theorem;860
22.6;6. The communication complexity of Boolean predicates;861
22.7;7. The communication complexity of Boolean functions with many outputs;868
22.8;8. A lower bound on the switching energy of VLSI chips;872
22.9;9. Upper bounds on the AT2 -complexity of VLSI chips;877
22.10;Acknowledgment;880
22.11;References;880
23;CHAPTER 17. Parallel Algorithmsfor Shared-Memory Machines;884
23.1;1. Introduction;886
23.2;2. Efficient PRAM algorithms;888
23.3;3. Models of parallel computation;909
23.4;4. NC-algorithms and P-complete problems;921
23.5;5. Conclusion;946
23.6;Acknowledgment;947
23.7;References;947
24;CHAPTER 18. General Purpose Parallel Architectures;958
24.1;1. Introduction;960
24.2;2. Some networks;961
24.3;3. Routing;965
24.4;4. Universality;974
24.5;Acknowledgment;983
24.6;References;984
25;Subject Index;988