Curiculum Vitae
Other Writings
Book reviews
from the
Dutch Mathematical
Book reviews
from the journal
Acta Applicandae

Book review

Author(s) Uspensky, Vladimir
Semenov, Alexei
Title Algorithms: Main Ideas and Applications
Publisher Kluwer Academic Publishers
Year of publication 1993
Reviewed by Z. Kása

The interest for the theoretical foundation of computer science is growing, especially the problems related to algorithms are relevants. The essential contribution of the Soviet (not only Russian) researchers to this area is well-known. This book is one of these contributions.

In the first part of the book (Fundamental discoveries of the general theory of algorithms) the authors treat the following subjects: constructive objects and aggregates, local properties and actions, Kolmogorov complexes, the general notion of an algorithm, representative computational models (including programming languages), the general notion of the calculus, computable functions, recursive functions, the concepts of a program, the concept of numbering.

In the part II (Mathematical applications of the theory of algorithms) the subjects included are: applications to the foundation of mathematics, application to mathematical logic, computable analysis, numbered structure, application to probability theory, application to information theory, influence of theory of algorithms on algorithmic practice. The appendix deals with the probabilistic algorithms.

The book contains also a subject and an author index, and an impressive list of references of 44 pages. It is recommended to mathematicians and theoretical computer scientists who want to have a general view on the problems of theoretical and practical aspects of algorithms.