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

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

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



Ж. вычисл. матем. и матем. физ.:
Год:
Том:
Выпуск:
Страница:
Найти






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


Ж. вычисл. матем. и матем. физ., 2012, том 52, номер 10, страницы 1926–1935 (Mi zvmmf9772)  

Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

О сложности задачи дуализации

Е. В. Дюкова, Р. М. Сотнезов

119991 Москва, ул. Вавилова, 40, ВЦ РАН

Аннотация: Работа посвящена вопросам вычислительной сложности дискретных задач перечисления решений. Введено понятие асимптотически эффективного алгоритма для задачи дуализации, которая сформулирована как задача построения неприводимых покрытий булевой матрицы. Данное понятие предъявляет более слабые требования к числу «лишних» шагов алгоритма по сравнению с понятием асимптотически оптимального алгоритма, введенного впервые ранее. Для случая когда число строк в матрице не меньше числа столбцов (в этом случае не удается построить асимптотически оптимальные алгоритмы для рассматриваемой задачи), показана асимптотическая эффективность алгоритмов, основанных на перечислении с полиномиальной задержкой «совместимых» наборов столбцов булевой матрицы. Аналогичный результат получен для задачи поиска максимальных конъюнкций монотонной булевой функции, заданной конъюнктивной нормальной формой. Библ. 20.

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

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

Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2012, 52:10, 1472–1481

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

Тип публикации: Статья
УДК: 519.7
Поступила в редакцию: 14.03.2012

Образец цитирования: Е. В. Дюкова, Р. М. Сотнезов, “О сложности задачи дуализации”, Ж. вычисл. матем. и матем. физ., 52:10 (2012), 1926–1935; Comput. Math. Math. Phys., 52:10 (2012), 1472–1481

Цитирование в формате AMSBIB
\RBibitem{DyuSot12}
\by Е.~В.~Дюкова, Р.~М.~Сотнезов
\paper О~сложности задачи дуализации
\jour Ж. вычисл. матем. и матем. физ.
\yr 2012
\vol 52
\issue 10
\pages 1926--1935
\mathnet{http://mi.mathnet.ru/zvmmf9772}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3150300}
\zmath{https://zbmath.org/?q=an:1274.68137}
\transl
\jour Comput. Math. Math. Phys.
\yr 2012
\vol 52
\issue 10
\pages 1472--1481
\crossref{https://doi.org/10.1134/S0965542512100090}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/zvmmf9772
  • http://mi.mathnet.ru/rus/zvmmf/v52/i10/p1926

    ОТПРАВИТЬ: 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

    Эта публикация цитируется в следующих статьяx:
    1. Е. В. Дюкова, П. А. Прокофьев, “Об асимптотически оптимальном перечислении неприводимых покрытий булевой матрицы”, ПДМ, 2014, № 1(23), 96–105  mathnet
    2. Е. В. Дюкова, П. А. Прокофьев, “Об асимптотически оптимальных алгоритмах дуализации”, Ж. вычисл. матем. и матем. физ., 55:5 (2015), 895–910  mathnet  crossref  mathscinet  zmath  elib; E. V. Djukova, P. A. Prokofjev, “Asymptotically optimal dualization algorithms”, Comput. Math. Math. Phys., 55:5 (2015), 891–905  crossref  isi  elib
  • Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Просмотров:
    Эта страница:233
    Полный текст:55
    Литература:32
    Первая стр.:18
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021