Overview

The theory of algorithms not only answers philosophical questions but also is applicable to practical computing, as well as to software and hardware design. This text presents exact mathematical formulations of major concepts and facts of the theory of algorithms in a unified way. Precise mathematical statements are given, together with their underlying motivations, philosophical interpretations and historical developments, starting with Frege, Hilbert and Borel through Goedel and Turing up to Kolmogorov's results of 1950-1980. It is divided into two parts. The first part outlines the fundamental discoveries of the general theory of algorithms. Numerous applications are discussed in the second part. The concept of probabilistic algorithms is presented in the appendix. This work should be of interest to mathematicians, computer scientists, engineers and to everyone who uses algorithms.

Full Product Details

Author:   Vladimir Uspensky ,  A.L. Semenov ,  A. Shen
Publisher:   Springer
Imprint:   Springer
Edition:   1993 ed.
Volume:   251
Dimensions:   Width: 15.60cm , Height: 1.70cm , Length: 23.40cm
Weight:   1.290kg
ISBN:  

9780792322108

ISBN 10:   079232210
Pages:   270
Publication Date:   31 March 1993
Audience:   Professional and scholarly ,  Professional & Vocational
Format:   Hardback
Publisher's Status:   Active
Availability:   In Print  
This item will be ordered in for you from one of our suppliers. Upon receipt, we will promptly dispatch it out to you. For in store availability, please contact us.

Table of Contents

Notation and Terminology.- 1.0 Preliminary notions of the theory of algorithms: constructive objects and aggregates; local properties and local actions.- 1.1 The general notion of an algorithm as an independent (separate) concept.- 1.2 Representative computational models.- 1.3 The general notion of a calculus as an independent (separate) concept.- 1.4 Representative generating models.- 1.5 Interrelations between algorithms and calculuses.- 1.6 Time and Space as complexities of computation and generation.- 1.7 Computable functions and generable sets; decidable sets; enumerable sets.- 1.8 The concept of a ?-recursive function.- 1.9 Possibility of an arithmetical and even Diophantine representation of any enumerable set of natural numbers.- 1.10 Construction of an undecidable generable set.- 1.11 Post’s reducibility problem.- 1.12 The concept of a relative algorithm, or an oracle algorithm.- 1.13 The concept of a computable operation.- 1.14 The concept of a program; programs as objects of computation and generation.- 1.15 The concept of a numbering and the theory of numberings.- 1.16 First steps in the invariant, or machine-independent, theory of complexity of computations.- 1.17 The theory of complexity and entropy of constructive objects.- 1.18 Convenient computational models.- 2.1 Investigations of mass problems.- 2.2 Applications to the foundations of mathematics: constructive semantics.- 2.3 Applications to mathematical logic: formalized languages of logic and arithmetic.- 2.4 Computable analysis.- 2.5 Numbered structures.- 2.6 Applications to probability theory: definitions of a random sequence.- 2.7 Applications to information theory: the algorithmic approach to the concept of quantity of information.- 2.8 Complexity bounds for particular problems.- 2.9 Influenceof the theory of algorithms on algorithmic practice.- Appendix. Probabilistic Algorithms (How the Use of Randomness Makes Computations Shorter).- A.1 Preliminary remarks.- A.2 Main results.- A.3 Formal definitions.- References.- Author Index.

Reviews

Author Information

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions