Algorithms: Main Ideas and Applications

by Vladimir Uspensky, A.L. Semenov

Overview

Today the notion of the algorithm is familiar not only to mathematicians. It forms a conceptual base for information processing; the existence of a corresponding algorithm makes automatic information processing possible. The theory of algorithms (together with mathematical logic ) forms the theoretical basis for modern computer science (see [Sem Us 86]; this article is called "Mathematical Logic in Computer Science and Computing Practice" and in its title mathematical logic is understood in a broad sense including the theory of algorithms). However, not everyone realizes that the word "algorithm" includes a transformed toponym Khorezm. Algorithms were named after a great sci­ entist of medieval East, is al-Khwarizmi (where al-Khwarizmi means "from Khorezm"). He lived between c. 783 and 850 B.C. and the year 1983 was chosen to celebrate his 1200th birthday. A short biography of al-Khwarizmi compiled in the tenth century starts as follows: "al-Khwarizmi. His name is Muhammad ibn Musa, he is from Khoresm" (cited according to [Bul Rozen Ah 83, p.8]).

Product Details

ISBN-13:	9789048142569
Publisher:	Springer Netherlands
Publication date:	12/07/2010
Series:	Mathematics and Its Applications , #251
Edition description:	Softcover reprint of hardcover 1st ed. 1993
Pages:	270
Product dimensions:	6.30(w) x 9.45(h) x 0.02(d)

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.

Editorial Reviews

Translated from the Russian edition. The theory of algorithms not only answers philosophical questions but also is extremely applicable in practical computing, as well as in software and hardware design. This work presents exact mathematical formulations of major concepts and facts of the theory of algorithms in a unified way. Precise mathematical statements are given 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. Annotation c. Book News, Inc., Portland, OR (booknews.com)

Booknews