Инд. авторы:	Федотов А.А.
Заглавие:	Построение определительных таблиц при неполной информации о частотах встречаемости определяемых объектов
Библ. ссылка:	Федотов А.А. Построение определительных таблиц при неполной информации о частотах встречаемости определяемых объектов // Вычислительные технологии. - 2000. - Т.5. - № 3. - С.110-122. - ISSN 1560-7534. - EISSN 2313-691X.
Внешние системы:	РИНЦ: 13026314;
Реферат:	eng: Search trees are intended for the identification of objects in biology, mineralogy etc. The traditional quality criterion of a search tree is the average time of the object identification. It, in its turn, is determined by the probability distribution over the set of objects which is usually not known with certainty. However, some known data about the objects occurrence rate can be used in order to reduce the time consumption for compiling the search trees. The case is considered when the data on the occurrency rate can be represented as some partial order. In this work a method for constructing a search tree close to optimum for thus specified class under the minimax approach is presented. An example of making use of the described algorithm is given. rus: Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, грант № 98-01-00772. Определительные таблицы (ключи) предназначены для идентификации объектов в биологии, минералогии и пр. Мерой качества определительной таблицы естественно считать среднее время (трудоемкость) определения объекта. В свою очередь, эта величина зависит от вероятностного распределения на множестве объектов, которое, как правило, точно не известно. Однако некоторые известные сведения о частотах встречаемости объектов можно попытаться использовать для уменьшения трудоемкости определительных таблиц. Рассматривается случай, когда сведения о частотах встречаемости можно представить в виде некоторого частичного порядка. В статье приведен метод построения определительной таблицы, близкой к наилучшей для заданного таким образом класса при минимаксном подходе. Приведен пример использования описанного алгоритма.
Издано:	2000
Физ. характеристика:	с.110-122
Цитирование:	1. Кричевский Р.Е. Сжатие и поиск информации. Радио и связь, М., 1989. 2. Рябко Б.Я., Харитонов А.Ю. Метод построения определительных таблиц, обнаруживающих и исправляющих ошибки. Изв. СО АН СССР. Сер. биол. наук, вып. 1, 1982. 3. Krichevsky R. E., Ryabko B. Ya. Universal Retrieval Trees. Discrete Appl. Math., 12, 1985, 293-302. 4. Рябко Б.Я. Кодирование источника с неизвестными, но упорядоченными вероятностями. Проблемы передачи информации, 14, № 2, 1979, 71-77. 5. Ермаков Н.Б., Красников А.А., Федотов А.А., Федотов А.М., Хорев А.Г. База данных "Флора Новосибирской области". http://www-sbras.nsc.ru/win/elbib/bio/db/ 6. Blahut R. Computation of Channel Capacity and Rate Distortion Functions. IEEE Trans., JT-18, No. 4, 1973, 460-473. 7. Галлагер Р. Теория информации и надежная связь. Советское Радио, М., 1974. 8. Гольштейн Е.Г. Теория двойственности в математическом программировании и ее приложения. Наука, М., 1971. 9. Флора Сибири. Т. 6. Наука, Новосибирск, 1993. 10. Kuhn H. W., Tucker A. W. Non-linear programming. Proc. of the Second Berkley Symp. of Math. Statistics and Probability. Berkley and Los Angeles, Univ. of California Press, 1951, 481-492. 11. Давыдов Э. Г. Игры, графы, ресурсы. Радио и связь, М., 1981. 12. Topsoe F. Частное сообщение.