2025/2026
Алгоритмы как математическое исследование
Статус:
Дисциплина общефакультетского пула
Кто читает:
Факультет математики
Где читается:
Факультет математики
Когда читается:
3, 4 модуль
Охват аудитории:
для всех кампусов НИУ ВШЭ
Язык:
русский
Кредиты:
6
Контактные часы:
72
Программа дисциплины
Аннотация
Слово Алгоритм часто оказывается мостом между программированием и математикой. Мы расскажем о том, в чём заключается и как оценивается эффективность алгоритмов. С одной стороны, алгоритмы оцениваются по своей асимптотической сложности. С другой стороны, мы уделим должное внимание структурам данных, выбор которых существенно влияет на сложность алгоритмов. Участники получат опыт практической реализации алгоритмов в виде программ: без этой работы было бы слишком трудно по настоящему понять алгоритмы. Курс будет иллюстрирован примерами, как из учебников, так и из практики.
Замечание
Студенты матфака имеют широкие возможности выбора курсов, в частности на других факультетах ВШЭ и в ШАД имеются глубокие многосеместровые курсы по Алгоритмам. Выбирая между этими возможностями следует иметь в виду, что наша цель состоит прежде всего в том, чтобы за ограниченное время показать математику в алгоритмах, используя минимальный багаж программирования, что удобно для тех, кто пока ещё присматривается к компьютерным наукам.
Содержание учебной дисциплины
- Начальные примеры алгоритмических задач. Понятие сложности алгоритма и сложности задачи. Нижние оценки сложности алгоритмов. Навыки: алгоритмы на множествах чисел, оценка их сложности.
- Стандартные структуры данных: массив, стек, очередь, список, дерево, хэш таблица. Навыки: умение программировать некоторые методы структур данных и выбирать подходящую структуру для задачи.
- Неориентированные графы и их обходы. Поиск в ширину и его применения. Навык: умение решать алгоритмические задачи на графах методом построения структуры данных и по- иска в ширину.
- Ориентированные графы и порядки на множествах. Поиск в глубину. Топологическая сортировка, поиск сильно связных компонент, перечисление всех ориентированных циклов. Навык: построение полных порядков из предпорядка.
- Потоки на графах. Алгоритмы поиска максимального потока и минимального разреза. Многопродуктовые потоки, алгоритмы поиска максимального конкурентного потока. Навык: решение задач методом построения и максимизации потока на графе.
- Динамическое программирование
- Жадные алгоритмы и их применимость. Матроиды и субмодулярные функции. Примеры (минимальное покрывающее дерево, упаковка рюкзака, оптимальное расписание, покраски графов). Навык: умение видеть задачи, допускающие точные жадные алгоритмы
Промежуточная аттестация
- 2025/2026 4th module0.125 * Решение задач + 0.35 * Устный экзамен + 0.15 * Колоквиум + 0.125 * Решение задач посредством программирования
