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