Булевы функции и полиномы

Полугодовой спецкурс. Лектор - Селезнева С.Н.

Программа

Полиномы: обобщенные, Жегалкина, поляризованные. Теоремы о реализации булевых функций ими.

Быстрые алгоритмы построения векторов коэффициентов полинома Жегалкина и поляризованных полиномов по вектору значений булевой функции.

Сложность реализации булевых функций обобщенными полиномами.

Сложность реализации булевых функций поляризованными полиномами.

Сложность приближенной реализации булевых функций полиномами Жегалкина.

Алгоритмическая сложность распознавания монотонности булевой функции, заданной полиномом Жегалкина.

Четные и нечетные булевы функции. Свойства полиномов четных и нечетных булевых функций.

Алгоритмическая сложность распознавания самодвойственности булевой функции, заданной полиномом Жегалкина.

Преобразование Мебиуса. Теорема о выражении коэффициентов полинома Жегалкина булевой функции через ее значения.

Полиномы над кольцом целых чисел. Теоремы о реализации булевых функций ими.

Теорема о выражении коэффициентов полинома над кольцом целых чисел булевой функции через ее значения.

Алгоритмическая сложность нахождения остатка от деления на степень двойки веса булевой функции, заданной полиномом Жегалкина.

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

текст лекций

Литература

1. Яблонский С. В. Введение в дискретную математику. М., Высшая школа, 2001 (Гл. 1, с. 9-42).
2. Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. М., Физматлит, 2004 (Гл. 1, п. 3, с. 52-58).
3. Кириченко К. Д. Верхняя оценка сложности полиномиальных нормальных форм булевых функций. Дискретная математика, т, 17, вып. 3, 2005, с. 80-88.
4. Even S., Kohavi I., Paz A. On minimal modulo 2 sums of products for switching functions. IEEE Trans. Elect. Comput., 1967< p. 671-674.
5. Перязев Н. А. Сложность булевых функций в классе полиномиальных поляризованных форм. Алгебра и логика, т. 34, вып. 3, 1995, с. 323-326.
6. Джавадов Р. М. О сложности приближенного задания функций алгебры логики. ДАН, т. 265, вып. 1, 1982, с. 24-27.
7. Селезнева С. Н. О сложности распознавания полноты множеств булевых функций, реализованных полиномами Жегалкина. Дискретная математика, т. 9, вып. 4, 1997, с. 24-31.
8. Логачев О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии. М., МЦНМО, 2004 (Гл. 2, п. 2.1-2.2, с. 65-90).
9. Carlet C., Guillot Ph. A new representation of Boolean functions. Technical report INRIA Project CODES, 1999, p. 1-14.
10. Селезнева С. Н. Об алгоритмической сложности нахождения остатка от деления на степень двойки веса булевой функции, заданной полиномом. Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2007, вып. 1, с. 25-29.
11. Селезнева С. Н. О приближении с заданной точностью функций k-значных логик полиномами. Дискретная математика, т. 20, вып. 2, 2008, с. 32-45.
12. Khovratovich D. Divisibility of a Hamming Weight by 2^k and Monomial Criteria for Boolean Functions.