Дискретные функции и выполнимость ограничений
Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"
Лекции - 2 ч в неделю, семинары - 1 ч в неделю
Лектор — доцент Селезнева Светлана Николаевна
Программа курса
Лекция 1. Единичный n-мерный куб. Функции алгебры логики. Полином Жегалкина. Некоторые свойства полиномов Жегалкина функций алгебры логики.
Лекция 2. Поляризованные полиномиальные формы (ПНФ). Длина функции в классе ПНФ. Теорема Перязева о длине функций алгебры логики в классе ПНФ. Теорема о длине почти всех функций в классе ПНФ. Сложность системы функций в классе ПНФ. Теорема о сложности систем функций алгебры логики, содержащих хотя бы две функции, в классе ПНФ.
Лекция 3. Полиномиальные нормальные формы (ПНФ). Длина функции в классе ПНФ. Теорема Кириченко о длине функций алгебры логики в классе ПНФ.
Программа семинарских занятий
Семинар 1.