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

Булевы функции, формулы, схемы, компьютерная арифметика, эквивалентные преобразования,NP-полные задачи
Самокорректирующиеся схемы и коды, надежные схемы из ненадежных компонентов
Тесты, разрешающие диаграммы и распознавание образов

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

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

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

Изгибаемость и жёсткость многогранников. Теоремы Коши и Максвелла.
Геометрия шарнирных устройств.
Кинематика и статика в проективном изложении.
Напряжённосвязанные конструкции.

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

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

Перечисление графов.
Цепи, циклы, покрытия, потоки.
Теоремы Менгера, Эйлера, Холла, Дируорса, Форда-Фалкерсона.
Раскраски графов. Теоремы Брукса, Визинга, Рамсея.
Плоские графы.
Реализация графов на плоскости и в пространстве.
Алгоритмы на графах.
Сложность графов.

Базовые понятия и результаты словарной комбинаторики
Основные алгоритмы поиска образцов в символьных последовательностях
Поиск образцов в символьных последовательностях с использованием константного объема дополнительной памяти