Reconstruction of objects from a minimum number of distorted patterns.

*(English. Russian original)*Zbl 1008.94522
Dokl. Math. 55, No. 3, 417-420 (1997); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 354, No. 5, 593-596 (1997).

Summary: The problem of effectively recognizing an unknown object (such as a sequence of symbols) from its patterns distorted by errors of a given type and multiplicity is studied. Recognition efficiency is understood as minimization of the number \(N\) of distorted patterns of the object sufficient for the reproduction of an arbitrary unknown object with a required accuracy and/or probability. The problem of recognizing an unknown object from its patterns arises in various fields of science, such as computer science, chemistry, and genetics. This problem is essentially different from the traditional problems of storing and transmitting encoded messages, because it involves reconstructing an arbitrary object from a given set. We formulate this problem in terms of metric spaces and solve it for the basic metric spaces studied in the theory of data transmission. In addition, we construct simple algorithms for reconstructing objects with the use of the found minimum number of distorted patterns.