Дискретные функции и выполнимость ограничений
Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"
Лекции - 2 ч в неделю, семинары - 1 ч в неделю
Лектор — доцент Селезнева Светлана Николаевна
Программа курса
- Единичный n-мерный куб. Функции алгебры логики. Полином Жегалкина. Некоторые свойства полиномов Жегалкина. Быстрый способ построения полинома Жегалкина функции алгебры логики.
- Поляризованные полиномиальные формы (ППФ). Длина функции в классе ППФ. Теорема Перязева о длине функций алгебры логики в классе ППФ. Теорема о длине почти всех функций в классе ППФ. Сложность системы функций в классе ППФ. Теорема о сложности систем функций алгебры логики, содержащих хотя бы две функции, в классе ППФ.
- Полиномиальные нормальные формы (ПНФ). Длина функции в классе ПНФ. Нижняя мощностная оценка длины функций алгебры логики в классе ПНФ. Теорема Кириченко об оценке длины функций алгебры логики в классе ПНФ через затеняющее множество куба. Покрытия матриц. Градиентное покрытие матрицы. Лемма о градиентном покрытии. Оценка затеняющего множества куба. Верхняя оценка длины функций алгебры логики в классе ПНФ.
- Приближения функций алгебры логики полиномами. Леммы о свойствах биномиальных коэффициентов и их сумм. Теорема о ранге полиномов, приближающих функции алгебры логики с точностью d, 0 < d < 1, и с точностью до одной точки. Лемма о приближении функции алгебры логики на множестве. Теорема о длине полиномов, приближающих функции алгебры логики с точностью d, 0 < d < 1, и с точностью до одной точки..
- Задачи распознавания свойств. Классы P и NP. Полиномиальные, NP-трудные и NP-полные задачи. NP-полнота задач распознавания выполнимости КНФ (ВЫП) и 3-КНФ (3-ВЫП), полиномиальность задачи распознавания выполнимости 2-КНФ (2-ВЫП). Постановка задачи обобщенной выполнимости S-ВЫП.
- Имплицента, простая имплицента функции алгебры логики. Леммы об имплицентах функции алгебры логики. Сокращенная КНФ функции и способы ее построения.
- Слабо положительные, слабо отрицательные и биюнктивные КНФ и слабо положительные, слабо отрицательные и биюнктивные функции алгебры логики. Критерии слабой положительности, слабой отрицательности и биюнктивности функции. Полиномиальность распознавания выполнимости слабо положительной, слабо отрицательной и биюнктивной КНФ.
- Линейные и мультиаффинные функции алгебры логики. Приведенное представление мультиаффинной функции алгебры логики. Критерий мультиаффинности функции. Полиномиальность распознавания выполнимости конъюнкции приведенных представлений мультиаффинных функций.
- Условная выразимость функций алгебры логики, леммы об условной выразимости функций (о транзитивности, о замене множителя в конъюнктивной форме, о подстановке констант вместо переменных и о навешивании отрицаний над переменными). Лемма о функции, сохраняющей константу 0, и функции, не сохраняющей константу 1. Лемма о функции, не являющейся четной. Лемма о функции, не являющейся слабо положительной, и функции, не являющейся слабо отрицательной. Леммы о небиюнктивной функции и немультиаффинной функции. Теорема разделимости Шефера о сложности задачи обобщенной выполнимости S-ВЫП.
- NP-полнота задач распознавания слабой положительности, слабой отрицательности, биюнктивности и мультиаффинности функции алгебры логики, заданной в виде ДНФ. Нижняя единица функции. Лемма о нахождении всех нижних единиц функции алгебры логики по ее полиному Жегалкина. Полиномиальность задачи распознавания монотонности функции алгебры логики, заданной в виде полинома Жегалкина. Лемма о числе сомножителей в приведенном представлении мультиаффинной функции. Полиномиальность распознавания мультиаффинности функции алгебры логики, заданной в виде полинома Жегалкина.
Программа семинарских занятий
Семинар 1. Повторение. 1. Построить сокращенную ДНФ данной функции алгебры логики по ее ДНФ или по ее КНФ.
2. Быстрым способом построить полином Жегалкина данной функции алгебры логики.
Семинар 2. ППФ. 1. Быстрым способом построить ППФ по заданному вектору поляризации для данной функции алгебры логики.
2. Построить классификацию всех функций алгебры логики, зависящих от 2-х переменных, по длине в классе ППФ.
3. Построить классификацию всех функций алгебры логики, зависящих от 3-х переменных, по длине в классе ППФ.
Семинар 3. ПНФ. 1. Построить ПНФ для данной функции алгебры логики по затеняющему множеству единичного n-мерного куба.
2. Найти точную оценку длины функций алгебры логики, зависящих от 2-х переменных, в классе ПНФ.
3. Найти точную оценку длины функций алгебры логики, зависящих от 3-х переменных, в классе ПНФ.
Семинар 4. 1. Найти точную оценку ранга полиномов, приближающих функции алгебры логики, с точностью до одной точки.
2. Найти точную оценку ранга полиномов, приближающих функции алгебры логики, с точностью до двух точек.
3. Найти асимптотику длины полиномов, приближающих функции алгебры логики, с точностью до одной точки.
Семинар 5. 1. Доказать полиномиальность задач распознавания линейности функции алгебры логики, заданной совершенной ДНФ и сокращенной ДНФ.
2. Доказать полиномиальность задач распознавания монотонности функции алгебры логики, заданной совершенной ДНФ и сокращенной ДНФ.
3. Доказать полиномиальность задачи распознавания самодвойственности функции алгебры логики, заданной совершенной ДНФ.
4. Доказать полиномиальность проверки несуществования двух противоположных выполняющих наборов монотонной ДНФ.
Экзамен
В билете 2 вопроса и задача. Один вопрос в билете может содержать несколько вопросов из списка вопросов к экзамену. Подготовка к ответу на билет - 1 ч.
