+612 9045 4394
$7.95 Delivery per order to Australia and New Zealand
100% Australian owned
Over a hundred thousand in-stock titles ready to ship
Algorithms : Main Ideas and Applications - Vladimir Uspensky


Main Ideas and Applications

Hardcover Published: 31st March 1993
ISBN: 9780792322108
Number Of Pages: 270

Share This Book:


or 4 easy payments of $84.72 with Learn more
Ships in 15 business days

Earn 678 Qantas Points
on this Book

Other Available Editions (Hide)

  • Paperback View Product Published: 7th December 2010
    Ships in 15 business days

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

Introductionp. 1
Notation and Terminologyp. 3
Fundamental Discoveries of the General Theory of Algorithmsp. 5
Preliminary notions of the theory of algorithms: constructive objects and aggregates; local properties and local actionsp. 7
The general notion of an algorithm as an independent (separate) conceptp. 17
Representative computational modelsp. 22
Appendix 1.2: Schonhage machinesp. 28
The general notion of a calculus as an independent (separate) conceptp. 31
Appendix 1.3: Algebraic examplesp. 37
Representative generating modelsp. 45
Interrelations between algorithms and calculusesp. 46
Time and Space as complexities of computation and generationp. 48
Appendix 1.6: Real-time simulationp. 57
Computable functions and generable sets; decidable sets; enumerable setsp. 58
The concept of a [mu]-recursive functionp. 66
Possibility of an arithmetical and even Diophantine representation of any enumerable set of natural numbersp. 68
Construction of an undecidable generable setp. 70
Post's reducibility problemp. 73
The concept of a relative algorithm, or an oracle algorithmp. 77
The concept of a computable operationp. 80
The concept of a program; programs as objects of computation and generationp. 84
The concept of a numbering and the theory of numberingsp. 98
First steps in the invariant, or machine-independent, theory of complexity of computationsp. 108
The theory of complexity and entropy of constructive objectsp. 110
Convenient computational modelsp. 115
Mathematical Applications of the Theory of Algorithmsp. 119
Investigations of mass problemsp. 121
Applications to the foundations of mathematics: constructive semanticsp. 137
Applications to mathematical logic: formalized languages of logic and arithmeticp. 141
Computable analysisp. 145
Numbered structuresp. 154
Applications to probability theory: definitions of a random sequencep. 166
Applications to information theory: the algorithmic approach to the concept of quantity of informationp. 179
Complexity bounds for particular problemsp. 184
Influence of the theory of algorithms on algorithmic practicep. 188
Appendix. Probabilistic Algorithms (How the Use of Randomness Makes Computations Shorter)p. 195
Referencesp. 209
Subject Indexp. 253
Author Indexp. 267
Table of Contents provided by Blackwell. All Rights Reserved.

ISBN: 9780792322108
ISBN-10: 079232210X
Series: Mathematics and Its Applications
Audience: General
Format: Hardcover
Language: English
Number Of Pages: 270
Published: 31st March 1993
Publisher: Springer
Country of Publication: NL
Dimensions (cm): 23.39 x 15.6  x 1.75
Weight (kg): 0.58

Earn 678 Qantas Points
on this Book