РЕШЕНИЕ СИСТЕМЫ ДИЗЪЮНКТИВНЫХ УРАВНЕНИЙ МЕТОДОМ ПЕРЕМНОЖЕНИЯ ДНФ
Аннотация
Рассматривается система логических уравнений, представленных в дизъюнктивной нормальной форме (ДНФ), и предлагаются алгоритмы поиска всех ее корней, базирующиеся на операции перемножения ДНФ. Алгоритмы реализованы биполярными программами. Один полюс активизируется при большом числе неизвестных (n > 32), когда приходится использовать «дорогостоящие» операции над длинными векторами (превышающими длину машинного слова). Другой полюс действует при малом числе неизвестных (n £ 32), когда можно использовать векторное представление булевых функций и более быстрые операции над короткими векторами, что приводит к значительному ускорению процесса решения. Приводятся результаты экспериментальных испытаний алгоритмов на потоках псевдослучайных систем логических уравнений и на примерах конкретных систем из практики логического проектирования.
Список литературы
1. Закревский, А.Д. Логические уравнения. Изд. 2-е стереотипное / А.Д. Закревский. – М.: Едиториал УРСС, 2003. – 96 с.
2. Закревский, А.Д. Алгоритмы синтеза дискретных автоматов / А.Д. Закревский. – М.: Наука, 1971. – 512 с.
3. Закревский, А.Д. Решение логических уравнений / А.Д. Закревский // Логическое проектирование. – Минск: Ин-т техн. кибернетики НАН Беларуси, 2001. – С. 51–68.
4. Posthoff, Ch. Binare Gleichungen: Algorithmen und Programme / Ch. Posthoff, B. Steinbach. – Karl-Marx-St., 1978.
5. Baumann, M. Criptoanaly of the Hagelin M-209 Machine / M. Baumann, R. Rohde, R. Barthel // 3rd International Workshop on Boolean Problems, Sept. 17–18, 1998. – Freiberg (Sachsen). Germany, 1998. – P. 109–116.
6. Нильсон, Н. Искусственный интеллект. Методы поиска решений / Н. Нильсон. – М.: Наука, 1971. – 512 с.
7. Zakrevskij, A.D. Parallel operations over neighbors in Boolean space / A.D. Zakrevskij // Proc. of the Sixth International Conference CAD DD-07. – Minsk, 2007. – Vol. 2. – P. 6–13.
8. Торопов, Н.Р. Минимизация систем булевых функций в классе ДНФ / Н.Р. Торопов // Логическое проектирование: cб. науч. тр. – Минск: Ин-т техн. кибернетики НАН Беларуси, 1999. – Вып. 4. – С. 4–19.
9. Торопов, Н.Р. Раздельная минимизация булевых функций в системе с поляризацией их значений / Н.Р. Торопов // Методы логического проектирования. – Минск: ОИПИ НАН Беларуси, 2002. – С. 44–55.
10. Романов, В.И. Булевы векторы и матрицы в С++ / В.И. Романов, И.В. Василькова //
11. Логическое проектирование. – Минск: Ин-т техн. кибернетики НАН Беларуси, 1997. – С. 150–158.
12. Черемисинов, Д.И. Троичные векторы и матрицы / Д.И. Черемисинов, Л.Д. Черемисинова // Логическое проектирование. – Минск: Ин-т техн. кибернетики НАН Беларуси, 1998. – С. 146–155.
13. Романов, В.И. Программные средства для решения логико-комбинаторных задач / В.И. Романов // Информатика. – 2005. – № 4. – С. 114–123.
Рецензия
Для цитирования:
Торопов Н.Р. РЕШЕНИЕ СИСТЕМЫ ДИЗЪЮНКТИВНЫХ УРАВНЕНИЙ МЕТОДОМ ПЕРЕМНОЖЕНИЯ ДНФ. Информатика. 2008;(3(19)):81-89.
Просмотров: 528
Послать статью по эл. почте 