Vladimir Uspensky, A. L. Semenov

Algorithms: Main Ideas and Applications (eBook, PDF)

• Format: PDF

Produktbeschreibung

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 the oretical 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]).

---

Dieser Download kann aus rechtlichen Gründen nur mit Rechnungsadresse in A, B, BG, CY, CZ, D, DK, EW, E, FIN, F, GR, HR, H, IRL, I, LT, L, LR, M, NL, PL, P, R, S, SLO, SK ausgeliefert werden.

Produktdetails

• Verlag: Springer Netherlands
• Seitenzahl: 270
• Erscheinungstermin: 14. März 2013
• Englisch
• ISBN-13: 9789401582322
• Artikelnr.: 44054331

Inhaltsangabe

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.