ПАРАЛЛЕЛЬНАЯ ПРОВЕРКА ДНФ НА ТАВТОЛОГИЮ
Abstract
Рассматривается одна из базовых задач логико-комбинаторных вычислений – проверка дизъюнктивной нормальной формы на тавтологию. Предлагаются два алгоритма параллельного решения этой задачи с использованием многопроцессорных систем. Приводятся результаты экспериментальных испытаний предложенных алгоритмов на суперкомпьютере семейства СКИФ, показывающие эффективность параллельных вычислений при решении логико-комбинаторной задачи.
About the Author
Н. Торопов
Объединенный институт проблем информатики НАН Беларуси
Belarus
References
1. Zakrevskii A.D. Algoritmy sinteza diskretnykh avtomatov. - M.: Nauka, 1971.
2. Utkin A.A. Eksperimental'noe issledovanie algoritmov «vypolnimost'» // Avtomatika i vychislitel'naya tekhnika. - 1960. - № 6. - S. 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. Toropov N.R. Minimizatsiya sistem bulevykh funktsii v klasse DNF // Logicheskoe proektirovanie: sb. nauch. tr. - Mn: In-t tekhn. kibernetiki NAN Belarusi, 1999. - Vyp. 4. - S. 4-19.
5. Toropov N.R. Inversiya sistemy DNF // Logicheskoe proektirovanie: sb. nauch. tr. - Mn: In-t tekhn. kibernetiki NAN Belarusi, 1999. - Vyp. 4. - S. 20-33.
6. Printsipy postroeniya superkomp'yuterov semeistva «SKIF» i ikh realizatsiya / S.M. Abramov, N.N. Paramonov, V.V. Anishchenko i dr. // Informatika. - 2004. - № 1. - S. 89-106.
7. Gropp W., Lusk E., Skjellum A. Using MPI: Portable parallel programming with message passing interface. - MIT Press, 1999.
For citations:
. Informatics. 2005;(2(6)):35-42.
(In Russ.)
Views: 597
Email this article 