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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Лекции)
(не показаны 34 промежуточных версий 1 участника)
Строка 16: Строка 16:
  
 
==Объявления==
 
==Объявления==
 +
 +
<!---'''Основной экзамен состоится 12 января. Начало в 10 ч'''.
 +
 +
'''Консультация''' к экзамену состоится '''11 января''' с помощью zoom; ссылка такая же, как и для лекций. Начало '''в 11 ч'''.
 +
 +
'''Просьба ко всем, кто собирается сдавать курс в качестве спецкурса или элективного курса, прислать сообщение об этом лектору [[Селезнева Светлана Николаевна | Селезневой Светлане Николаевне]] по эл. почте'''.
 +
 +
Для сдающих спецкурс экзамен будет проходить в виде письменной работы (10 заданий разной сложности, включающие задачи и вопросы по теории). Продолжительность написания работы - 1 ч 45 мин (105 мин).
 +
 +
Работу нужно написать контрастной ручкой на светлых листах. Затем выполненную работу нужно отсканировать или сфотографировать и сканы/фото загрузить по присланной ссылке. Файлы нужно назвать по фамилии сдающего; форматы файлов pdf, jpg, png.
 +
 +
На сканирование/фотографирование работы отводится 15 мин. Т.е. работу нужно сдать через 2 ч (120 мин) после получения задания.
 +
 +
Вопросы по содержанию курса и проведению экзамена можно задавать лектору [[Селезнева Светлана Николаевна | Селезневой Светлане Николаевне]] по эл. почте.--->
  
 
==Лекции==
 
==Лекции==
Строка 27: Строка 41:
 
[[Media: dfvo-l3-selezn.pdf | Лекция 3]]. Полином Жегалкина. Способы построения полинома Жегалкина функции. Линейная имплицента функции. Линейная конъюнктивная нормальная форма (ЛКНФ). Линейная соимплицента функции. Поиск всех линейных соимплицент функции.  
 
[[Media: dfvo-l3-selezn.pdf | Лекция 3]]. Полином Жегалкина. Способы построения полинома Жегалкина функции. Линейная имплицента функции. Линейная конъюнктивная нормальная форма (ЛКНФ). Линейная соимплицента функции. Поиск всех линейных соимплицент функции.  
  
Лекция 4. Задачи распознавания. Вычислительная сложность задачи. Классы P и NP, NP-полные задачи. NP-полнота задачи 3-раскраски графов. Задача обобщенной выполнимости.
+
[[Media: dfvo-l4-selezn.pdf | Лекция 4]]. Задачи распознавания. Вычислительная сложность задачи. Классы P и NP, NP-полные задачи. NP-полнота задачи 3-раскраски графов. Задача обобщенной выполнимости.
  
 
Коллоквиум 1.
 
Коллоквиум 1.
Строка 37: Строка 51:
 
[[Media: dfvo-l6-selezn.pdf | Лекция 6]]. Биюнктивные КНФ и функции. Критерий биюнктивности функции. Полиномиальность проверки выполнимости биюнктивной КНФ. Полиномиальность поиска решения выполнимой биюнктивной КНФ.
 
[[Media: dfvo-l6-selezn.pdf | Лекция 6]]. Биюнктивные КНФ и функции. Критерий биюнктивности функции. Полиномиальность проверки выполнимости биюнктивной КНФ. Полиномиальность поиска решения выполнимой биюнктивной КНФ.
  
[[Media: dfvo-l7-selezn.pdf | Лекция 7]]. ЛКНФ и мультиаффинные функции. Критерий мультиаффинности функции. Полиномиальность проверки выполнимости ЛКНФ. Функции, сохраняющие константу.
+
[[Media: dfvo-l7-selezn.pdf | Лекция 7]]. ЛКНФ и мультиаффинные функции. Критерий мультиаффинности функции. Полиномиальность проверки выполнимости ЛКНФ. Полиномиальность проверки по полиному Жегалкина представимости функции в виде ЛКНФ. Функции, сохраняющие константу.
  
 
[[Media: dfvo-l8-selezn.pdf | Лекция 8]]. Условная выразимость функций. Леммы об условной выразимости. Лемма о функции, не сохраняющий единицу, и о функции, сохраняющей ноль. Лемма о несамодополнительной функции. Лемма о самодополнительной функции.
 
