Дискретные функции и выполнимость ограничений — различия между версиями
Материал из Кафедра математической кибернетики
(→Экзамен) |
|||
| Строка 4: | Строка 4: | ||
Лектор — доцент [[Селезнева Светлана Николаевна]] | Лектор — доцент [[Селезнева Светлана Николаевна]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
==Программа курса== | ==Программа курса== | ||
| − | + | #Единичный n-мерный куб. Функции алгебры логики. Полином Жегалкина. Некоторые свойства полиномов Жегалкина функций алгебры логики. | |
| − | + | #Поляризованные полиномиальные формы (ППФ). Длина функции в классе ППФ. Теорема Перязева о длине функций алгебры логики в классе ППФ. Теорема о длине почти всех функций в классе ППФ. Сложность системы функций в классе ППФ. Теорема о сложности систем функций алгебры логики, содержащих хотя бы две функции, в классе ППФ. | |
| − | + | #Полиномиальные нормальные формы (ПНФ). Длина функции в классе ПНФ. Нижняя мощностная оценка длины функций алгебры логики в классе ПНФ. Теорема Кириченко об оценке длины функций алгебры логики в классе ПНФ через затеняющее множество куба. Покрытия матриц. Градиентное покрытие матрицы. Лемма о градиентном покрытии. Оценка затеняющего множества куба. Верхняя оценка длины функций алгебры логики в классе ПНФ. | |
| − | + | #Приближения функций алгебры логики полиномами. Леммы о свойствах биномиальных коэффициентов и их сумм. Теорема о ранге полиномов, приближающих функции алгебры логики с точностью d, 0 < d < 1, и с точностью до одной точки. Лемма о приближении функции алгебры логики на множестве. Теорема о длине полиномов, приближающих функции алгебры логики с точностью d, 0 < d < 1, и с точностью до одной точки.. | |
| − | + | #Задачи распознавания свойств. Классов P и NP. Полиномиальные, NP-трудные и NP-полные задачи. NP-полнота задач распознавания выполнимости КНФ (ВЫП) и 3-КНФ (3-ВЫП), полиномиальность задачи распознавания выполнимости 2-КНФ (2-ВЫП). Постановка задачи обобщенной выполнимости S-ВЫП. | |
| − | + | #Имплицента, простая имплицента функции алгебры логики. Леммы об имплицентах функции алгебры логики. Сокращенная КНФ функции и способы ее построения. | |
| − | + | #Слабо положительные, слабо отрицательные и биюнктивные КНФ и слабо положительные, слабо отрицательные и биюнктивные функции алгебры логики. Критерии слабой положительности, слабой отрицательности и биюнктивности функции. Теоремы о полиномиальности распознавания выполнимости слабо положительной, слабо отрицательной и биюнктивной КНФ. | |
| − | + | #Линейные и мультиаффинные функции алгебры логики. Приведенное представление мультиаффинной функции алгебры логики. Критерий мультиаффинности функции. Теорема о полиномиальности распознавания выполнимости конъюнкции приведенных представлений мультиаффинных функций. | |
| − | + | #Условная выразимость функций алгебры логики, леммы об условной выразимости функций (о транзитивности, о замене множителя в конъюнктивной форме, о подстановке констант и о навешивании отрицаний над переменными). Лемма о функции, сохраняющей константу 0, и о функции, не сохраняющей константу 1. Лемма о функции, не являющейся четной. Лемма о не слабо положительной функции и не слабо отрицательной функции. Леммы о небиюнктивной функции и немультиаффинной функции. Теорема разделимости Шефера о сложности задачи S-ВЫП. | |
| − | + | #NP-полнота задач распознавания слабой положительности, слабой отрицательности, биюнктивности и мультиаффинности функции алгебры логики, заданной в виде ДНФ. Нижняя единица функции. Лемма о нахождении всех нижних единиц функции алгебры логики по ее полиному Жегалкина. Полиномиальность задачи распознавания монотонности функции алгебры логики, заданной в виде полинома Жегалкина. Лемма о числе сомножителей в приведенном представлении мультиаффинной функции. Полиномиальность распознавания мультиаффинности функции алгебры логики, заданной в виде полинома Жегалкина. | |
==Программа семинарских занятий== | ==Программа семинарских занятий== | ||
| Строка 62: | Строка 54: | ||
4. Доказать полиномиальность проверки несуществования двух противоположных выполняющих наборов монотонной ДНФ. | 4. Доказать полиномиальность проверки несуществования двух противоположных выполняющих наборов монотонной ДНФ. | ||
| + | |||
| + | ==Экзамен== | ||
| + | |||
| + | Досрочный экзамен состоится в пятницу, 18 декабря 2015 г. Начало в 14 ч. | ||
| + | |||
| + | В билете 2 вопроса и задача. Один вопрос в билете может содержать несколько вопросов из списка вопросов к экзамену. Подготовка к ответу на билет - 1 ч. | ||
| + | |||
| + | [[Media:dfp-2015.docx|Вопросы к экзамену, зимняя сессия 2015-2016 уч.г.]] | ||
Версия 20:00, 24 декабря 2016
Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"
Лекции - 2 ч в неделю, семинары - 1 ч в неделю
Лектор — доцент Селезнева Светлана Николаевна
Программа курса
- Единичный n-мерный куб. Функции алгебры логики. Полином Жегалкина. Некоторые свойства полиномов Жегалкина функций алгебры логики.
- Поляризованные полиномиальные формы (ППФ). Длина функции в классе ППФ. Теорема Перязева о длине функций алгебры логики в классе ППФ. Теорема о длине почти всех функций в классе ППФ. Сложность системы функций в классе ППФ. Теорема о сложности систем функций алгебры логики, содержащих хотя бы две функции, в классе ППФ.
- Полиномиальные нормальные формы (ПНФ). Длина функции в классе ПНФ. Нижняя мощностная оценка длины функций алгебры логики в классе ПНФ. Теорема Кириченко об оценке длины функций алгебры логики в классе ПНФ через затеняющее множество куба. Покрытия матриц. Градиентное покрытие матрицы. Лемма о градиентном покрытии. Оценка затеняющего множества куба. Верхняя оценка длины функций алгебры логики в классе ПНФ.
- Приближения функций алгебры логики полиномами. Леммы о свойствах биномиальных коэффициентов и их сумм. Теорема о ранге полиномов, приближающих функции алгебры логики с точностью d, 0 < d < 1, и с точностью до одной точки. Лемма о приближении функции алгебры логики на множестве. Теорема о длине полиномов, приближающих функции алгебры логики с точностью d, 0 < d < 1, и с точностью до одной точки..
- Задачи распознавания свойств. Классов P и NP. Полиномиальные, NP-трудные и NP-полные задачи. NP-полнота задач распознавания выполнимости КНФ (ВЫП) и 3-КНФ (3-ВЫП), полиномиальность задачи распознавания выполнимости 2-КНФ (2-ВЫП). Постановка задачи обобщенной выполнимости S-ВЫП.
- Имплицента, простая имплицента функции алгебры логики. Леммы об имплицентах функции алгебры логики. Сокращенная КНФ функции и способы ее построения.
- Слабо положительные, слабо отрицательные и биюнктивные КНФ и слабо положительные, слабо отрицательные и биюнктивные функции алгебры логики. Критерии слабой положительности, слабой отрицательности и биюнктивности функции. Теоремы о полиномиальности распознавания выполнимости слабо положительной, слабо отрицательной и биюнктивной КНФ.
- Линейные и мультиаффинные функции алгебры логики. Приведенное представление мультиаффинной функции алгебры логики. Критерий мультиаффинности функции. Теорема о полиномиальности распознавания выполнимости конъюнкции приведенных представлений мультиаффинных функций.
- Условная выразимость функций алгебры логики, леммы об условной выразимости функций (о транзитивности, о замене множителя в конъюнктивной форме, о подстановке констант и о навешивании отрицаний над переменными). Лемма о функции, сохраняющей константу 0, и о функции, не сохраняющей константу 1. Лемма о функции, не являющейся четной. Лемма о не слабо положительной функции и не слабо отрицательной функции. Леммы о небиюнктивной функции и немультиаффинной функции. Теорема разделимости Шефера о сложности задачи S-ВЫП.
- NP-полнота задач распознавания слабой положительности, слабой отрицательности, биюнктивности и мультиаффинности функции алгебры логики, заданной в виде ДНФ. Нижняя единица функции. Лемма о нахождении всех нижних единиц функции алгебры логики по ее полиному Жегалкина. Полиномиальность задачи распознавания монотонности функции алгебры логики, заданной в виде полинома Жегалкина. Лемма о числе сомножителей в приведенном представлении мультиаффинной функции. Полиномиальность распознавания мультиаффинности функции алгебры логики, заданной в виде полинома Жегалкина.
Программа семинарских занятий
Семинар 1. ППФ.
Семинар 2. 1. Найти точную оценку длины функций алгебры логики, зависящих от 2-х переменных, в классе ПНФ.
2. Найти точную оценку длины функций алгебры логики, зависящих от 3-х переменных, в классе ПНФ.
Семинар 3. 1. Найти градиентное покрытие заданных матриц.
Семинар 4. 1. Найти точную оценку ранга полиномов, приближающих функции алгебры логики, с точностью до одной точки.
2. Найти точную оценку ранга полиномов, приближающих функции алгебры логики, с точностью до двух точек.
3. Найти асимптотику длины полиномов, приближающих функции алгебры логики, с точностью до одной точки.
Семинар 5. 1. Доказать полиномиальность задач распознавания линейности функции алгебры логики, заданной совершенной ДНФ и сокращенной ДНФ.
2. Доказать полиномиальность задач распознавания монотонности функции алгебры логики, заданной совершенной ДНФ и сокращенной ДНФ.
3. Доказать полиномиальность задачи распознавания самодвойственности функции алгебры логики, заданной совершенной ДНФ.
4. Доказать полиномиальность проверки несуществования двух противоположных выполняющих наборов монотонной ДНФ.
Экзамен
Досрочный экзамен состоится в пятницу, 18 декабря 2015 г. Начало в 14 ч.
В билете 2 вопроса и задача. Один вопрос в билете может содержать несколько вопросов из списка вопросов к экзамену. Подготовка к ответу на билет - 1 ч.
