Algorithms and Complexity

Algorithms and Complexity

by: UNKNOWN AUTHOR

Elsevier Reference Monographs, 2014

ISBN: 9780080933917 , 1011 Pages

Format: PDF, PDB

Windows PC,Mac OSX Apple iPad, Android Tablet PC's Palm OS, PocketPC 2002 und älter, PocketPC 2003 und neuer, Windows Mobile Smartphone, Handys (mit Symbian)

Price: 65,39 EUR

More eBook Details

Algorithms and Complexity


 

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