Параллельный решатель проблемы булевой выполнимости, использующий метод Монте-Карло для поиска эффективных декомпозиций
глобальная оптимизация, Монте-Карло проблема булевой выполнимости
Программа предназначена для решения трудных экземпляров проблемы булевой выполнимости (SAT). На первом этапе с применением метода Монте-Карло осуществляется поиск такого подмножества множества переменных КНФ, которое обеспечит наименьшее прогнозное время решения SAT-задачи для данной КНФ. Путем означивания всех возможных значений переменных из выбранного подмножества формируются подзадачи, которые проще исходной задачи. Задача поиска подмножества с наименьшей оценкой суммарного времени решения всех соответствующих подзадач ставится и решается как задача глобальной оптимизации типа «черный ящик». На втором этапе формируются и обрабатываются все подзадачи по найденному на первом этапе подмножеству. Программа разработана при поддержке совета по грантам Президента Российской федерации (стипендия СП-3545.2019.5) и Российского научного фонда (грант 16-11-10046).
Решение трудных задачи криптографии и комбинаторики, сведенные к проблеме булевой выполнимости.
Александр
Семенов
Анатольевич
ведущий научный сотрудник
Кандидат технических наук
Доцент
R-3844-2016
56659912400
7629
РОССИЯ
Игорь
Бычков
Вячеславович
директор
РОССИЯ
28.23.29
Программная реализация интеллектуальных систем
28.23.17
Логика в искусственном интеллекте
01.02.EP
COMPUTER SCIENCE, ARTIFICIAL INTELLIGENCE
Олег
Заикин
Сергеевич
Разработка архитектуры и алгоритмов программы, реализация программного кода, тестирование
РОССИЯ
Ирина
Грибанова
Александровна
Разработка и реализация алгоритмов работы программы, тестирование
РОССИЯ
РНФ
Российский научный фонд
1137799022261
Организация
Организации, учрежденные юридическими лицами или гражданами, или юридическими лицами и гражданами совместно
Фонды
ИДСТУ СО РАН
Федеральное государственное бюджетное учреждение науки Институт динамики систем и теории управления имени В.М. Матросова Сибирского отделения Российской академии наук)
1023801757000
Организация
Министерство науки и высшего образования Российской Федерации
Федеральные государственные бюджетные учреждения