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

Regular version of the site

Delivered by:: Faculty of Mathematics

Type:: Optional course (faculty)

When:: 3, 4 module

Instructor

Klimenko, Alexey V.

Полная версия программы учебной дисциплины Задать вопрос

Аннотация

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

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

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

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

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

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

КР
Коллоквиум
Экзамен

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

2024/2025 4th module
Оценка складывается из 3 составляющих. 50% составит оценка за выполнение периодически анонсируемых упражнений по решению задач, как в виде текстового решения, так и на программирование; 15% — оценка за коллоквиум в конце третьего модуля; 35% — оценка за устный экзамен в конце курса.

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

Авторы

Иконописцева Юлия Вахтанговна
Клименко Алексей Владимирович

Algorithms as Math Research