EN|RU

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

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

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

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

Шоломов Лев Абрамович 1
1. Институт системного анализа РАН,
пр. 60-летия Октября, 9, 117312 Москва, Россия
е-mail: sholomov@isa.ru

Статья поступила 16 января 2012 г.
Исправленный вариант — 9 апреля 2012 г.

 © Институт математики им. С. Л. Соболева, 2015