ПАРАЛЛЕЛЬНАЯ ПРОВЕРКА ДНФ НА ТАВТОЛОГИЮ
Аннотация
Рассматривается одна из базовых задач логико-комбинаторных вычислений – проверка дизъюнктивной нормальной формы на тавтологию. Предлагаются два алгоритма параллельного решения этой задачи с использованием многопроцессорных систем. Приводятся результаты экспериментальных испытаний предложенных алгоритмов на суперкомпьютере семейства СКИФ, показывающие эффективность параллельных вычислений при решении логико-комбинаторной задачи.
Список литературы
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.
Просмотров: 556
Послать статью по эл. почте 