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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Экзамен)
 
(не показаны 117 промежуточные версии 2 участников)
Строка 1: Строка 1:
Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"
+
[[Категория:Лекционные курсы кафедры МК]]
 +
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]
 +
[[Категория:Спецкурсы кафедры МК]]
 +
Обязательный курс для студентов 518/1 группы магистерской программы "Дискретные структуры и алгоритмы".
  
Лекции - 2 ч в неделю, семинары - 1 ч в неделю
+
Спецкурс для студентов магистратуры.
  
Лектор — доцент [[Селезнева Светлана Николаевна]]
+
Лектор - [[Селезнева Светлана Николаевна]]
  
==Экзамен==
+
Лекции - 2 ч в неделю.
  
Досрочный экзамен состоится в пятницу, 18 декабря 2015 г. Начало в 14 ч.
+
Семинары - 1 ч в неделю (для студентов 518/1 группы).
  
В билете 2 вопроса и задача. Один вопрос в билете может содержать несколько вопросов из списка вопросов к экзамену. Подготовка к ответу на билет - 1 ч.
+
'''Аннотация'''. Курс посвящен рассмотрению подходов к изучению теоретической вычислительной сложности задач обобщенной выполнимости. Задача обобщенной выполнимости состоит в выяснении выполнимости системы отношений, принадлежащих заранее известному множеству S и связывающих произвольные переменные. При этом полагается, что в множество S входят отношения на конечном множестве, содержащем k элементов. Известная задача выполнимости КНФ является частным случаем этой задачи. В курсе подробно разбирается случай k=2, описываются все виды множеств S, при которых задача обобщенной выполнимости может быть решена полиномиальными алгоритмами, и показывается ее труднорешаемость во всех других случаях. Разбирается общий подход к изучению вычислительной сложности этой задачи при произвольных k.  
  
[[Media:dfp-2015.docx|Вопросы к экзамену, зимняя сессия 2015-2016 уч.г.]]
+
==Объявления==
  
==Программа курса==
+
<!---'''Основной экзамен состоится 12 января. Начало в 10 ч'''.
  
'''Лекция 1'''. Единичный n-мерный куб. Функции алгебры логики. Полином Жегалкина. Некоторые свойства полиномов Жегалкина функций алгебры логики.  
+
'''Консультация''' к экзамену состоится '''11 января''' с помощью zoom; ссылка такая же, как и для лекций. Начало '''в 11 ч'''.
  
'''Лекция 2'''. Поляризованные полиномиальные формы (ППФ). Длина функции в классе ППФ. Теорема Перязева о длине функций алгебры логики в классе ППФ. Теорема о длине почти всех функций в классе ППФ. Сложность системы функций в классе ППФ. Теорема о сложности систем функций алгебры логики, содержащих хотя бы две функции, в классе ППФ.
+
'''Просьба ко всем, кто собирается сдавать курс в качестве спецкурса или элективного курса, прислать сообщение об этом лектору [[Селезнева Светлана Николаевна | Селезневой Светлане Николаевне]] по эл. почте'''.  
  
'''Лекция 3'''. Полиномиальные нормальные формы (ПНФ). Длина функции в классе ПНФ. Нижняя мощностная оценка длины функций алгебры логики в классе ПНФ. Теорема Кириченко об оценке длины функций алгебры логики в классе ПНФ через затеняющее множество куба.
+
Для сдающих спецкурс экзамен будет проходить в виде письменной работы (10 заданий разной сложности, включающие задачи и вопросы по теории). Продолжительность написания работы - 1 ч 45 мин (105 мин).  
  
'''Лекция 4'''. Покрытия матриц. Градиентное покрытие матрицы. Лемма о градиентном покрытии. Оценка затеняющего множества куба. Верхняя оценка длины функций алгебры логики в классе ПНФ.
+
Работу нужно написать контрастной ручкой на светлых листах. Затем выполненную работу нужно отсканировать или сфотографировать и сканы/фото загрузить по присланной ссылке. Файлы нужно назвать по фамилии сдающего; форматы файлов pdf, jpg, png.
  