[[Media: dfvo-l8-selezn.pdf | Лекция 8]]. Условная выразимость функций. Леммы об условной выразимости. Лемма о функции, не сохраняющий единицу, и о функции, сохраняющей ноль. Лемма о несамодополнительной функции. Лемма о самодополнительной функции.
Строка 43: Строка 57:
 
[[Media: dfvo-l9-selezn.pdf | Лекция 9]]. Лемма о не слабо положительной функции и не слабо отрицательной функции. Лемма о небиюнктивной функции и немультиаффинной функции. Условная выразимость дизъюнкции трех литералов.
 
[[Media: dfvo-l9-selezn.pdf | Лекция 9]]. Лемма о не слабо положительной функции и не слабо отрицательной функции. Лемма о небиюнктивной функции и немультиаффинной функции. Условная выразимость дизъюнкции трех литералов.
  
[[Media: dfvo-l10-selezn.pdf | Лекция 10]]. Теорема разделимости Шефера. Примеры.
+
[[Media: dfvo-l10-selezn.pdf | Лекция 10]]. Теорема разделимости Шефера. Задача обобщенной выполнимости с бесконечным множеством.
  
 
Коллоквиум 2.
 
Коллоквиум 2.
 +
<!--- '''Часть 3. Выполнимость ограничений'''.
  
'''Часть 3. Выполнимость ограничений'''.
+
[[Media: dfvo-l11-selezn.pdf | Лекция 11]]. Предикаты на конечном множестве. Формулы, S-формулы и замкнутые классы предикатов. Задача обобщенной выполнимости S-ВЫП. Вычислительная сложность некоторых задач S-ВЫП.
  
[[Media: dfvo-l11-selezn.pdf | Лекция 11]]. Предикаты над конечным множеством. Формулы, S-формулы и замкнутые классы предикатов. Задача обобщенной выполнимости S-ВЫП. Вычислительная сложность некоторых задач S-ВЫП.
+
[[Media: dfvo-l12-selezn.pdf | Лекция 12]]. Функции на конечном множестве. Формулы и замкнутые классы функций. Сохранение предиката функцией,  полиморфизмы. Двузначный случай. Вычислительная сложность некоторых задач S-ВЫП. Теорема разделимости.
  
[[Media: dfvo-l12-selezn.pdf | Лекция 12]]. Функции над конечным множеством. Формулы и замкнутые классы функций. Сохранение предиката функцией,  полиморфизмы. Двузначный случай. Вычислительная сложность некоторых задач S-ВЫП. Теорема разделимости.
+
Коллоквиум 3.--->
  
Коллоквиум 3.
+
==Семинары==
 
+
==Упражнения==
+
  
 
[[Media: dfvo-s1-selezn.pdf | Занятие 1]]. Сокращенная КНФ и способы ее построения.
 
[[Media: dfvo-s1-selezn.pdf | Занятие 1]]. Сокращенная КНФ и способы ее построения.
  
[[Media: dfvo-s2-selezn.pdf | Занятие 2]]. Полином Жегалкина. ЛКНФ и представимость ЛКНФ.
+
[[Media: dfvo-s2-selezn.pdf | Занятие 2]]. Полином Жегалкина. ЛКНФ и представимость в виде ЛКНФ.
  
 
[[Media: dfvo-s3-selezn.pdf | Занятие 3]]. Классы P и NP, NP-полнота.
 
[[Media: dfvo-s3-selezn.pdf | Занятие 3]]. Классы P и NP, NP-полнота.
 +
 +
Коллоквиум 1 по теме "Функции алгебры логики и сложностные классы".
  
 
[[Media: dfvo-s4-selezn.pdf | Занятие 4]]. Слабо положительные и слабо отрицательные функции.  
 
[[Media: dfvo-s4-selezn.pdf | Занятие 4]]. Слабо положительные и слабо отрицательные функции.  
Строка 69: Строка 84:
 
[[Media: dfvo-s6-selezn.pdf | Занятие 6]]. Теорема разделимости Шефера.
 
[[Media: dfvo-s6-selezn.pdf | Занятие 6]]. Теорема разделимости Шефера.
  
[[Media: dfvo-s7-selezn.pdf | Занятие 7]]. Доказательство NP-полноты некоторых задач.
+
Коллоквиум 2 по теме "Теорема Шефера".
 +
