scientific article; zbMATH DE number 3872639
algorithm modelsautomata with memorycomplexitydiscrete devicesdiscrete informationerror correcting codeslogical functionsreliabilityswitching circuitsuncertaintyuniversal Turing machineunsolvability
Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Algorithms in computer science (68W99)
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.
- Discrete analysis of expert information. Research trends
- scientific article; zbMATH DE number 4022632 (Why is no real title available?)
- scientific article; zbMATH DE number 45686 (Why is no real title available?)
- Evaluation of Boolean functions on noisy input
- SOLENOIDAL MAPS, AUTOMATIC SEQUENCES, VAN DER PUT SERIES, AND MEALY AUTOMATA
- Comparative complexity of quantum and classical OBDDs for total and partial functions
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)