'''Лекция 5'''. Приближения функций алгебры логики полиномами. Леммы о свойствах биномиальных коэффициентов и их сумм. Теорема о ранге полиномов, приближающих функции алгебры логики с заданной точностью.
+
На сканирование/фотографирование работы отводится 15 мин. Т.е. работу нужно сдать через 2 ч (120 мин) после получения задания.
  
'''Лекция 6'''. Приближения функций алгебры логики полиномами. Лемма о приближении функции алгебры логики на множестве. Теорема о длине полиномов, приближающих функции алгебры логики с заданной точностью.
+
Вопросы по содержанию курса и проведению экзамена можно задавать лектору [[Селезнева Светлана Николаевна | Селезневой Светлане Николаевне]] по эл. почте.--->
  
'''Лекция 7'''. Задачи распознавания свойств. Задачи из классов P и NP. Полиномиальные,  NP-трудные и NP-полные задачи. Линейные функции алгебры логики. Обоснование нелинейности функции. NP-полнота задачи распознавания нелинейности функции алгебры логики, заданной в виде ДНФ. Монотонные функции алгебры логики. Обоснование немонотонности функции. NP-полнота задачи распознавания немонотонности функции алгебры логики, заданной в виде ДНФ.
+
==Лекции==
  
'''Лекция 8'''. Нижняя единица и верхний ноль функции. Лемма о нахождении всех нижних единиц функции алгебры логики по ее полиному Жегалкина. Полиномиальность задачи распознавания монотонности функции алгебры логики, заданной в виде полинома Жегалкина.
+
'''Часть 1. Повторение'''.
  
'''Лекция 9'''. NP-полнота задачи распознавания несамодвойственности функции алгебры логики, заданной в виде ДНФ. Четные функции. Лемма о соотношении между самодвойственными и четными функциями алгебры логики. Леммы о свойствах полиномов Жегалкина четных функций алгебры логики. Полиномиальность задачи распознавания самодвойственности функции алгебры логики, заданной в виде полинома Жегалкина.
+
Лекция 1. Вступление. Алгебра логики. Функции алгебры логики. Формулы. Полнота. Замкнутые классы. Классы T_0, T_1, L, S, M. Теорема Поста.
  
'''Лекция 10'''. NP-полнота задачи выполнимости системы функций алгебры логики, заданных в виде полиномов Жегалкина. Вес функции алгебры логики. NP-трудность задачи распознавания равенства веса n-местной функции алгебры логики, заданной в виде полинома Жегалкина, числу 2^{n-1}. Выражение коэффициентов полинома Жегалкина функции алгебры логики через ее значения. Критерий четности веса функции алгебры логики. Полиномиальность задачи распознавания кратности веса функции алгебры логики, заданной в виде полинома Жегалкина, числу 2^m, где m -- заранее известное натуральное число.
+
Лекция 2. Конъюнктивные нормальные формы. Имплицента, простая имплицента функции. Сокращенная КНФ функции. Способы построения сокращенной КНФ.
  
==Программа семинарских занятий==
+
Лекция 3. Полином Жегалкина. Способы построения полинома Жегалкина функции. Линейная имплицента функции. Линейная конъюнктивная нормальная форма (ЛКНФ). Линейная соимплицента функции. Поиск всех линейных соимплицент функции.
  
'''Семинар 1'''. ППФ.
+
Лекция 4. Задачи распознавания. Вычислительная сложность задачи. Классы P и NP, NP-полные задачи. NP-полнота задачи 3-раскраски графов. Задачи обобщенной выполнимости.
  
'''Семинар 2'''.
+
Коллоквиум 1.
1. Найти точную оценку длины функций алгебры логики, зависящих от 2-х переменных, в классе ПНФ.  
+
  
