Том 19, номер 6, 2012 г., Стр. 72-98
УДК 519.728
Шоломов Л. А.
Разложение недоопределённых данных
Аннотация:
Рассмотрена задача разложения недоопределённого источника произвольного вида в произведение источников, порождающих символы 0, 1 и неопределённый символ *, а также задача лучшего (в условленном смысле) приближённого разложения источника, если точное разложение невозможно. Показано, что для любого недоопределённого источника лучшее приближённое разложение существует и с точностью до некоторого отношения равносильности единственно (для разложимого источника оно является разложением). Описан полиномиальный алгоритм его построения. Изучены задачи, связанные с упрощением и равносильными преобразованиями разложений, предложены некоторые полиномиальные алгоритмы.
Табл. 4, библиогр. 8.
Ключевые слова: недоопределённый источник, информационная равносильность, разложение, нижняя аппроксимация, полиномиальный алгоритм.
Шоломов Лев Абрамович 1
1. Институт системного анализа РАН,
пр. 60-летия Октября, 9, 117312 Москва, Россия
е-mail: sholomov@isa.ru
Статья поступила 16 января 2012 г.
Исправленный вариант — 9 апреля 2012 г.
Литература
[1] Агибалов Г. П. Конечные автоматы на полурешетках. — Томск: Изд-во ТГУ, 1993. – 209 с.
[2] Галлагер Р. Теория информации и надежная связь. — М.: Сов. радио, 1974. — 720 с.
[3] Парватов Н. Г. Функциональная полнота в замкнутых классах квазимонотонных и монотонных трёхзначных функций на полурешётке // Дискрет. анализ и исслед. операций. Сер. 1. — 2003. — Т. 10, № 1. — C. 61–78.
[4] Парватов Н. Г. О формах представления монотонных и квазимонотонных функций на трехэлементной полурешетке // Мат. IX Междунар. семинара «Дискретная математика и её приложения». — М.: Изд-во мех.- мат. ф-та МГУ, 2007. — С. 127–130.
[5] Шоломов Л. А. Преобразование нечётких данных с сохранением информационных свойств // Дискрет. анализ и исслед. операций. Сер. 1. — 2005. — Т. 12, № 3. — С. 85–104.
[6] Шоломов Л. А. Элементы теории недоопределённой информации // Прикл. дискрет. математика. Прил. № 2. — 2009. — С. 18–42.
[7] Шоломов Л. А. Декомпозиция недоопределённых данных // «Проблемы теоретической кибернетики». Мат. XVI Междунар. конф. — Нижний Новгород: Изд-во Нижегородского гос. ун-та, 2011. — С. 570–573.
[8] Яблонский С. В. Элементы математической кибернетики. — М.: Высш. шк., 2007. — 188 с.
|