Аннотация:
Исследуются вопросы построения эффективных алгоритмов для труднорешаемых дискретных задач. Рассматриваются перечислительные задачи, труднорешаемость которых имеет два аспекта: экспоненциальный рост числа решений при увеличении размера задачи и сложность их нахождения (перечисления). Главной перечислительной задачей считается дуализация монотонной конъюнктивной нормальной формы. Эквивалентной задачей является поиск неприводимых покрытий булевой матрицы. Для задачи поиска неприводимых покрытий булевой матрицы и обобщений этой задачи на случай целочисленной матрицы получены асимптотики типичного числа решений. Эти оценки необходимы, в частности, для обоснования существования асимптотически оптимальных алгоритмов монотонной дуализации и ее обобщений. Библ. 15.
Образец цитирования:
Е. В. Дюкова, Ю. И. Журавлев, “Задача монотонной дуализации и ее обобщения: асимптотические оценки числа решений”, Ж. вычисл. матем. и матем. физ., 58:12 (2018), 2153–2168; Comput. Math. Math. Phys., 58:12 (2018), 2064–2077
\RBibitem{DyuZhu18}
\by Е.~В.~Дюкова, Ю.~И.~Журавлев
\paper Задача монотонной дуализации и ее обобщения: асимптотические оценки числа решений
\jour Ж. вычисл. матем. и матем. физ.
\yr 2018
\vol 58
\issue 12
\pages 2153--2168
\mathnet{http://mi.mathnet.ru/zvmmf10811}
\crossref{https://doi.org/10.31857/S004446690003559-5}
\elib{https://elibrary.ru/item.asp?id=36759183}
\transl
\jour Comput. Math. Math. Phys.
\yr 2018
\vol 58
\issue 12
\pages 2064--2077
\crossref{https://doi.org/10.1134/S0965542518120102}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000458237300014}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85062098601}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/zvmmf10811
https://www.mathnet.ru/rus/zvmmf/v58/i12/p2153
Эта публикация цитируется в следующих 4 статьяx:
Е. В. Дюкова, Г. О. Масляков, Д. С. Янаков, “Корректная классификация по прецедентам: ДСМ-метод над произведением частичных порядков”, Информ. и её примен., 18:3 (2024), 61–68
N. A. Dragunov, E. V. Djukova, A. P. Djukova, “Logical Classification Based on Finding Regular Representative Elementary Classifiers”, J. Comput. Syst. Sci. Int., 63:4 (2024), 634
Nikita Dragunov, Elena Djukova, 2021 International Conference on Information Technology and Nanotechnology (ITNT), 2021, 1
Anvar Kabulov, Erkin Urunbayev, Aziz Ashurov, 2019 International Conference on Information Science and Communications Technologies (ICISCT), 2019, 1
Цитирование в формате AMSBIB
Обратная связь: