Дискретные функции и выполнимость ограничений — различия между версиями
(→Упражнения) |
|||
| Строка 52: | Строка 52: | ||
*NP-полнота задач распознавания слабой положительности, слабой отрицательности, биюнктивности и мультиаффинности функции алгебры логики, заданной в виде ДНФ. Нижняя единица функции. Лемма о нахождении всех нижних единиц функции алгебры логики по ее полиному Жегалкина. Полиномиальность задачи распознавания монотонности функции алгебры логики, заданной в виде полинома Жегалкина. Лемма о числе сомножителей в приведенном представлении мультиаффинной функции. Полиномиальность распознавания мультиаффинности функции алгебры логики, заданной в виде полинома Жегалкина. | *NP-полнота задач распознавания слабой положительности, слабой отрицательности, биюнктивности и мультиаффинности функции алгебры логики, заданной в виде ДНФ. Нижняя единица функции. Лемма о нахождении всех нижних единиц функции алгебры логики по ее полиному Жегалкина. Полиномиальность задачи распознавания монотонности функции алгебры логики, заданной в виде полинома Жегалкина. Лемма о числе сомножителей в приведенном представлении мультиаффинной функции. Полиномиальность распознавания мультиаффинности функции алгебры логики, заданной в виде полинома Жегалкина. | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
==Экзамен== | ==Экзамен== | ||
Версия 13:04, 3 октября 2018
Обязательный курс для студентов 518/1 группы магистерской программы "Дискретные структуры и алгоритмы".
Спецкурс для студентов магистратуры.
Лекции - 2 ч в неделю.
Семинары - 1 ч в неделю (для студентов 518/1 группы).
Аннотация. Цель курса - показать, каким образом теория дискретных функций применяется при решении задачи обобщенной выполнимости. Задача обобщенной выполнимости, или выполнимости ограничений (англ. constraint satisfaction problem, CSP) состоит в выяснении выполнимости системы отношений, взятых из заранее известного множества S и связывающих произвольные переменные. При этом полагается, что в S входят отношения над конечным множеством A, |A| = k. В курсе показывается, что вычислительная сложность задачи S-выполнимости зависит только от функций, сохраняющих все отношения из S. Первая часть курса посвящена булевой выполнимости (k = 2). В ней рассматривается теорема Шефера о дихотомии вычислительной сложности задачи булевой выполнимости. Вторая часть курса посвящена задаче S-выполнимости для произвольных конечных k > 2. Доказываются случаи NP-полноты этой задачи, а также рассматриваются ее полиномиальные случаи. Приводится теорема о дихотомии вычислительной сложности задачи S-выполнимости для произвольных конечных k.
Лектор - Селезнева Светлана Николаевна
Содержание
Объявления
Лекции
Лекция 1. Функции алгебры логики. Формулы и функции, определяемые формулами. Замкнутые классы и полные системы.
Лекция 2. Конъюнктивные и дизъюнктивные нормальные формы (КНФ и ДНФ). Сокращенная КНФ и способы ее построения.
Лекция 3. Полиномы Жегалкина. Линейная конъюнктивная нормальная форма (ЛКНФ), представимость ЛКНФ.
Упражнения
Занятие 1. Сокращенная КНФ и способы ее построения.
Занятие 2. Полином Жегалкина. ЛКНФ и представимость ЛКНФ.
Занятие 3. Классы P и NP, NP-полнота.
Занятие 4. Слабо положительные, слабо отрицательные и биюнктивные функции.
Занятие 5. Мультиаффинные функции.
Занятие 6. Теорема разделимости Шефера.
Занятие 7. Доказательство NP-полноты некоторых задач.
Занятие 8. Доказательство полиномиальности некоторых задач.
Программа курса
- Функции алгебры логики. Конъюнктивные и дизъюнктивные нормальные формы (КНФ и ДНФ). Сокращенная КНФ и способы ее построения. Полиномы Жегалкина, быстрый способ построения полинома Жегалкина функции. Линейные конъюнктивные нормальные формы (ЛКНФ). Проверка представимости функции ЛКНФ.
- Задачи распознавания свойств. Классы P и NP. Полиномиальные, NP-трудные и NP-полные задачи. NP-полнота задач распознавания выполнимости КНФ (ВЫП) и 3-КНФ (3-ВЫП), полиномиальность задачи распознавания выполнимости 2-КНФ (2-ВЫП). Постановка задачи обобщенной выполнимости S-ВЫП.
- Слабо положительные, слабо отрицательные и биюнктивные КНФ и слабо положительные, слабо отрицательные и биюнктивные функции алгебры логики. Критерии слабой положительности, слабой отрицательности и биюнктивности функции. Полиномиальность распознавания выполнимости слабо положительной, слабо отрицательной и биюнктивной КНФ.
- Линейные и мультиаффинные функции алгебры логики. Приведенное представление мультиаффинной функции алгебры логики. Критерий мультиаффинности функции. Полиномиальность распознавания выполнимости конъюнкции приведенных представлений мультиаффинных функций.
- Условная выразимость функций алгебры логики, леммы об условной выразимости функций (о транзитивности, о замене множителя в конъюнктивной форме, о подстановке констант вместо переменных и о навешивании отрицаний над переменными). Лемма о функции, сохраняющей константу 0, и функции, не сохраняющей константу 1. Лемма о функции, не являющейся четной. Лемма о функции, не являющейся слабо положительной, и функции, не являющейся слабо отрицательной. Леммы о небиюнктивной функции и немультиаффинной функции. Теорема разделимости Шефера о сложности задачи обобщенной выполнимости S-ВЫП.
- NP-полнота задач распознавания слабой положительности, слабой отрицательности, биюнктивности и мультиаффинности функции алгебры логики, заданной в виде ДНФ. Нижняя единица функции. Лемма о нахождении всех нижних единиц функции алгебры логики по ее полиному Жегалкина. Полиномиальность задачи распознавания монотонности функции алгебры логики, заданной в виде полинома Жегалкина. Лемма о числе сомножителей в приведенном представлении мультиаффинной функции. Полиномиальность распознавания мультиаффинности функции алгебры логики, заданной в виде полинома Жегалкина.
Экзамен
Экзамен устный. В билете 2 вопроса и задача. Подготовка к ответу на билет - 1 ч.
