Название спецкурса на русском языке
Сложность булевых функций
Перевод названия курса на английский язык
Boolean complexity
Авторы курса
Чашкин Александр Викторович
Целевая аудитория
2 курс
3 курс
4 курс
5 курс
6 курс
Подразделение
[Кафедра дискретной математики]
Семестр
Полгода (осень)
Тип курса
Спецкурс по выбору кафедры
Учебный год
2021/22
Аудитория
[Неприменимо]
Аннотация
В курсе рассматриваются следующие вопросы. Реализация функций формулами, схемами, автоматами и машинами Тьюринга. Сложность функции. Сложность систем линейных булевых функций. Оценки сложности и глубины вычисления префиксных сумм. Оценки сложности и глубины арифметических операций над целыми числами. Оценки сложности быстрого преобразования Фурье и умножения многочленов. Асимптотические методы реализации булевых функций схемами и формулами. Оценки сложности вычисления монотонных булевых функций. Вычисления с ограниченной памятью. Схемы на плоскости и их сложность (площадь). Схемы в 3-х мерном пространстве и их сложность (объем). Самокорректирующиеся схемы. Моделирование схем автоматами и машинами Тьюринга. Теорема Кука. NP-полные задачи.