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

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

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

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

Экзамен

Досрочный экзамен состоится 18 декабря 2015 г. Начало в 14 ч.

В билете 2 вопроса и задача. Один вопрос в билете может содержать несколько вопросов из списка вопросов к экзамену. Подготовка к ответу на билет - 1 ч.

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

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

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

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

Лекция 4. Покрытия матриц. Градиентное покрытие матрицы. Лемма о градиентном покрытии. Оценка затеняющего множества куба. Верхняя оценка длины функций алгебры логики в классе ПНФ.

Лекция 5. Приближения функций алгебры логики полиномами. Леммы о свойствах биномиальных коэффициентов и их сумм. Теорема о ранге полиномов, приближающих функции алгебры логики с заданной точностью.

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

Лекция 7. Задачи распознавания свойств. Задачи из классов P и NP. Полиномиальные, NP-трудные и NP-полные задачи. Линейные функции алгебры логики. Обоснование нелинейности функции. NP-полнота задачи распознавания нелинейности функции алгебры логики, заданной в виде ДНФ. Монотонные функции алгебры логики. Обоснование немонотонности функции. NP-полнота задачи распознавания немонотонности функции алгебры логики, заданной в виде ДНФ.

Лекция 8. Нижняя единица и верхний ноль функции. Лемма о нахождении всех нижних единиц функции алгебры логики по ее полиному Жегалкина. Полиномиальность задачи распознавания монотонности функции алгебры логики, заданной в виде полинома Жегалкина.

Лекция 9. NP-полнота задачи распознавания несамодвойственности функции алгебры логики, заданной в виде ДНФ. Четные функции. Лемма о соотношении между самодвойственными и четными функциями алгебры логики. Леммы о свойствах полиномов Жегалкина четных функций алгебры логики. Полиномиальность задачи распознавания самодвойственности функции алгебры логики, заданной в виде полинома Жегалкина.

Лекция 10. NP-полнота задачи выполнимости системы функций алгебры логики, заданных в виде полиномов Жегалкина. Вес функции алгебры логики. NP-трудность задачи распознавания равенства веса n-местной функции алгебры логики, заданной в виде полинома Жегалкина, числу 2^{n-1}. Выражение коэффициентов полинома Жегалкина функции алгебры логики через ее значения. Критерий четности веса функции алгебры логики. Полиномиальность задачи распознавания кратности веса функции алгебры логики, заданной в виде полинома Жегалкина, числу 2^m, где m -- заранее известное натуральное число.

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

Семинар 1. ППФ.

Семинар 2. 1. Найти точную оценку длины функций алгебры логики, зависящих от 2-х переменных, в классе ПНФ.

2. Найти точную оценку длины функций алгебры логики, зависящих от 3-х переменных, в классе ПНФ.

Семинар 3. 1. Найти градиентное покрытие заданных матриц.

Семинар 4. 1. Найти точную оценку ранга полиномов, приближающих функции алгебры логики, с точностью до одной точки.

2. Найти точную оценку ранга полиномов, приближающих функции алгебры логики, с точностью до двух точек.

3. Найти асимптотику длины полиномов, приближающих функции алгебры логики, с точностью до одной точки.

Семинар 5. 1. Доказать полиномиальность задач распознавания линейности функции алгебры логики, заданной совершенной ДНФ и сокращенной ДНФ.

2. Доказать полиномиальность задач распознавания монотонности функции алгебры логики, заданной совершенной ДНФ и сокращенной ДНФ.

3. Доказать полиномиальность задачи распознавания самодвойственности функции алгебры логики, заданной совершенной ДНФ.

4. Доказать полиномиальность проверки несуществования двух противоположных выполняющих наборов монотонной ДНФ.