Тип публикации: диссертация
Год издания: 2007
Аннотация: Изучена сложность тестирования и сложность полиномиальных представлений булевых функций. Цели: найти связь сложности специальной операторной формы со сложностью булевых функций; перенести операторный подход, развитый для булевых функций, на спектральную теорию; описать связь двоичного спектра со сложностью булевых функций; исследовПоказать полностьюать верхнюю оценку функции Шеннона для проверяющих тестов относительно бесповторной альтернативы; исследовать вопросы построения минимальных представлений булевых функций большой размерности в различных классах полиномиальных форм. Найдено точное значение функции Шеннона для проверяющих тестов относительно бесповторной альтернативы и алгоритм построения таких тестов; найдены соотношения, позволяющие вычислить сложность булевых функций в классе операторных пучков и классе всех операторных форм с использованием сложности специальной операторной формы. С использованием операторного подхода введено понятие кронекерова спектра булевых функций, найдены способ построения таких спектров и метод вычисления сложности булевых функций в классе кронекеровых форм. Сформулированы и реализованы алгоритмы построения минимальных представлений булевых функций в классе кронекеровых форм и в классе полиномиальных нормальных форм.