2. Найти точную оценку длины функций алгебры логики, зависящих от 3-х переменных, в классе ПНФ.
+
'''Часть 2. Обобщенная выполнимость'''.
  
'''Семинар 3'''.  
+
Лекция 5. Слабо положительные и слабо отрицательные КНФ и функции. Критерии слабой положительности и слабой отрицательности функции. Полиномиальные алгоритмы проверки выполнимости слабо положительной и слабо отрицательной КНФ.
1. Найти градиентное покрытие заданных матриц.
+
  
'''Семинар 4'''.  
+
Лекция 6. Биюнктивные КНФ и функции. Критерий биюнктивности функции. Полиномиальные алгоритмы проверки выполнимости биюнктивной КНФ. Полиномиальный алгоритм поиска решения выполнимой биюнктивной КНФ.
1. Найти точную оценку ранга полиномов, приближающих функции алгебры логики, с точностью до одной точки.  
+
  
2. Найти точную оценку ранга полиномов, приближающих функции алгебры логики, с точностью до двух точек.  
+
Лекция 7. ЛКНФ и мультиаффинные функции. Критерий мультиаффинности функции. Полиномиальный алгоритм проверки выполнимости ЛКНФ. Полиномиальный алгоритм проверки по полиному Жегалкина представимости функции в виде ЛКНФ. Функции, сохраняющие константу.
  
3. Найти асимптотику длины полиномов, приближающих функции алгебры логики, с точностью до одной точки.  
+
Лекция 8. Условная выразимость функций. Леммы об условной выразимости. Лемма о функции, не сохраняющий единицу, и о функции, сохраняющей ноль. Лемма о несамодополнительной функции. Лемма о самодополнительной функции.
  
'''Семинар 5'''.  
+
Лекция 9. Лемма о не слабо положительной функции и не слабо отрицательной функции. Лемма о небиюнктивной функции и немультиаффинной функции. Условная выразимость дизъюнкции трех литералов.
1. Доказать полиномиальность задач распознавания линейности функции алгебры логики, заданной совершенной ДНФ и сокращенной ДНФ.  
+
  
2. Доказать полиномиальность задач распознавания монотонности функции алгебры логики, заданной совершенной ДНФ и сокращенной ДНФ.  
+
Лекция 10. Теорема Шефера о разделимости вычислительной сложности задач обобщенной выполнимости. Задачи обобщенной выполнимости с бесконечным множеством.
  
3. Доказать полиномиальность задачи распознавания самодвойственности функции алгебры логики, заданной совершенной ДНФ.  
+
Коллоквиум 2.
  
4. Доказать полиномиальность проверки несуществования двух противоположных выполняющих наборов монотонной ДНФ.  
+
'''Часть 3. Общий подход'''.
  
 
+
Лекция 11. Отношения на конечном множестве. Формулы, S-формулы и замкнутые классы отношений. Задачи обобщенной выполнимости S-ВЫП. Вычислительная сложность некоторых задач S-ВЫП.
  
[[Категория:Лекционные курсы кафедры МК]]
+
Лекция 12. Функции на конечном множестве. Формулы и замкнутые классы функций. Сохранение отношения функцией,  полиморфизмы. Двузначный случай.
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]
+
 
 +
Коллоквиум 3.
 +
 
 +
==Семинары==
 +
 
 +
Занятие 1. Сокращенная КНФ и способы ее построения.
 +
 
 +
Занятие 2. Полином Жегалкина. ЛКНФ и представимость в виде ЛКНФ.
 +
 
 +
Занятие 3. Классы P и NP, NP-полнота.
 +
 
 +
Коллоквиум 1 по теме "Функции алгебры логики и сложностные классы".
 +
 
 +
Занятие 4. Слабо положительные и слабо отрицательные функции.
 +
 
 +
