|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Задача монотонной дуализации и её обобщения: асимптотические оценки числа решенийстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК- Авторы: Дюкова Е.В., Журавлёв Ю.И.
- Журнал: Журнал вычислительной математики и математической физики
- Том: 58
- Номер: 12
- Год издания: 2018
- Издательство: ФГБУ "Издательство "Наука"
- Местоположение издательства: Москва
- Аннотация: Исследуются вопросы построения эффективных алгоритмов для труднорешаемых дискретных задач. Рассматриваются перечислительные задачи, труднорешаемость которых имеет два аспекта: экспоненциальный рост числа решений при увеличении размера задачи и сложность их нахождения (перечисления). Главной перечислительной задачей считается дуализация монотонной конъюнктивной нормальной формы. Эквивалентной задачей является поиск неприводимых покрытий булевой матрицы. Для задачи поиска неприводимых покрытий булевой матрицы и обобщений этой задачи на случай целочисленной матрицы получены асимптотики типичного числа решений. Эти оценки необходимы, в частности, для обоснования существования асимптотически оптимальных алгоритмов монотонной дуализации и её обобщений.
- Добавил в систему: Дюкова Елена Всеволодовна