Страница публикации
Применение метода Монте-Карло к прогнозированию параллельного времени решения проблемы булевой выполнимости
Авторы: Заикин О.С., Семенов А.А.
Журнал: Вычисл. методы и программирование
Том: 15
Номер:
Год: 2014
Отчётный год: 2014
Издательство:
Местоположение издательства:
URL:
Аннотация: Рассматривается применение метода Монте-Карло к планированию решения сложных вариантов задачи о булевой выполнимости (SAT, Boolean Satisfiability) в пара ллельных вычислительных системах. Распараллеливание SAT-задачи является результатом выделения в множестве булевых переменных исходной конъюнктивной нормальной формы некоторого подмножества, называемого декомпозиционным множеством. Для декомпозиционных множеств можно естественным образом определить ряд параметров, характеризующих ``качество'' декомпозиции. Для оценки этих параметров предлагается использовать вычислительную схему метода Монте-Карло. В частности, данный метод применен для поиска декомпозиционного множества с наименьшим прогнозным временем решения исходной задачи. Реализована параллельная MPI-программа, с помощью которой на вычислительном кластере был получен прогноз времени решения задачи логического криптоанализа шифра Bivium. Успешно осуществлен логический криптоанализ нескольких ослабленных версий шифра Bivium, проведено сравнение реального времени криптоанализа с прогнозным.}
Индексируется WOS: 0
Индексируется Scopus: 0
Индексируется РИНЦ: 1
Публикация в печати: 0
Добавил в систему: