Обобщенная выполнимость — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Объявления)
 
(не показаны 99 промежуточные версии 2 участников)
Строка 1: Строка 1:
 +
[[Категория:Лекционные курсы кафедры МК]]
 +
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]
 +
[[Категория:Спецкурсы кафедры МК]]
 
Обязательный курс для студентов 518/1 группы магистерской программы "Дискретные структуры и алгоритмы".
 
Обязательный курс для студентов 518/1 группы магистерской программы "Дискретные структуры и алгоритмы".
  
 
Спецкурс для студентов магистратуры.
 
Спецкурс для студентов магистратуры.
 +
 +
Лектор - [[Селезнева Светлана Николаевна]]
  
 
Лекции - 2 ч в неделю.
 
Лекции - 2 ч в неделю.
Строка 7: Строка 12:
 
Семинары - 1 ч в неделю (для студентов 518/1 группы).
 
Семинары - 1 ч в неделю (для студентов 518/1 группы).
  
−
'''Аннотация'''. Цель курса - показать, каким образом теория дискретных функций применяется при решении задачи обобщенной выполнимости. Задача обобщенной выполнимости, или выполнимости ограничений (англ. constraint satisfaction problem, CSP) состоит в выяснении выполнимости системы отношений, взятых из заранее известного множества S и связывающих произвольные переменные. При этом полагается, что в S входят отношения над конечным множеством A, |A| = k. В курсе показывается, что вычислительная сложность задачи S-выполнимости зависит только от функций, сохраняющих все отношения из S. Первая часть курса посвящена булевой выполнимости (k = 2). В ней рассматривается теорема Шефера о дихотомии вычислительной сложности задачи булевой выполнимости. Во второй части курса рассматривается задача S-выполнимости для произвольных конечных k > 2. Доказываются случаи NP-полноты этой задачи, а также рассматриваются ее полиномиальные случаи. Приводится теорема о дихотомии вычислительной сложности задачи S-выполнимости для произвольных конечных k.
+
'''Аннотация'''. Курс посвящен рассмотрению подходов к изучению теоретической вычислительной сложности задач обобщенной выполнимости. Задача обобщенной выполнимости состоит в выяснении выполнимости системы отношений, принадлежащих заранее известному множеству S и связывающих произвольные переменные. При этом полагается, что в множество S входят отношения на конечном множестве, содержащем k элементов. Известная задача выполнимости КНФ является частным случаем этой задачи. В курсе подробно разбирается случай k=2, описываются все виды множеств S, при которых задача обобщенной выполнимости может быть решена полиномиальными алгоритмами, и показывается ее труднорешаемость во всех других случаях. Разбирается общий подход к изучению вычислительной сложности этой задачи при произвольных k.  
−
 
+
−
Лектор - [[Селезнева Светлана Николаевна]]
+
  
 
==Объявления==
 
==Объявления==
 +
 +
Вопросы по курсу можно задавать по эл. почте лектору [[Селезнева Светлана Николаевна | Селезневой Светлане Николаевне]].
  
 
==Лекции==
 
==Лекции==
  
−
Лекция 1. Функции алгебры логики. Формулы и функции, определяемые формулами. Замкнутые классы и полные системы.
+
'''Часть 1. Повторение'''.
  
−
[[Media: dfvo-l2-selezn.pdf | Лекция 2]]. Конъюнктивные и дизъюнктивные нормальные формы (КНФ и ДНФ). Сокращенная КНФ и способы ее построения.
+
Лекция 1. Вступление. Алгебра логики. Функции алгебры логики. Формулы. Полнота. Замкнутые классы. Классы T_0, T_1, L, S, M. Теорема Поста.
  
−
[[Media: dfvo-l3-selezn.pdf | Лекция 3]]. Полиномы Жегалкина. Линейная конъюнктивная нормальная форма (ЛКНФ), представимость ЛКНФ.
+
Лекция 2. Конъюнктивные нормальные формы. Имплицента, простая имплицента функции. Сокращенная КНФ функции. Способы построения сокращенной КНФ.
  
−
==Упражнения==
+
Лекция 3. Полином Жегалкина. Способы построения полинома Жегалкина функции. Линейная имплицента функции. Линейная конъюнктивная нормальная форма (ЛКНФ). Линейная соимплицента функции. Поиск всех линейных соимплицент функции.
  
−
[[Media: dfvo-s1-selezn.pdf | Занятие 1]]. Сокращенная КНФ и способы ее построения.
+
Лекция 4. Задачи распознавания. Вычислительная сложность задачи. Классы P и NP, NP-полные задачи. NP-полнота задачи 3-раскраски графов. Задачи обобщенной выполнимости.
  
−
[[Media: dfvo-s2-selezn.pdf | Занятие 2]]. Полином Жегалкина. ЛКНФ и представимость ЛКНФ.
+
Коллоквиум 1.
  
−
==Программа курса==
+
'''Часть 2. Обобщенная выполнимость'''.
  