Занятие 5. Биюнктивные и мультиаффинные функции.
 +
 
 +
Занятие 6. Теорема разделимости Шефера.
 +
 
 +
Коллоквиум 2 по теме "Теорема Шефера".
 +
<!---Занятие 7. Доказательство NP-полноты некоторых задач.
 +
 +
Занятие 8. Доказательство полиномиальности некоторых задач.--->
 +
 
 +
==Программа курса==
 +
 
 +
*Функции алгебры логики. Конъюнктивные и дизъюнктивные нормальные формы (КНФ и ДНФ). Сокращенная КНФ и способы ее построения. Полиномы Жегалкина, быстрый способ построения полинома Жегалкина функции. Линейные конъюнктивные нормальные формы (ЛКНФ). Проверка представимости функции в виде ЛКНФ.
 +
 
 +
*Задачи распознавания свойств. Классы P и NP. Полиномиальные, NP-трудные и NP-полные задачи. NP-полнота задачи k-раскраски графов при k >= 3. Задача обобщенной выполнимости S-ВЫП.
 +
 
 +
*Слабо положительные, слабо отрицательные и биюнктивные КНФ и слабо положительные, слабо отрицательные и биюнктивные функции алгебры логики. Критерии слабой положительности, слабой отрицательности и биюнктивности функции. Полиномиальность распознавания выполнимости слабо положительной, слабо отрицательной и биюнктивной КНФ.
 +
 
 +
*Линейные и мультиаффинные функции алгебры логики. Приведенное представление мультиаффинной функции алгебры логики. Критерий мультиаффинности функции. Полиномиальность распознавания выполнимости конъюнкции приведенных представлений мультиаффинных функций.
 +
 
 +
*Условная выразимость функций алгебры логики, леммы об условной выразимости функций (о транзитивности, о замене множителя в конъюнктивной форме, о подстановке констант вместо переменных и о навешивании отрицаний над переменными). Лемма о функции, сохраняющей константу 0, и функции, не сохраняющей константу 1. Лемма о функции, не являющейся самодополнительной. Лемма о функции, не являющейся слабо положительной, и функции, не являющейся слабо отрицательной. Леммы о небиюнктивной функции и немультиаффинной функции. Теорема Шефера о разделимости вычислительной сложности задачи S-ВЫП.
 +
 
 +
*Отношения на конечном множестве. Формулы, S-формулы и замкнутые классы отношений. Задача обобщенной выполнимости S-ВЫП. Функции на конечном множестве. Формулы и замкнутые классы функций. Сохранение отношения функцией, полиморфизмы. Двузначный случай.
 +
 
 +
==Экзамен==

Текущая версия на 18:25, 10 октября 2023

Обязательный курс для студентов 518/1 группы магистерской программы "Дискретные структуры и алгоритмы".

Спецкурс для студентов магистратуры.

Лектор - Селезнева Светлана Николаевна

Лекции - 2 ч в неделю.

Семинары - 1 ч в неделю (для студентов 518/1 группы).

Аннотация. Курс посвящен рассмотрению подходов к изучению теоретической вычислительной сложности задач обобщенной выполнимости. Задача обобщенной выполнимости состоит в выяснении выполнимости системы отношений, принадлежащих заранее известному множеству S и связывающих произвольные переменные. При этом полагается, что в множество S входят отношения на конечном множестве, содержащем k элементов. Известная задача выполнимости КНФ является частным случаем этой задачи. В курсе подробно разбирается случай k=2, описываются все виды множеств 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.

Часть 3. Общий подход.

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

Лекция 12. Функции на конечном множестве. Формулы и замкнутые классы функций. Сохранение отношения функцией, полиморфизмы. Двузначный случай.

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

Семинары

Занятие 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-ВЫП. Функции на конечном множестве. Формулы и замкнутые классы функций. Сохранение отношения функцией, полиморфизмы. Двузначный случай.

Экзамен