Preview

Информатика

Расширенный поиск

ПАРАЛЛЕЛЬНАЯ ПРОВЕРКА ДНФ НА ТАВТОЛОГИЮ

Аннотация

Рассматривается одна из базовых задач логико-комбинаторных вычислений – проверка дизъюнктивной нормальной формы на тавтологию. Предлагаются два алгоритма параллельного решения этой задачи с использованием многопроцессорных систем. Приводятся результаты экспериментальных испытаний предложенных алгоритмов на суперкомпьютере семейства СКИФ, показывающие эффективность параллельных вычислений при решении логико-комбинаторной задачи.

Об авторе

Н. Р. Торопов
Объединенный институт проблем информатики НАН Беларуси
Беларусь


Список литературы

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.

Просмотров: 472


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)