Вопросы к экзамену (1111922)
Текст из файла
Вопросы к экзамену по курсу
«Дискретные функции и их представления» (2016-2017 уч.г.)
Лектор – доцент, д.ф.-м.н. Селезнева Светлана Николаевна
-
Поляризованные полиномиальные формы (ППФ). Длина функции в классе ППФ. Теорема о длине функций алгебры логики в классе ППФ.
-
Сложность системы функций в классе ППФ. Теорема о сложности систем функций алгебры логики, содержащих хотя бы две функции, в классе ППФ.
-
Полиномиальные нормальные формы (ПНФ). Длина функции в классе ПНФ. Нижняя мощностная оценка длины функций алгебры логики в классе ПНФ.
-
Теорема об оценке длины функций алгебры логики в классе ПНФ через затеняющее множество куба. Градиентная оценка затеняющего множества куба. Верхняя оценка длины функций алгебры логики в классе ПНФ.
-
Приближения функций алгебры логики полиномами. Леммы о свойствах биномиальных коэффициентов и их сумм. Теорема о ранге полиномов, приближающих функции алгебры логики с точностью d, 0 < d < 1.
-
Приближения функций алгебры логики полиномами. Лемма о приближении функции алгебры логики на множестве. Теорема о длине полиномов, приближающих функции алгебры логики с точностью d, 0 < d < 1.
-
Имплицента, простая имплицента функции алгебры логики. Леммы об имплицентах функции алгебры логики. Сокращенная КНФ функции и способы ее построения.
-
Слабо положительные КНФ и слабо положительные функции алгебры логики. Критерии слабой положительности. Полиномиальность распознавания выполнимости слабо положительной КНФ.
-
Слабо отрицательные КНФ и слабо отрицательные функции алгебры логики. Критерии слабой отрицательности. Полиномиальность распознавания выполнимости слабо отрицательной КНФ.
-
Биюнктивные КНФ и биюнктивные функции алгебры логики. Критерии биюнктивности функции. Полиномиальность распознавания выполнимости биюнктивной КНФ.
-
Линейные и мультиаффинные функции алгебры логики. Приведенное представление мультиаффинной функции алгебры логики. Критерий мультиаффинности функции. Полиномиальность распознавания выполнимости конъюнкции приведенных представлений мультиаффинных функций.
-
Условная выразимость функций алгебры логики. Леммы об условной выразимости функций (о транзитивности, о замене множителя в конъюнктивной форме, о подстановке констант вместо переменных и о навешивании отрицаний над переменными).
-
Лемма о функции, сохраняющей константу 0, и функции, не сохраняющей константу 1. Лемма о функции, не являющейся четной.
-
Лемма о функции, не являющейся четной. Лемма о функции, не являющейся слабо положительной, и о функции, не являющейся слабо отрицательной.
-
Леммы о небиюнктивной функции и немультиаффинной функции.
-
Теорема разделимости Шефера о сложности задачи обобщенной выполнимости S-ВЫП.
-
NP-полнота задач распознавания слабой положительности, слабой отрицательности, биюнктивности и мультиаффинности функции алгебры логики, заданной в виде ДНФ.
-
Нижняя единица функции алгебры логики. Лемма о нахождении всех нижних единиц функции алгебры логики по ее полиному Жегалкина. Полиномиальность задачи распознавания монотонности функции алгебры логики, заданной в виде полинома Жегалкина.
-
Лемма о числе сомножителей в приведенном представлении мультиаффинной функции. Полиномиальность распознавания мультиаффинности функции алгебры логики, заданной в виде полинома Жегалкина.
Литература
-
Горшков С.П. О сложности распознавания мультиаффинности, биюнктивности, слабой положительности и слабой отрицательности // Обзор промышленной и прикладной математики. Серия Дискретная математика. 1997. Т. 4, вып. 2. С. 216-237.
-
Джавадов Р. М. О сложности приближенного задания функций алгебры логики // ДАН СССР. 1982. Т. 265, вып. 1. С. 24-27.
-
Кириченко К. Д. Верхняя оценка сложности полиномиальных нормальных форм булевых функций // Дискретная математика. 2005. Т. 17, вып. 3. С. 80-88.
-
Перязев Н. А. Сложность булевых функций в классе полиномиальных поляризованных форм // Алгебра и логика. 1995. Т. 34, вып. 3. С. 323-326.
-
Селезнева С. Н. О сложности распознавания полноты множеств булевых функций, реализованных полиномами Жегалкина // Дискретная математика. 1997. Т. 9, вып. 4. С. 24-31.
-
Селезнева С. Н. О приближении с заданной точностью функций k-значных логик полиномами // Дискретная математика. 2008. Т. 20, вып. 2. С. 32-45.
-
Even S., Kohavi I., Paz A. On minimal modulo 2 sums of products for switching functions // IEEE Trans. Elect. Comput. 1967. P. 671-674.
-
Горшков С.П., Тарасов А.В. Сложность систем булевых уравнений. М.: Курс, 2017.
-
Creignou N., Khanna S., Sudan M. Complexity classifications of Boolean constraint satisfaction problems. 2001.
-
http://mk.cs.msu.ru/index.php/Булевы_функции_и_полиномы текст лекций спецкурса
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.