−
*Функции алгебры логики. Конъюнктивные и дизъюнктивные нормальные формы (КНФ и ДНФ). Сокращенная КНФ и способы ее построения. Полиномы Жегалкина, быстрый способ построения полинома Жегалкина функции. Линейные конъюнктивные нормальные формы (ЛКНФ). Проверка представимости функции ЛКНФ.  
+
Лекция 5. Слабо положительные и слабо отрицательные КНФ и функции. Критерии слабой положительности и слабой отрицательности функции. Полиномиальные алгоритмы проверки выполнимости слабо положительной и слабо отрицательной КНФ.
  
−
*Задачи распознавания свойств. Классы P и NP. Полиномиальные, NP-трудные и NP-полные задачи. NP-полнота задач распознавания выполнимости КНФ (ВЫП) и 3-КНФ (3-ВЫП), полиномиальность задачи распознавания выполнимости 2-КНФ (2-ВЫП). Постановка задачи обобщенной выполнимости S-ВЫП.  
+
Лекция 6. Биюнктивные КНФ и функции. Критерий биюнктивности функции. Полиномиальные алгоритмы проверки выполнимости биюнктивной КНФ. Полиномиальный алгоритм поиска решения выполнимой биюнктивной КНФ.
  
−
*Слабо положительные, слабо отрицательные и биюнктивные КНФ и слабо положительные, слабо отрицательные и биюнктивные функции алгебры логики. Критерии слабой положительности, слабой отрицательности и биюнктивности функции. Полиномиальность распознавания выполнимости слабо положительной, слабо отрицательной и биюнктивной КНФ.  
+
Лекция 7. ЛКНФ и мультиаффинные функции. Критерий мультиаффинности функции. Полиномиальный алгоритм проверки выполнимости ЛКНФ. Полиномиальный алгоритм проверки по полиному Жегалкина представимости функции в виде ЛКНФ. Функции, сохраняющие константу.
  
−
*Линейные и мультиаффинные функции алгебры логики. Приведенное представление мультиаффинной функции алгебры логики. Критерий мультиаффинности функции. Полиномиальность распознавания выполнимости конъюнкции приведенных представлений мультиаффинных функций.  
+
Лекция 8. Условная выразимость функций. Леммы об условной выразимости. Лемма о функции, не сохраняющий единицу, и о функции, сохраняющей ноль. Лемма о несамодополнительной функции. Лемма о самодополнительной функции.
  
−
*Условная выразимость функций алгебры логики, леммы об условной выразимости функций (о транзитивности, о замене множителя в конъюнктивной форме, о подстановке констант вместо переменных и о навешивании отрицаний над переменными). Лемма о функции, сохраняющей константу 0, и функции, не сохраняющей константу 1. Лемма о функции, не являющейся четной. Лемма о функции, не являющейся слабо положительной, и функции, не являющейся слабо отрицательной. Леммы о небиюнктивной функции и немультиаффинной функции. Теорема разделимости Шефера о сложности задачи обобщенной выполнимости S-ВЫП.  
+
Лекция 9. Лемма о не слабо положительной функции и не слабо отрицательной функции. Лемма о небиюнктивной функции и немультиаффинной функции. Условная выразимость дизъюнкции трех литералов.
  
−
*NP-полнота задач распознавания слабой положительности, слабой отрицательности, биюнктивности и мультиаффинности функции алгебры логики, заданной в виде ДНФ. Нижняя единица функции. Лемма о нахождении всех нижних единиц функции алгебры логики по ее полиному Жегалкина. Полиномиальность задачи распознавания монотонности функции алгебры логики, заданной в виде полинома Жегалкина. Лемма о числе сомножителей в приведенном представлении мультиаффинной функции. Полиномиальность распознавания мультиаффинности функции алгебры логики, заданной в виде полинома Жегалкина.
+
Лекция 10. Теорема Шефера о разделимости вычислительной сложности задач обобщенной выполнимости. Задачи обобщенной выполнимости с бесконечным множеством.
  
−
==Программа семинарских занятий==
+
Коллоквиум 2.
  
−
'''Семинар 1. Повторение'''.  
+
'''Часть 3. Общий подход'''.
  
−
1. Построить сокращенную ДНФ данной функции алгебры логики по ее ДНФ или по ее КНФ.
+
Лекция 11. Отношения на конечном множестве. Формулы, S-формулы и замкнутые классы отношений. Задачи обобщенной выполнимости S-ВЫП. Вычислительная сложность некоторых задач S-ВЫП.
  
−
2. Быстрым способом построить полином Жегалкина данной функции алгебры логики.
+
Лекция 12. Функции на конечном множестве. Формулы и замкнутые классы функций. Сохранение отношения функцией,  полиморфизмы. Двузначный случай.  
  
−
'''Семинар 2. Поляризованные полиномиальные формы (ППФ)'''.  
+
Коллоквиум 3.
  
−
1. Быстрым способом построить ППФ по заданному вектору поляризации для данной функции алгебры логики.
+
==Семинары==
  
