Дискретные функции и выполнимость ограничений — различия между версиями
(→Программа курса) |
(→Программа курса) |
||
| Строка 11: | Строка 11: | ||
'''Лекция 2'''. Поляризованные полиномиальные формы (ППФ). Длина функции в классе ППФ. Теорема Перязева о длине функций алгебры логики в классе ППФ. Теорема о длине почти всех функций в классе ППФ. Сложность системы функций в классе ППФ. Теорема о сложности систем функций алгебры логики, содержащих хотя бы две функции, в классе ППФ. | '''Лекция 2'''. Поляризованные полиномиальные формы (ППФ). Длина функции в классе ППФ. Теорема Перязева о длине функций алгебры логики в классе ППФ. Теорема о длине почти всех функций в классе ППФ. Сложность системы функций в классе ППФ. Теорема о сложности систем функций алгебры логики, содержащих хотя бы две функции, в классе ППФ. | ||
| − | '''Лекция 3'''. Полиномиальные нормальные формы (ПНФ). Длина функции в классе ПНФ. Теорема Кириченко о | + | '''Лекция 3'''. Полиномиальные нормальные формы (ПНФ). Длина функции в классе ПНФ. Нижняя мощностная оценка длины функций алгебры логики в классе ПНФ. Теорема Кириченко об оценке длины функций алгебры логики в классе ПНФ через затеняющее множество куба. |
| + | |||
| + | '''Лекция 4'''. Покрытия матриц. Градиентное покрытие матрицы. Лемма о градиентном покрытии. Оценка затеняющего множества куба. Верхняя оценка длины функций алгебры логики в классе ПНФ. | ||
| + | |||
| + | '''Лекция 5'''. Приближения функций алгебры логики полиномами. Леммы о свойствах биномиальных коэффициентов и их сумм. Теорема о ранге полиномов, приближающих функции алгебры логики с заданной точностью. | ||
| + | |||
| + | '''Лекция 6'''. Приближения функций алгебры логики полиномами. Лемма о приближении функции алгебры логики на множестве. Теорема о длине полиномов, приближающих функции алгебры логики с заданной точностью. | ||
| + | |||
| + | '''Лекция 7'''. Задачи распознавания свойств. Задачи из классов P и NP. Полиномиальные, NP-трудные и NP-полные задачи. Линейные функции алгебры логики. Обоснование нелинейности функции. NP-полнота задачи распознавание нелинейности функции алгебры логики, заданной в виде ДНФ. Монотонные функции алгебры логики. Обоснование немонотонности функции. NP-полнота задачи распознавание немонотонности функции алгебры логики, заданной в виде ДНФ. | ||
| + | |||
| + | '''Лекция 8'''. Нижняя единица и верхний ноль функции. Лемма о нахождении всех нижних единиц функции алгебры логики по ее полиному Жегалкина. Полиномиальность задачи распознавания монотонности функции алгебры логики, заданной в виде полинома Жегалкина. | ||
==Программа семинарских занятий== | ==Программа семинарских занятий== | ||
Версия 20:55, 28 октября 2015
Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"
Лекции - 2 ч в неделю, семинары - 1 ч в неделю
Лектор — доцент Селезнева Светлана Николаевна
Программа курса
Лекция 1. Единичный n-мерный куб. Функции алгебры логики. Полином Жегалкина. Некоторые свойства полиномов Жегалкина функций алгебры логики.
Лекция 2. Поляризованные полиномиальные формы (ППФ). Длина функции в классе ППФ. Теорема Перязева о длине функций алгебры логики в классе ППФ. Теорема о длине почти всех функций в классе ППФ. Сложность системы функций в классе ППФ. Теорема о сложности систем функций алгебры логики, содержащих хотя бы две функции, в классе ППФ.
Лекция 3. Полиномиальные нормальные формы (ПНФ). Длина функции в классе ПНФ. Нижняя мощностная оценка длины функций алгебры логики в классе ПНФ. Теорема Кириченко об оценке длины функций алгебры логики в классе ПНФ через затеняющее множество куба.
Лекция 4. Покрытия матриц. Градиентное покрытие матрицы. Лемма о градиентном покрытии. Оценка затеняющего множества куба. Верхняя оценка длины функций алгебры логики в классе ПНФ.
Лекция 5. Приближения функций алгебры логики полиномами. Леммы о свойствах биномиальных коэффициентов и их сумм. Теорема о ранге полиномов, приближающих функции алгебры логики с заданной точностью.
Лекция 6. Приближения функций алгебры логики полиномами. Лемма о приближении функции алгебры логики на множестве. Теорема о длине полиномов, приближающих функции алгебры логики с заданной точностью.
Лекция 7. Задачи распознавания свойств. Задачи из классов P и NP. Полиномиальные, NP-трудные и NP-полные задачи. Линейные функции алгебры логики. Обоснование нелинейности функции. NP-полнота задачи распознавание нелинейности функции алгебры логики, заданной в виде ДНФ. Монотонные функции алгебры логики. Обоснование немонотонности функции. NP-полнота задачи распознавание немонотонности функции алгебры логики, заданной в виде ДНФ.
Лекция 8. Нижняя единица и верхний ноль функции. Лемма о нахождении всех нижних единиц функции алгебры логики по ее полиному Жегалкина. Полиномиальность задачи распознавания монотонности функции алгебры логики, заданной в виде полинома Жегалкина.
Программа семинарских занятий
Семинар 1.
