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

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

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



Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование:
Год:
Том:
Выпуск:
Страница:
Найти






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


Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование, 2016, том 9, выпуск 3, страницы 17–30 (Mi vyuru326)  

Математическое моделирование

An inference algorithm for monotone Boolean functions associated with undirected graphs

[Алгоритм расшифровки монотонных булевых функций, порождаемых неориентированными графами]

D. N. Gainanova, V. A. Rasskazovab

a Ural Federal University, Ekaterinburg, Russian Federation
b Moscow Aviation Institute, Moscow, Russian Federation

Аннотация: Существует достаточно прикладных задач, в которых одним из инструментов моделирования служат булевы функции, среди которых важную роль играют монотонные булевы функции. Например, монотонные булевы функции являются удобным средством для описания структуры совместных подсистем несовместных систем условий, поскольку совместность является монотонным свойством.
В работе рассматриваются монотонные булевы функции, порождаемые неориентированными графами, в которых нули функции определяются как такие двоичные наборы, для которых соответствующий подграф исходного неориентированного графа пуст, или не содержит ребер. Для такого класса монотонных булевых функций даются постановки задач, связанных с выделением верхних нулей и максимальных верхних нулей функции. Вводятся понятия $k$-вершины и $(k, m)$-вершины в неориентированном графе. Показано, что для любой $k$-вершины исходного графа существует максимальный верхний нуль порожденной монотонной булевой функции, в котором компонента $x_{i}$, соответствующая этой $k$-вершине, принимает значение $1$.
На основе этого утверждения построен алгоритм выделения максимального верхнего нуля для рассматриваемого класса монотонных булевых функций, который гарантирует, при определенных условиях, нахождение точного решения задачи поиска максимального верхнего нуля, либо приводит к снижению размерности исходной задачи. Предложенный алгоритм обобщается для случая использования $(k, m)$-вершин. Построенный алгоритм выделяет верхний нуль монотонной булевой функции и дает оценку его отклонения от максимального верхнего нуля по числу единиц в этих наборах. Алгоритм имеет сложность $O(n^2p)$, где $n$ — число вершин и $p$ — число ребер исходного графа.

Ключевые слова: монотонная булева функция; верхний нуль монотонной булевой функции; неориентированный граф; алгоритм поиска максимальных верхних нулей монотонной булевой функции.

Финансовая поддержка
Работа проводилась при финансовой поддержке КЦП (Коллективный центр превосходства) «Квантум и видеоинформационные технологии» программа развития Уральского федерального университета им. первого президента России Б.Н. Ельцина.


DOI: https://doi.org/10.14529/mmp160302

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

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.1
MSC: 05C85
Поступила в редакцию: 01.04.2016
Язык публикации: английский

Образец цитирования: D. N. Gainanov, V. A. Rasskazova, “An inference algorithm for monotone Boolean functions associated with undirected graphs”, Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование, 9:3 (2016), 17–30

Цитирование в формате AMSBIB
\RBibitem{GaiRas16}
\by D.~N.~Gainanov, V.~A.~Rasskazova
\paper An inference algorithm for monotone Boolean functions associated with undirected graphs
\jour Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование
\yr 2016
\vol 9
\issue 3
\pages 17--30
\mathnet{http://mi.mathnet.ru/vyuru326}
\crossref{https://doi.org/10.14529/mmp160302}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000390881400002}
\elib{http://elibrary.ru/item.asp?id=26563749}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/vyuru326
  • http://mi.mathnet.ru/rus/vyuru/v9/i3/p17

    ОТПРАВИТЬ: 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
  • Просмотров:
    Эта страница:104
    Полный текст:19
    Литература:19
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019