ПАРАЛЛЕЛЬНАЯ ПРОВЕРКА ДНФ НА ТАВТОЛОГИЮ
Аннотация
Рассматривается одна из базовых задач логико-комбинаторных вычислений – проверка дизъюнктивной нормальной формы на тавтологию. Предлагаются два алгоритма параллельного решения этой задачи с использованием многопроцессорных систем. Приводятся результаты экспериментальных испытаний предложенных алгоритмов на суперкомпьютере семейства СКИФ, показывающие эффективность параллельных вычислений при решении логико-комбинаторной задачи.
Об авторе
Н. Р. Торопов
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Список литературы
1. Закревский А.Д. Алгоритмы синтеза дискретных автоматов. - М.: Наука, 1971.
2. Уткин А.А. Экспериментальное исследование алгоритмов «выполнимость» // Автоматика и вычислительная техника. - 1960. - № 6. - С. 66-74.
3. Crawford J.M., Auton L.D. Experimental results on the crossover point in random 3-SAT // Artificial Intelligence. - 1996. - 81(1). - P. 31-57.
4. Торопов Н.Р. Минимизация систем булевых функций в классе ДНФ // Логическое проектирование: сб. науч. тр. - Мн: Ин-т техн. кибернетики НАН Беларуси, 1999. - Вып. 4. - С. 4-19.
5. Торопов Н.Р. Инверсия системы ДНФ // Логическое проектирование: сб. науч. тр. - Мн: Ин-т техн. кибернетики НАН Беларуси, 1999. - Вып. 4. - С. 20-33.
6. Принципы построения суперкомпьютеров семейства «СКИФ» и их реализация / С.М. Абрамов, Н.Н. Парамонов, В.В. Анищенко и др. // Информатика. - 2004. - № 1. - С. 89-106.
7. Gropp W., Lusk E., Skjellum A. Using MPI: Portable parallel programming with message passing interface. - MIT Press, 1999.
Для цитирования:
Торопов Н.Р.
ПАРАЛЛЕЛЬНАЯ ПРОВЕРКА ДНФ НА ТАВТОЛОГИЮ. Информатика. 2005;(2(6)):35-42.
Просмотров: 592
Послать статью по эл. почте 