Тип публикации: статья из журнала
Год издания: 2015
Ключевые слова: выполнимость, Sat, конъюнктивная нормальная форма, литерал, клоз, NP-полнота, DPLL-алгоритмы, PPSZ-алгоритмы, алгоритмы расщепления, декомпозиционные алго-ритмы, правила редукции.
Аннотация: В статье исследуется задача о пропозициональной выполнимости и известные алгоритмы ее решения. Приведено обоснование её значимости как широко применимой задачи, для которой впервые было сформулировано и доказано свойство NP-полноты. Автором разработана и описана программа, реализованная на основе DPLL-алгоритма, позволяющая найти рПоказать полностьюешение задачи о пропозициональной выполнимости.
Журнал: Молодой ученый
Выпуск журнала: № 24
Номера страниц: 8-12
ISSN журнала: 20720297
Место издания: Казань
Издатель: Общество с ограниченной ответственностью Издательство Молодой ученый