Математические олимпиады

Regular version of the site

Delivered by:: Faculty of Mathematics

Type:: Optional course (faculty)

When:: 3, 4 module

Дополнительные материалы в LMS Задать вопрос

Аннотация

Слово "Алгоритм" часто оказывается мостом между программированием и математикой. Мы расскажем о том, в чём заключается и как оценивается эффективность алгоритмов, при этом мы уделим должное внимание структурам данных, выбор которых существенно влияет на сложность алгоритмов. Курс включает лекции, решение задач на алгоритмы, а также участники получат опыт практической реализации алгоритмов в виде программ: без этой работы было бы слишком трудно по настоящему понять алгоритмы. Курс ориентирован на математическую составляющую построения и анализа алгоритмов, в которых теоремы и другие утверждения не менее важны, чем сами алгоритмы.

Цель освоения дисциплины

Планируемые результаты обучения

Содержание учебной дисциплины

Начальные примеры алгоритмических задач. Понятие сложности алгоритма и сложности задачи. Нижние оценки сложности алгоритмов. Навыки: алгоритмы на множествах чисел, оценка их сложности.
Стандартные структуры данных: массив, стек, очередь, список, дерево, хэш таблица. Навыки: умение программировать некоторые методы структур данных и выбирать подходящую структуру для задачи.
Неориентированные графы и их обходы. Поиск в ширину и его применения. Навык: умение решать алгоритмические задачи на графах методом построения структуры данных и по- иска в ширину.
Ориентированные графы и порядки на множествах. Поиск в глубину. Топологическая сортировка, поиск сильно связных компонент, перечисление всех ориентированных циклов. Навык: построение полных порядков из предпорядка.
Потоки на графах. Алгоритмы поиска максимального потока и минимального разреза. Многопродуктовые потоки, алгоритмы поиска максимального конкурентного потока. Навык: решение задач методом построения и максимизации потока на графе.
Динамическое программирование
Жадные алгоритмы и их применимость. Матроиды и субмодулярные функции. Примеры (минимальное покрывающее дерево, упаковка рюкзака, оптимальное расписание, покраски графов). Навык: умение видеть задачи, допускающие точные жадные алгоритмы

Элементы контроля

Решение задач
Решение задач посредством программирования
Колоквиум
Устный экзамен

Промежуточная аттестация

2025/2026 4th module
0.125 * Решение задач + 0.35 * Устный экзамен + 0.15 * Колоквиум + 0.125 * Решение задач посредством программирования

Список литературы

Авторы

Клименко Алексей Владимирович

Algorithms as Math Research

Программа дисциплины