|
Ж. вычисл. матем. и матем. физ., 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
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
Е. В. Дюкова, П. А. Прокофьев, “Об асимптотически оптимальном перечислении неприводимых покрытий булевой матрицы”, ПДМ, 2014, № 1(23), 96–105
-
Е. В. Дюкова, П. А. Прокофьев, “Об асимптотически оптимальных алгоритмах дуализации”, Ж. вычисл. матем. и матем. физ., 55:5 (2015), 895–910
; E. V. Djukova, P. A. Prokofjev, “Asymptotically optimal dualization algorithms”, Comput. Math. Math. Phys., 55:5 (2015), 891–905
|
Просмотров: |
Эта страница: | 233 | Полный текст: | 55 | Литература: | 32 | Первая стр.: | 18 |
|