Van Leeuwen J. (ed.) Handbook of Theoretical Computer Science. Volume A. Algorithms and Complexity

Elsiever / MIT Press, 1990. — 1010 p.Всеобъемлющий справочник о различных типах сложности алгоритмов и вычислений.
Modern developments in computer and software systems have raised many challenging issues concerning the design and efficiency of complex programming applications. There is an increasing need for "advanced theory", to understand and exploit basic concepts and mechanisms in computing and information processing. The Handbook of Theoretical Computer Science is designed to provide a wide audience of professionals and students in Computer Science and related disciplines with an overview of the major results and developments in the theoretical exploration of these issues to date.
There are many different roles for "theory" in Computer Science. On the one hand it provides the necessary mathematical foundations for studying formal systems and algorithms that are needed. On the other hand, it provides concepts and languages to capture the essence, in algorithmic and descriptive terms, of any system from specification to efficient implementation. But the mathematical frameworks that have proved to be invaluable for Computer Science are used increasingly in many other disciplines as well. Wherever notions of information or information processing are identified, questions of representation and computation can be formalized in computer science terms. Theoretical Computer Science concerns itself with all formal models and methods and all techniques of description and analysis that are required in this domain.
As a consequence there are many facets to Theoretical Computer Science. As a discipline it employs advanced techniques from Mathematics and Logic, but at the same time it has established its own formal models and fundamental results in which the original motivations have remained visible. The Handbook of Theoretical Computer Science attempts to offer an in-depth view of the field of Theoretical Computer Science as a whole, by a comprehensive exposition of the scientific advances in this area.
In order to keep the Handbook within manageable limits, it was decided to restrict the material to the recognized core areas of Theoretical Computer Science. Even with this restriction imposed, further choices had to be made in the subjects covered and the extent of the material provided on each subject. The current version of the Handbook is presented in two volumes:
Vol. A: Algorithms and Complexity
Vol. B: Formal Models and Semantics
This more or less reflects the division between algorithm-oriented and description- oriented research that can be witnessed in Theoretical Computer Science, and it seemed natural to follow it for these books. Whereas the volumes can be used independently, there are many interesting connections that show that the two areas really are highly intertwined. Together, the volumes give a unique impression of research in Theoretical Computer Science as it is practised today. If not for reference purposes, we hope you will use these books to get a feeling for the theoretical work that is going on in the many fields of Computer Science or to simply satisfy your curiosity.
Each volume consists of close to twenty chapters, with each chapter devoted to a representative subject of current research. Volume A presents the basic material on models of computation, complexity theory, data structures and efficient computation in many recognized subdisciplines of Theoretical Computer Science. Volume B presents a choice of material on the theory of automata and rewriting systems, the foundations of modern programming languages, logics for program specification and verification, and a number of studies aimed at the theoretical modeling of advanced computing applications. Both volumes have been organized to reflect the development of Theoretical Computer Science from its classical roots to the modern complexity-theoretic and logic approaches to, for example, parallel and distributed computing. In most cases an extensive bibliography has been provided to assist in further study of the field and finding specific source documents for further reference. Specific attention has been given to a structured development of the material in the various chapters in order to make the Handbook largely self-contained. However, some familiarity with Computer Science at an undergraduate level is assumed.Machine Models and Simulations
A Catalog of Complexity Classes
Machine-Independent Complexity Theory
Kolmogorov Complexity and its Applications
Data Structures
Computational Geometry
Algorithmic Motion Planning in Robotics
Average-Case Analysis of Algorithms and Data Structures
Graph Algorithms
Algorithms in Number Theory
Cryptography
The Complexity of Finite Functions
Communication Networks
VLSI Theory
Parallel Algorithms for Shared-Memory Machines
General Purpose Parallel Architectures