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

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

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

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

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

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

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

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