<!---[[Media: dfvo-s7-selezn.pdf | Занятие 7]]. Доказательство NP-полноты некоторых задач.
 
   
 
   
[[Media: dfvo-s8-selezn.pdf | Занятие 8]]. Доказательство полиномиальности некоторых задач.
+
[[Media: dfvo-s8-selezn.pdf | Занятие 8]]. Доказательство полиномиальности некоторых задач.--->
  
 
==Программа курса==
 
==Программа курса==
  
*Функции алгебры логики. Конъюнктивные и дизъюнктивные нормальные формы (КНФ и ДНФ). Сокращенная КНФ и способы ее построения. Полиномы Жегалкина, быстрый способ построения полинома Жегалкина функции. Линейные конъюнктивные нормальные формы (ЛКНФ). Проверка представимости функции ЛКНФ.  
+
*Функции алгебры логики. Конъюнктивные и дизъюнктивные нормальные формы (КНФ и ДНФ). Сокращенная КНФ и способы ее построения. Полиномы Жегалкина, быстрый способ построения полинома Жегалкина функции. Линейные конъюнктивные нормальные формы (ЛКНФ). Проверка представимости функции в виде ЛКНФ.  
  
*Задачи распознавания свойств. Классы P и NP. Полиномиальные, NP-трудные и NP-полные задачи. NP-полнота задач распознавания выполнимости КНФ (ВЫП) и 3-КНФ (3-ВЫП), полиномиальность задачи распознавания выполнимости 2-КНФ (2-ВЫП). Постановка задачи обобщенной выполнимости S-ВЫП.  
+
*Задачи распознавания свойств. Классы P и NP. Полиномиальные, NP-трудные и NP-полные задачи. NP-полнота задачи k-раскраски графов при k >= 3. Задача обобщенной выполнимости S-ВЫП.  
  
 
*Слабо положительные, слабо отрицательные и биюнктивные КНФ и слабо положительные, слабо отрицательные и биюнктивные функции алгебры логики. Критерии слабой положительности, слабой отрицательности и биюнктивности функции. Полиномиальность распознавания выполнимости слабо положительной, слабо отрицательной и биюнктивной КНФ.  
 
*Слабо положительные, слабо отрицательные и биюнктивные КНФ и слабо положительные, слабо отрицательные и биюнктивные функции алгебры логики. Критерии слабой положительности, слабой отрицательности и биюнктивности функции. Полиномиальность распознавания выполнимости слабо положительной, слабо отрицательной и биюнктивной КНФ.  
Строка 83: Строка 99:
 
*Линейные и мультиаффинные функции алгебры логики. Приведенное представление мультиаффинной функции алгебры логики. Критерий мультиаффинности функции. Полиномиальность распознавания выполнимости конъюнкции приведенных представлений мультиаффинных функций.  
 
*Линейные и мультиаффинные функции алгебры логики. Приведенное представление мультиаффинной функции алгебры логики. Критерий мультиаффинности функции. Полиномиальность распознавания выполнимости конъюнкции приведенных представлений мультиаффинных функций.  
  
*Условная выразимость функций алгебры логики, леммы об условной выразимости функций (о транзитивности, о замене множителя в конъюнктивной форме, о подстановке констант вместо переменных и о навешивании отрицаний над переменными). Лемма о функции, сохраняющей константу 0, и функции, не сохраняющей константу 1. Лемма о функции, не являющейся самодополнительной. Лемма о функции, не являющейся слабо положительной, и функции, не являющейся слабо отрицательной. Леммы о небиюнктивной функции и немультиаффинной функции. Теорема разделимости Шефера о сложности задачи обобщенной выполнимости S-ВЫП.
+
*Условная выразимость функций алгебры логики, леммы об условной выразимости функций (о транзитивности, о замене множителя в конъюнктивной форме, о подстановке констант вместо переменных и о навешивании отрицаний над переменными). Лемма о функции, сохраняющей константу 0, и функции, не сохраняющей константу 1. Лемма о функции, не являющейся самодополнительной. Лемма о функции, не являющейся слабо положительной, и функции, не являющейся слабо отрицательной. Леммы о небиюнктивной функции и немультиаффинной функции. Теорема Шефера о разделимости вычислительной сложности задачи S-ВЫП.
 +
 
 +
