Дискретные функции и выполнимость ограничений

Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"

Лекции - 2 ч в неделю, семинары - 1 ч в неделю

Лектор — доцент Селезнева Светлана Николаевна

Программа курса

Лекция 1. Единичный n-мерный куб. Функции алгебры логики. Полином Жегалкина. Некоторые свойства полиномов Жегалкина функций алгебры логики.

Лекция 2. Поляризованные полиномиальные формы (ППФ). Длина функции в классе ППФ. Теорема Перязева о длине функций алгебры логики в классе ППФ. Теорема о длине почти всех функций в классе ППФ. Сложность системы функций в классе ППФ. Теорема о сложности систем функций алгебры логики, содержащих хотя бы две функции, в классе ППФ.

Лекция 3. Полиномиальные нормальные формы (ПНФ). Длина функции в классе ПНФ. Теорема Кириченко о длине функций алгебры логики в классе ПНФ.

Программа семинарских занятий

Семинар 1.