Средняя сложность булевых функций
Название спецкурса на английском языке
Boolean average-case complexity
Пререквизиты
Отсутствуют
Целевая аудитория
1-2 курс
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра дискретной математики]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2025/26
Список тем
Схемы из функциональных элементов и неветвящиеся программы с условной остановкой.
Вычисление булевых функций схемами и программами с условной остановкой. Средняя сложность булевых функций.
Асимптотические оценки средней сложности n-местных булевых функций, функций данного веса и монотонных функций.
Оценки монотонной средней сложности булевых функций.
Соотношения между средней сложностью и сложностью в худшем случае.
Вычисление булевых функций схемами и программами с условной остановкой. Средняя сложность булевых функций.
Асимптотические оценки средней сложности n-местных булевых функций, функций данного веса и монотонных функций.
Оценки монотонной средней сложности булевых функций.
Соотношения между средней сложностью и сложностью в худшем случае.
Список источников
Чашкин А. В. Асимптотические оценки средней сложности
булевых функций // Математические вопросы кибернетики. Вып. 20. — М.: ФИЗМАТЛИТ, 2022. — С. 257–306.
булевых функций // Математические вопросы кибернетики. Вып. 20. — М.: ФИЗМАТЛИТ, 2022. — С. 257–306.
Дополнительная информация
Связь с лектором: chashkin@inbox.ru
День недели
по согласованию
Время
по согласованию
Аудитория
Ещё не назначена
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.