Разработка и программная реализация эффективных дискретных алгоритмов минимизации булевых функций в классе полиномиальных нормальных форм с фиксированной полярностью

• Автор: Акинин, Андрей Александрович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Воронеж
• Количество страниц: 143 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1 РАЗРАБОТКА МЕТОДИКИ СРАВНИТЕЛЬНОЙ ОЦЕНКИ ЭФФЕКТИВНОСТИ ДИСКРЕТНЫХ АЛГОРИТМОВ
ПОЛИНОМИАЛЬНОГО ПРЕОБРАЗОВАНИЯ БУЛЕВЫХ ФУНКЦИЙ
1.1 Структурные и математические модели тестопригодных полиномиальных логических преобразователей
1.2 Особенности аналитических методов полиномиального преобразования булевых функций
1.3 Методика сравнительной эффективности дискретных алгоритмов полиномиального преобразования на основе метода неопределенных коэффициентов
Цель работы и задачи исследования
2 РАЗРАБОТКА АЛЬТЕРНАТИВНЫХ ДИСКРЕТНЫХ АЛГОРИТМОВ ПРЕОБРАЗОВАНИЯ БУЛЕВЫХ ФУНКЦИЙ К ПОЛИНОМУ ЖЕГАЛКИНА
2.1 Алгоритмы преобразования на основе метода неопределенных коэффициентов
2.2 Алгоритм пэеобразования на основе частных полиномиальных нормальных форм
2.3. Алгоритм преобразования на основе метода конечных разностей
2.4 Алгоритм фрактального полиномиального разложения булевых функций
2.5 Алгоритм бинарно-векторного разложения булевых функций.

Выводы
3 РАЗРАБОТКА АЛЬТЕРНАТИВНЫХ ДИСКРЕТНЫХ АЛГОРИТМОВ ПРЕОБРАЗОВАНИЯ БУЛЕВЫХ ФУНКЦИЙ К
МИНИМИЗИРОВАННЫМ ПОЛЯРИЗОВАННЫМ ПОЛИНОМАМ РИДА-МАЛЛЕРА
3.1 Общие подходы к преобразованию булевых функций в

поляризованные полиномы Рида-Маллера
3.2 Алгоритмы преобразования к поляризованным полиномам на

основе предварительной поляризации булевых функций
3.3 Алгоритмы преобразования к поляризованным полиномам на

основе поляризации полинома Жегалкина
Выводы
4 РАЗРАБОТКА И ВЕРИФИКАЦИЯ ПРОБЛЕМНО-ОРИЕНТИРОВАННОГО ПРОГРАММОГО КОМПЛЕКСА

МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ В КЛАССЕ ПОЛИНОМИАЛЬНЫХ НОРМАЛЬНЫХ ФОРМ С ФИКСИРОВАННОЙ ПОЛЯРНОСТЬЮ
4.1 Разработка структуры и интерфейса программного комплекса
4.2 Разработка программного модуля восстановления дизъюнктивной ^
нормальной формы булевой функции до совершенной формы
4.3 Разработка программного модуля минимизации поляризованных полиномов Рида-Маллера
4.4 Верификация программных модулей преобразования булевых функций к полиному Жегалкина

Выводы
ЗАКЛЮЧЕНИЕ
УСЛОВНЫЕ ОБОЗНАЧЕНИЯ
СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЯ

Цель работы и задачи исследования
На основе проведенного анализа структурных и математических моделей матричных структур, ориентированных на реализацию тестопригодных логических преобразователей, показано, что для их практической реализации необходимо представление исходных булевых функций (БФ) в виде полиномиальных нормальных форм (ПНФ) - в виде полиномов Рида-Малера с фиксированной полярностью.
Среди множества полиномиальных нормальных форм существуют полиномы, характеризующиеся минимальной структурной формулой, под которой традиционно понимается формула, содержащая наименьшее количество конъюнктивных членов.
Определены на основе анализа доступной научно-технической литературы следующие аналитические методы преобразования БФ в полиномиальные нормальные формы: метод неопределенных коэффициентов; метод частных полиномиальнь х форм; метод на основе булева дифференциального исчисления; метод, базирующийся на преобразовании вектора значений функции (позитивное разложение Давио).
Для полиномиального преобразования БФ к поляризованным полиномам Рида-Малера возможны два подхода: первый базируется на предварительной поляризации исходной булевой функции и последующего преобразования её к полиному Жегалкина, а второй - на предварительном определении полинома Жегалкина с последующей его поляризацией.
Предложен теоретический подход к оценке вычислительной сложности альтернативных алгоритмов преобразования булевых функций к полиномиальной форме, базирующийся на геометрической (табличной) модели аналитического метода неопределенных коэффициентов, позволяющий ранжировать различные алгоритмы преобразования по их вычислительной сложности без программной их реализации.