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