*Предикаты на конечном множестве. Формулы, S-формулы и замкнутые классы предикатов. Задача выполнимости ограничений S-ВЫП. Функции на конечном множестве. Формулы и замкнутые классы функций. Сохранение предиката функцией, полиморфизмы. Двузначный случай. Вычислительная сложность некоторых задач S-ВЫП. Теорема о разделимости вычислительной сложности задачи S-ВЫП.
  
 
==Экзамен==
 
==Экзамен==

Версия 16:19, 29 ноября 2022


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

Лекция 1. Вступление. Алгебра логики. Функции алгебры логики. Формулы. Полнота. Замкнутые классы. Классы T_0, T_1, L, S, M. Теорема Поста.

Лекция 2. Конъюнктивные нормальные формы. Имплицента, простая имплицента функции. Сокращенная КНФ функции. Способы построения сокращенной КНФ.

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

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

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

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

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

Лекция 6. Биюнктивные КНФ и функции. Критерий биюнктивности функции. Полиномиальность проверки выполнимости биюнктивной КНФ. Полиномиальность поиска решения выполнимой биюнктивной КНФ.

Лекция 7. ЛКНФ и мультиаффинные функции. Критерий мультиаффинности функции. Полиномиальность проверки выполнимости ЛКНФ. Полиномиальность проверки по полиному Жегалкина представимости функции в виде ЛКНФ. Функции, сохраняющие константу.

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

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

Лекция 10. Теорема разделимости Шефера. Задача обобщенной выполнимости с бесконечным множеством.

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

Семинары

Занятие 1. Сокращенная КНФ и способы ее построения.

Занятие 2. Полином Жегалкина. ЛКНФ и представимость в виде ЛКНФ.

Занятие 3. Классы P и NP, NP-полнота.

Коллоквиум 1 по теме "Функции алгебры логики и сложностные классы".

Занятие 4. Слабо положительные и слабо отрицательные функции.

Занятие 5. Биюнктивные и мультиаффинные функции.

Занятие 6. Теорема разделимости Шефера.

Коллоквиум 2 по теме "Теорема Шефера".

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

  • Функции алгебры логики. Конъюнктивные и дизъюнктивные нормальные формы (КНФ и ДНФ). Сокращенная КНФ и способы ее построения. Полиномы Жегалкина, быстрый способ построения полинома Жегалкина функции. Линейные конъюнктивные нормальные формы (ЛКНФ). Проверка представимости функции в виде ЛКНФ.
  • Задачи распознавания свойств. Классы P и NP. Полиномиальные, NP-трудные и NP-полные задачи. NP-полнота задачи k-раскраски графов при k >= 3. Задача обобщенной выполнимости S-ВЫП.
  • Слабо положительные, слабо отрицательные и биюнктивные КНФ и слабо положительные, слабо отрицательные и биюнктивные функции алгебры логики. Критерии слабой положительности, слабой отрицательности и биюнктивности функции. Полиномиальность распознавания выполнимости слабо положительной, слабо отрицательной и биюнктивной КНФ.
  • Линейные и мультиаффинные функции алгебры логики. Приведенное представление мультиаффинной функции алгебры логики. Критерий мультиаффинности функции. Полиномиальность распознавания выполнимости конъюнкции приведенных представлений мультиаффинных функций.
  • Условная выразимость функций алгебры логики, леммы об условной выразимости функций (о транзитивности, о замене множителя в конъюнктивной форме, о подстановке констант вместо переменных и о навешивании отрицаний над переменными). Лемма о функции, сохраняющей константу 0, и функции, не сохраняющей константу 1. Лемма о функции, не являющейся самодополнительной. Лемма о функции, не являющейся слабо положительной, и функции, не являющейся слабо отрицательной. Леммы о небиюнктивной функции и немультиаффинной функции. Теорема Шефера о разделимости вычислительной сложности задачи S-ВЫП.
  • Предикаты на конечном множестве. Формулы, S-формулы и замкнутые классы предикатов. Задача выполнимости ограничений S-ВЫП. Функции на конечном множестве. Формулы и замкнутые классы функций. Сохранение предиката функцией, полиморфизмы. Двузначный случай. Вычислительная сложность некоторых задач S-ВЫП. Теорема о разделимости вычислительной сложности задачи S-ВЫП.

Экзамен