No label defined (Q3769959)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4028893
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4028893 |
Statements
1987
0 references
theory of algorithms
0 references
computational complexity
0 references
In this book an attempt is made to overview all the basic achievements in the theory of algorithms in the last 50 years. The book is an improved version of an earlier work [the authors, ``What are the gains of the theory of algorithms'', Lect. Notes Comput. Sci. 122, 100-234 (1981; Zbl 0477.68035)]. The book is well-written and surprisingly informal. The only drawback (conditioned by the space limits) is the fluency of some considerations. It may be recommended as a guide-book for beginners in the field as well as for specialists. The book consists of two parts and an appendix. In Part 1, ``Basic discoveries of the general theory of algorithms'', the following main fields are overviewed: the general notion of algorithms; representative computational models; interrelations between algorithms and calculi; time and space as complexities of computations; computable functions and generable sets; decidable sets, enumerable sets; the concept of \(\mu\)- recursive function; the possibility of arithmetical and diophantine representation of enumerable sets; Post's reducibility problem; the concept of numbering and the theory of numberings; machine-independent theory of computational complexity, the complexity and entropy of constructive objects. Part 2, ``Basic mathematical applications of the theory of algorithms'', contains the following main applications: investigation of mass problems; applications to foundations of mathematics; computable analysis; applications to probability theory and information theory; evaluation of complexity for solving particular problems; influence of the theory on algorithmic practice. The appendix contains some comments on the power of probabilistic algorithms.
0 references