−
2. Построить классификацию всех функций алгебры логики, зависящих от 2-х переменных, по длине в классе ППФ.
+
Занятие 1. Сокращенная КНФ и способы ее построения.
  
−
3. Построить классификацию всех функций алгебры логики, зависящих от 3-х переменных, по длине в классе ППФ.
+
Занятие 2. Полином Жегалкина. ЛКНФ и представимость в виде ЛКНФ.
  
−
'''Семинар 3. Полиномиальные нормальные формы (ПНФ)'''.  
+
Занятие 3. Классы P и NP, NP-полнота.
  
−
1. Построить ПНФ для данной функции алгебры логики по затеняющему множеству единичного n-мерного куба.
+
Коллоквиум 1 по теме "Функции алгебры логики и сложностные классы".
  
−
2. Найти точную оценку длины функций алгебры логики, зависящих от 2-х переменных, в классе ПНФ.  
+
Занятие 4. Слабо положительные и слабо отрицательные функции.  
  
−
3. Найти точную оценку длины функций алгебры логики, зависящих от 3-х переменных, в классе ПНФ.
+
Занятие 5. Биюнктивные и мультиаффинные функции.  
  
−
'''Семинар 4. Конъюнктивные нормальные формы'''.  
+
Занятие 6. Теорема разделимости Шефера.
  
−
1. Выяснить, является ли заданная элементарная дизъюнкция имплицентой или простой имплицентой данной функции алгебры логики.
+
Коллоквиум 2 по теме "Теорема Шефера".
  
−
2. Построить сокращенную КНФ заданной функции алгебры логики по ее ДНФ или по ее КНФ.
+
==Программа курса==
  
−
'''Семинар 5. Слабо положительные, слабо отрицательные и биюнктивные функции'''.  
+
*Функции алгебры логики. Конъюнктивные и дизъюнктивные нормальные формы (КНФ и ДНФ). Сокращенная КНФ и способы ее построения. Полиномы Жегалкина, быстрый способ построения полинома Жегалкина функции. Линейные конъюнктивные нормальные формы (ЛКНФ). Проверка представимости функции в виде ЛКНФ.  
  
−
1. Выяснить, является ли заданная функция алгебры логики слабо положительно, слабо отрицательной или биюнктивной по соответствующему критерию.  
+
*Задачи распознавания свойств. Классы P и NP. Полиномиальные, NP-трудные и NP-полные задачи. NP-полнота задачи k-раскраски графов при k >= 3. Задача обобщенной выполнимости S-ВЫП.  
  
−
2. Построить приведенное представление данной слабо положительно, слабо отрицательной или биюнктивной функции.  
+
*Слабо положительные, слабо отрицательные и биюнктивные КНФ и слабо положительные, слабо отрицательные и биюнктивные функции алгебры логики. Критерии слабой положительности, слабой отрицательности и биюнктивности функции. Полиномиальность распознавания выполнимости слабо положительной, слабо отрицательной и биюнктивной КНФ.  
  
−
'''Семинар 6. Мультиаффинные функции'''.  
+
*Линейные и мультиаффинные функции алгебры логики. Приведенное представление мультиаффинной функции алгебры логики. Критерий мультиаффинности функции. Полиномиальность распознавания выполнимости конъюнкции приведенных представлений мультиаффинных функций.  
  
−
1. Выяснить, является ли заданная функция алгебры логики мультиаффинной по соответствующему критерию.  
+
*Условная выразимость функций алгебры логики, леммы об условной выразимости функций (о транзитивности, о замене множителя в конъюнктивной форме, о подстановке констант вместо переменных и о навешивании отрицаний над переменными). Лемма о функции, сохраняющей константу 0, и функции, не сохраняющей константу 1. Лемма о функции, не являющейся самодополнительной. Лемма о функции, не являющейся слабо положительной, и функции, не являющейся слабо отрицательной. Леммы о небиюнктивной функции и немультиаффинной функции. Теорема Шефера о разделимости вычислительной сложности задачи S-ВЫП.
  
−
2. Построить приведенное представление данной мультиаффинной функции.  
+
*Отношения на конечном множестве. Формулы, S-формулы и замкнутые классы отношений. Задача обобщенной выполнимости S-ВЫП. Функции на конечном множестве. Формулы и замкнутые классы функций. Сохранение отношения функцией, полиморфизмы. Двузначный случай.
−
 
+
−
'''Семинар 7. Теорема разделимости Шефера'''.
+
−
 
+
−
1. Выяснить для заданного множества S функций алгебры логики, является задача S-ВЫП полиномиальной или NP-полной.
+
  
 
==Экзамен==
 
==Экзамен==
−
 
−
Экзамен устный. В билете 2 вопроса и задача. Подготовка к ответу на билет - 1 ч.
 
−
 
−
 
−
[[Категория:Лекционные курсы кафедры МК]]
 
−
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]
 

Текущая версия на 15:56, 2 сентября 2025

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

Экзамен

Источник — «https://mk.cs.msu.ru/index.php?title=Обобщенная_выполнимость&oldid=12055»