RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


ПДМ, 2018, номер 39, страницы 13–32 (Mi pdm616)  

Теоретические основы прикладной дискретной математики

Об одном инварианте в задаче разложения недоопределённых данных

Л. А. Шоломов

ФИЦ "Информатика и управление" РАН, г. Москва, Россия

Аннотация: Рассматривается задача разложения произвольного недоопределённого источника в произведение недоопределённых двоичных источников. Ранее автором было установлено, что точное разложение существует не всегда, но всегда имеется в определённом смысле лучшее аппроксимирующее разложение. Исследуются построение и минимизация аппроксимирующих разложений. Развивается новая техника работы с разложениями на основе связанного с ними графа, названного характеристическим. Доказано, что этот граф является инвариантом равносильных преобразований разложений и полностью определяет класс равносильности. Установлено, что каждому конкретному разложению из этого класса соответствует покрытие характеристического графа системой полных двудольных подграфов, причём это соответствие взаимно однозначно с точностью до некоторой стандартизации разложений. Введённый инвариант, позволяя вместо отдельных разложений иметь дело со всем классом равносильности, значительно расширяет возможности конструктивного исследования разложений. В частности, он даёт подход к решению задачи минимизации разложений, недоступной для предшествующих методов.

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

DOI: https://doi.org/10.17223/20710410/39/2

Полный текст: PDF файл (739 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.728

Образец цитирования: Л. А. Шоломов, “Об одном инварианте в задаче разложения недоопределённых данных”, ПДМ, 2018, № 39, 13–32

Цитирование в формате AMSBIB
\RBibitem{Sho18}
\by Л.~А.~Шоломов
\paper Об одном инварианте в~задаче разложения недоопределённых данных
\jour ПДМ
\yr 2018
\issue 39
\pages 13--32
\mathnet{http://mi.mathnet.ru/pdm616}
\crossref{https://doi.org/10.17223/20710410/39/2}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm616
  • http://mi.mathnet.ru/rus/pdm/y2018/i1/p13

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:106
    Полный текст:26
    Литература:13
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020