scientific article; zbMATH DE number 3872639

From MaRDI portal
Publication:3339244





The book consists of an introduction and three parts. Part one displays an apparatus of logical functions and their representation with the help of discrete devices without memory. The complexity of circuitry of such devices (in terms of the number of elements) is analyzed and methods for their design are suggested, including the asymptotic method. A method for the design of automata with memory is outlined which features a minimal number of states and performs specified algorithms of functioning with the use of logical elements and delays. Part two treats algorithm models and their equivalence. A universal Turing machine is designed capable of modelling an arbitrary algorithmic procedure. The existence of algorithmically unsolvable problems is established. Computational limitations are studied imposed by memory size and problem solving time. The complexity of different classes of problems is discussed. Problems of reliability of storage, transmission and processing of discrete data are dealt with in Part three. It studies error detecting and error correcting codes, and their use in the design of self- correcting switching circuits and analyzes the asymptotic estimation of their complexity. A correlation is established between the amounts of information and uncertainty, on one hand, and throughput, on the other. Optimal compression of discrete information is considered. The monograph is a student book and may be useful for computer engineers, too.












This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3339244)