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

Схемы из функциональных элементов и неветвящиеся программы с условной остановкой.
Вычисление булевых функций схемами и программами с условной остановкой. Средняя сложность булевых функций.
Асимптотические оценки средней сложности n-местных булевых функций, функций данного веса и монотонных функций.
Оценки монотонной средней сложности булевых функций.
Соотношения между средней сложностью и сложностью в худшем случае.

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

Блок-дизайны и t-дизайны.
Конечные геометрии.
Матрицы Адамара.
Латинские квадраты.
Трансверсальные дизайны.
Ортогональные массивы.
Связь с линейными кодами.
Разностные множества.
Корреляционно-иммунные и бент-функции.
Вист-турниры.

Булевы функции. Матрицы Адамара. Матрица Адамара--Сильвестра. Преобразование Уолша. Матричная форма преобразования Уолша. Формула обращения для преобразования Уолша. Автокорреляционные коэффициенты. Умножение вектор-строки автокорреляционных коэффициентов на матрицу Адамара--Сильвестра. Равенство Парсеваля. Ортогональный базис в $\mathbb{R}^{2^n}$. Теорема Титсворта.

Нелинейность булевой функции, ее выражение через коэффициенты Уолша. Верхняя оценка нелинейности булевой функции. Бент-функции. PS-семейство бент-функций. Семейство бент-функций Майораны--Макфарланда.

Корреляционно-иммунные и устойчивые булевы функции. Формула суммирования Пуассона. Спектральная характеризация корреляционно-иммунных функций. Теорема Фон-Дер-Флаасса. Достижимость равенства в оценке Фон-Дер-Флаасса.

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

Обобщение функции адреса. Число булевых и платовидных функций для обобщения функции адреса при некоторых условиях.

Рекурсивная конструкция носителей спектра. Число платовидных функций для носителей спектра из этой рекурсивной конструкции.

Булевы функции с носителем спектра мощности не больше $4$. Пучки наборов из носителя спектра по направлениям. Первая теорема о структуре таких пучков.

Пучки наборов из носителя спектра по направлениям. Вторая теорема о структуре таких пучков.

Свойства коэффициентов Фурье при разложении пространства по смежным классам подпространства. Лемма об ограничении на гиперплоскость. Существование аффинного подпространства коразмерности $O(\sqrt{|S_f|})$, на котором функция постоянна.

Корзинная сложность булевой функции. Оценка $O(\sqrt{|S_f|})$ для глубины дерева решений с проверкой четности. Теорема Бернаскони--Коденотти о ранге коммуникационной матрицы XOR-функции.

Еще одно обобщение функции адреса. Вероятностное доказательство существования набора аффинных подпространств, удовлетворяющих набору свойств на их взаимное расположение. Теорема Х. Хатами--Хоссейни--Ловетта--Остуни о существовании булевой функции с достаточно маленьким максимальным пучком в носителе спектра.

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

Изгибаемость и жёсткость идеальных структур трёхмерного евклидова пространства.
Теорема Лежандра- Коши об определённости выпуклых многогранников их гранями.
Теорема Максвелла о внутреннем напряжении в рёберном скелете проекции многогранника.
Проективная инвариантность статических свойств.
Геометрическая теория шарнирных механизмов и ферм.
Теория напряжённосвязанных конструкций (tensegrity frameworks).

Основы кинематики и статики твёрдых тел.
Математические основы робототехники, теории механизмов и строительной механики.
Кинематика и статика совокупностей твёрдых тел в проективном изложении.
Введение в вещественную алгебраическую геометрию.

Равномерно дискретные точечные системы в евклидовой плоскости.
Разбиения Делоне и Вороного.
Решётки в евклидовой плоскости.
Параллелоэдры.
Задачи плотнейшей упаковки и редчайшего покрытия евклидовой плоскости равными кругами.

Задание точечных решёток в евклидовом пространстве. Решётки и квадратичные формы. Реперы.
Свойства решёток. Леммы Блихфельдта и Минковского.
Подрешётки и центрировки, сечения и проекции решёток.
Минимальные векторы решётки и задача плотнейшей решётчатой упаковки шаров.

Эффективные структуры данных (суффиксные деревья, суффиксные массивы и суффиксные автоматы) для комбинаторных алгоритмов на формальных словах и алгоритмы их построения.
Поиск образцов в формальных словах посредством различных структур данных.
Эффективные алгоритмы поиска палиндромов, повторов и периодичностей в формальных словах.