Том 19, номер 6, 2012 г., Стр. 72-98

УДК 519.728
Шоломов Л. А. 
Разложение недоопределённых данных

Аннотация:
Рассмотрена задача разложения недоопределённого источника произвольного вида в произведение источников, порождающих символы 0, 1 и неопределённый символ *, а также задача лучшего (в условленном смысле) приближённого разложения источника, если точное разложение невозможно. Показано, что для любого недоопределённого источника лучшее приближённое разложение существует и с точностью до некоторого отношения равносильности единственно (для разложимого источника оно является разложением). Описан полиномиальный алгоритм его построения. Изучены задачи, связанные с упрощением и равносильными преобразованиями разложений, предложены некоторые полиномиальные алгоритмы.
Табл. 4, библиогр. 8.

Ключевые слова: недоопределённый источник, информационная равносильность, разложение, нижняя аппроксимация, полиномиальный алгоритм.

Шоломов Лев Абрамович ¹
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 с.