---

＜電子ブック＞
Algorithms: Main Ideas and Applications / by Vladimir Uspensky, A.L. Semenov
(Mathematics and Its Applications ; 251)

版	1st ed. 1993.
出版者	(Dordrecht : Springer Netherlands : Imprint: Springer)
出版年	1993
本文言語	英語
大きさ	XII, 270 p : online resource
著者標目	*Uspensky, Vladimir author Semenov, A.L author SpringerLink (Online service)
件　名	LCSH:Mathematical logic LCSH:Computer science LCSH:Logic FREE:Mathematical Logic and Foundations FREE:Theory of Computation FREE:Logic
一般注記	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 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]) HTTP:URL=https://doi.org/10.1007/978-94-015-8232-2

 類似資料