|
Теоретические основы прикладной дискретной математики
Об одном инварианте в задаче разложения недоопределённых данных
Л. А. Шоломов ФИЦ "Информатика и управление" РАН, г. Москва, Россия
Аннотация:
Рассматривается задача разложения произвольного недоопределённого источника в произведение недоопределённых двоичных источников. Ранее автором было установлено, что точное разложение существует не всегда, но всегда имеется в определённом смысле лучшее аппроксимирующее разложение. Исследуются построение и минимизация аппроксимирующих разложений. Развивается новая техника работы с разложениями на основе связанного с ними графа, названного характеристическим. Доказано, что этот граф является инвариантом равносильных преобразований разложений и полностью определяет класс равносильности. Установлено, что каждому конкретному разложению из этого класса соответствует покрытие характеристического графа системой полных двудольных подграфов, причём это соответствие взаимно однозначно с точностью до некоторой стандартизации разложений. Введённый инвариант, позволяя вместо отдельных разложений иметь дело со всем классом равносильности, значительно расширяет возможности конструктивного исследования разложений. В частности, он даёт подход к решению задачи минимизации разложений, недоступной для предшествующих методов.
Ключевые слова:
недоопределённый источник, декомпозиция, аппроксимация, инвариант равносильных преобразований, характеристический граф разложения, биклика, NP-полнота.
Образец цитирования:
Л. А. Шоломов, “Об одном инварианте в задаче разложения недоопределённых данных”, ПДМ, 2018, № 39, 13–32
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm616 https://www.mathnet.ru/rus/pdm/y2018/i1/p13
|
Статистика просмотров: |
Страница аннотации: | 179 | PDF полного текста: | 54 | Список литературы: | 29 |
|