Overview

The theory of algorithms not only answers philosophical questions but also is eminently applicable to practical computing, as well as to software and hardware design. This book presents exact mathematical formulations of major concepts and facts of the theory of algorithms in a unified and elegant way. Precise mathematical statements are given, together with their underlying motivations, philosophical interpretations and historical developments, starting with Frege, Hilbert and Borel through Godel and Turing up to Kolmogorov's results of 1950-1980. The book 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 will be of interest to mathematicians, computer scientists, engineers and to everyone who uses algorithms.

Full Product Details

Author:   Vladimir Uspensky ,  A.L. Semenov
Publisher:   Springer
Imprint:   Springer
Edition:   Softcover reprint of hardcover 1st ed. 1993
Volume:   251
Dimensions:   Width: 16.00cm , Height: 1.50cm , Length: 24.00cm
Weight:   0.454kg
ISBN:  

9789048142569

ISBN 10:   9048142563
Pages:   270
Publication Date:   07 December 2010
Audience:   Professional and scholarly ,  Professional & Vocational
Format:   Paperback
Publisher's Status:   Active
Availability:   Out of stock  
The supplier is temporarily out of stock of this item. It will be ordered for you on backorder and shipped when it becomes available.

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