No label defined (Q3339244)
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 3872639
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3872639 |
Statements
1980
0 references
unsolvability
0 references
logical functions
0 references
discrete devices
0 references
complexity
0 references
automata with memory
0 references
algorithm models
0 references
universal Turing machine
0 references
reliability
0 references
error correcting codes
0 references
switching circuits
0 references
uncertainty
0 references
discrete information
0 references
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.
0 references