Анализ булевых функций и приложения. I
Название спецкурса на английском языке
Analysis of boolean functions and related issues. I
Пререквизиты
Базовые знания математического анализа, линейной и высшей алгебры.
Целевая аудитория
1-2 курс
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра дискретной математики]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Преобразование Уолша булевой функции и его свойства.
Полиномиальные представления булевой функции, их свойства и следствия.
Теорема Симона-Вегенера и следствия из нее.
Регулярные булевы функции и их свойства.
Сложностные характеристики булевой функции и их взаимосвязь.
Деревья решений.
Приложения анализа булевых функций в теории сложности.
Нелинейность булевых функций.
Корреляционно-иммунные и устойчивые булевы функции.
Приложения анализа булевых функций в криптологии.
Полиномиальные представления булевой функции, их свойства и следствия.
Теорема Симона-Вегенера и следствия из нее.
Регулярные булевы функции и их свойства.
Сложностные характеристики булевой функции и их взаимосвязь.
Деревья решений.
Приложения анализа булевых функций в теории сложности.
Нелинейность булевых функций.
Корреляционно-иммунные и устойчивые булевы функции.
Приложения анализа булевых функций в криптологии.
Список источников
O’Donnell R. Analysis of boolean functions. Cambridge University Press, 2014.
Wegener I., The complexity of boolean functions, Wiley-Teubner Series in Computer Science, Teubner, Stuttgart, 1987.
Carlet C. Boolean functions for cryptography and coding theory. Cambridge University Press, 2021.
Таранников Ю. В. О корреляционно-иммунных и устойчивых булевых функциях. Математические вопросы кибернетики, 2002, вып. 11, с. 91-148.
Nisan N., CREW PRAMs and decision trees, SIAM J. Comput. 20 (6) (1991), p. 999 -1007.
Rubinstein D., Sensitivity vs. block sensitivity of Boolean functions, Combinatorica 15 (2) (1995), p. 297-299.
Buhrman H., de Wolf R. Complexity measures and decision tree complexity: a survey, Theoretical Computer Science 288 (2002), p. 21-43.
Wegener I., The complexity of boolean functions, Wiley-Teubner Series in Computer Science, Teubner, Stuttgart, 1987.
Carlet C. Boolean functions for cryptography and coding theory. Cambridge University Press, 2021.
Таранников Ю. В. О корреляционно-иммунных и устойчивых булевых функциях. Математические вопросы кибернетики, 2002, вып. 11, с. 91-148.
Nisan N., CREW PRAMs and decision trees, SIAM J. Comput. 20 (6) (1991), p. 999 -1007.
Rubinstein D., Sensitivity vs. block sensitivity of Boolean functions, Combinatorica 15 (2) (1995), p. 297-299.
Buhrman H., de Wolf R. Complexity measures and decision tree complexity: a survey, Theoretical Computer Science 288 (2002), p. 21-43.
Дополнительная информация
Связь с лектором по эл. почте yutarann@gmail.com
День недели
четверг
Время
12:30-14:05
Аудитория
1404
Дата первого занятия
Аудитория первого занятия
1404
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.