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

[[Категория:Лекционные курсы кафедры МК]]
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]
[[Категория:Спецкурсы кафедры МК]]

Обязательный курс для студентов 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. Повторение'''.

[[Media: dfvo-l1-selezn.pdf | Лекция 1]]. Вступление. Алгебра логики. Функции алгебры логики. Формулы. Полнота. Замкнутые классы. Классы T_0, T_1, L, S, M. Теорема Поста.

[[Media: dfvo-l2-selezn.pdf | Лекция 2]]. Конъюнктивные нормальные формы. Имплицента, простая имплицента функции. Сокращенная КНФ функции. Способы построения сокращенной КНФ.

[[Media: dfvo-l3-selezn.pdf | Лекция 3]]. Полином Жегалкина. Способы построения полинома Жегалкина функции. Линейная имплицента функции. Линейная конъюнктивная нормальная форма (ЛКНФ). Линейная соимплицента функции. Поиск всех линейных соимплицент функции. 

[[Media: dfvo-l4-selezn.pdf | Лекция 4]].  Задачи распознавания. Вычислительная сложность задачи. Классы P и NP, NP-полные задачи. NP-полнота задачи 3-раскраски графов. Задача обобщенной выполнимости.

Коллоквиум 1.

'''Часть 2. Обобщенная выполнимость'''.

[[Media: dfvo-l5-selezn.pdf | Лекция 5]]. Слабо положительные и слабо отрицательные КНФ и функции. Критерии слабой положительности и слабой отрицательности функции. Полиномиальность проверки выполнимости слабо положительной и слабо отрицательной КНФ.

[[Media: dfvo-l6-selezn.pdf | Лекция 6]]. Биюнктивные КНФ и функции. Критерий биюнктивности функции. Полиномиальность проверки выполнимости биюнктивной КНФ. Полиномиальность поиска решения выполнимой биюнктивной КНФ.

[[Media: dfvo-l7-selezn.pdf | Лекция 7]]. ЛКНФ и мультиаффинные функции. Критерий мультиаффинности функции. Полиномиальность проверки выполнимости ЛКНФ. Полиномиальность проверки по полиному Жегалкина представимости функции в виде ЛКНФ. Функции, сохраняющие константу.

[[Media: dfvo-l8-selezn.pdf | Лекция 8]]. Условная выразимость функций. Леммы об условной выразимости. Лемма о функции, не сохраняющий единицу, и о функции, сохраняющей ноль. Лемма о несамодополнительной функции. Лемма о самодополнительной функции.

Лекция 9. Лемма о не слабо положительной функции и не слабо отрицательной функции. Лемма о небиюнктивной функции и немультиаффинной функции. Условная выразимость дизъюнкции трех литералов.

Лекция 10. Теорема разделимости Шефера. Примеры.

Коллоквиум 2.

'''Часть 3. Выполнимость ограничений'''.

Лекция 11. Предикаты на конечном множестве. Формулы, S-формулы и замкнутые классы предикатов. Задача обобщенной выполнимости S-ВЫП. Вычислительная сложность некоторых задач S-ВЫП.

Лекция 12. Функции на конечном множестве. Формулы и замкнутые классы функций. Сохранение предиката функцией,  полиморфизмы. Двузначный случай. Вычислительная сложность некоторых задач S-ВЫП. Теорема разделимости.

Коллоквиум 3.

==Семинары==

[[Media: dfvo-s1-selezn.pdf | Занятие 1]]. Сокращенная КНФ и способы ее построения.

[[Media: dfvo-s2-selezn.pdf | Занятие 2]]. Полином Жегалкина. ЛКНФ и представимость ЛКНФ.

[[Media: dfvo-s3-selezn.pdf | Занятие 3]]. Классы P и NP, NP-полнота.

[[Media: dfvo-s4-selezn.pdf | Занятие 4]]. Слабо положительные и слабо отрицательные функции. 

[[Media: dfvo-s5-selezn.pdf | Занятие 5]]. Биюнктивные и мультиаффинные функции. 

[[Media: dfvo-s6-selezn.pdf | Занятие 6]]. Теорема разделимости Шефера.

[[Media: dfvo-s7-selezn.pdf | Занятие 7]]. Доказательство NP-полноты некоторых задач.
 
[[Media: dfvo-s8-selezn.pdf | Занятие 8]]. Доказательство полиномиальности некоторых задач.

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

*Функции алгебры логики. Конъюнктивные и дизъюнктивные нормальные формы (КНФ и ДНФ). Сокращенная КНФ и способы ее построения. Полиномы Жегалкина, быстрый способ построения полинома Жегалкина функции. Линейные конъюнктивные нормальные формы (ЛКНФ). Проверка представимости функции ЛКНФ. 

*Задачи распознавания свойств. Классы P и NP. Полиномиальные, NP-трудные и NP-полные задачи. NP-полнота задач распознавания выполнимости КНФ (ВЫП) и 3-КНФ (3-ВЫП), полиномиальность задачи распознавания выполнимости 2-КНФ (2-ВЫП). Постановка задачи обобщенной выполнимости S-ВЫП. 

*Слабо положительные, слабо отрицательные и биюнктивные КНФ и слабо положительные, слабо отрицательные и биюнктивные функции алгебры логики. Критерии слабой положительности, слабой отрицательности и биюнктивности функции. Полиномиальность распознавания выполнимости слабо положительной, слабо отрицательной и биюнктивной КНФ. 

*Линейные и мультиаффинные функции алгебры логики. Приведенное представление мультиаффинной функции алгебры логики. Критерий мультиаффинности функции. Полиномиальность распознавания выполнимости конъюнкции приведенных представлений мультиаффинных функций. 

*Условная выразимость функций алгебры логики, леммы об условной выразимости функций (о транзитивности, о замене множителя в конъюнктивной форме, о подстановке констант вместо переменных и о навешивании отрицаний над переменными). Лемма о функции, сохраняющей константу 0, и функции, не сохраняющей константу 1. Лемма о функции, не являющейся самодополнительной. Лемма о функции, не являющейся слабо положительной, и функции, не являющейся слабо отрицательной. Леммы о небиюнктивной функции и немультиаффинной функции. Теорема разделимости Шефера о сложности задачи обобщенной выполнимости S-ВЫП.

==Экзамен==