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

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

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

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

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

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

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

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