[Кафедра дискретной математики]

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

Битовая сложность умножения чисел. Быстрые алгоритмы умножения, их особенности.
Задача об эффективном возведении в степень и задача об аддитивных цепочках.
Векторные аддитивные цепочки. Задача Р. Беллмана. Задача Д. Кнута. Двойственность.
Сборка слов схемами конкатенации. Конструктивная нижняя оценка сложности сборки асимптотически самого сложного слова заданной длины.
Задача О. Б. Лупанова о сложности реализации элементов конечных абелевых групп.
Асимптотически точное решение.
Сложность вычисления элементов конечных нильпотентных и разрешимых групп.
Задача Н. Пиппенджера о сложности вычисления систем одночленов от нескольких переменных. Унивесальная нижняя оценка. Простые случаи: два одночлена или две переменные.
Сравнение задачи Пиппенджера и задачи о сложности вычисления систем элементов конечных абелевых групп.
Сложность аддитивных вычислений целочисленных линейных форм.
Задача о сложности вычисления элементов свободных абелевых групп.
Схемы из делений.
Сложность классических и обобщенных вентильных схем.

Трудности получения эффективных нижних оценок сложности для индивидуальных последовательностей функций. Теорема Яблонского о невозможности элиминации перебора при построении последовательности самых сложных функций. Нетривиальные линейные оценки в классе схем из функциональных элементов.
Контактные схемы. Физическая модель. Сложность контактных схем. Контактное дерево для системы конъюнкций. Минимальность контактного дерева в классе разделительных схем.
Метод каскадов. Наилучший по порядку метод синтеза схем на основе метода каскадов. Реализация линейной функции методом каскадов.
Разбиение наборов длины $2^m$ на непересекающиеся сферы. Асимптотически оптимальная реализация системы всех конъюнкций.
Мощностная нижняя оценка функции Шеннона сложности реализации булевых функций контактными схемами.
Асимптотически наилучший метод О. Б. Лупанова синтеза контактных схем. Корректирование одного замыкания или размыкания без асимптотического увеличения сложности.
Сложность формул как число символов переменных и как число функциональных символов. Мощностная нижняя оценка функции Шеннона сложности реализации булевых функций формулами (для двух определений сложности формулы).
Параллельно-последовательные контактные схемы, их связь с формулами в базисе $\{ \vee, \&, - \}$.Асимптотически наилучший метод О. Б. Лупанова синтеза параллельно-последовательных контактных схем.
Сложность реализации функции, принимающей единичное значение на наборах с одной единицей, контактными схемами. Теорема Кардо о сложности реализации линейной функции контактными схемами.
Метод Б. А. Субботовской получения нижних оценок сложности реализации булевых функций в классе параллельно-последовательных контактных схем. Нижняя оценка сложности линейных функций по методу Субботовской.
Метод В. М. Храпченко. Простые цепи и тупиковые сечения в параллельно-последовательных контактных схемах и их свойства. Теорема Храпченко о нижней оценке сложности реализации булевой функции в классе параллельно-последовательных контактных схем. Нижняя квадратичная оценка сложности реализации линейных функций.
Метод Э. И. Нечипорука получения нижних оценок сложности реализации булевых функций формулами в произвольном конечном базисе. Функция Нечипорука и нижняя оценка ее сложности при реализации формулами в произвольном конечном базисе.

Неявная выразимость. Параметрическая выразимость. Неэквивалентность неявной и
параметрической выразимости в P_k при k ⩾ 3.
Рефлексивность и монотонность оператора неявной выразимости. Цепочка вложений операторов выразимости.
Классы сохранения матриц и предикатов.
Централизаторы и бицентрализаторы. Централизатор как класс сохранения предиката.
Описание 25 параметрически замкнутых классов в P_2.
Эквивалентность неявной и параметрической выразимости в P_2.
Минимальные неявно полные классы без констант в P_3.
Критерий неявной полноты в P_k.

Реализация булевых функций формулами, схемами, автоматами и машинами Тьюринга. Сложность функции.
Сложность систем линейных булевых функций.
Оценки сложности и глубины вычисления префиксных сумм.
Оценки сложности и глубины арифметических операций над целыми числами.
Оценки сложности быстрого преобразования Фурье и умножения многочленов. Асимптотические методы реализации булевых функций схемами и формулами.
Оценки сложности вычисления монотонных булевых функций.
Вычисления с ограниченной памятью.
Схемы на плоскости и их сложность (площадь).
Схемы в 3-х мерном пространстве и их сложность (объем).
Самокорректирующиеся схемы.
Моделирование схем автоматами и машинами Тьюринга.
Теорема Кука. NP-полные задачи.

Преобразование Уолша булевой функции и его свойства.
Полиномиальные представления булевой функции, их свойства и следствия.
Теорема Симона-Вегенера и следствия из нее.
Регулярные булевы функции и их свойства.
Сложностные характеристики булевой функции и их взаимосвязь.
Деревья решений.
Приложения анализа булевых функций в теории сложности.
Нелинейность булевых функций.
Корреляционно-иммунные и устойчивые булевы функции.
Приложения анализа булевых функций в криптологии.