Algorithms: Main Ideas and Applications - A. L. Semenov

. .

Sommaire:
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.