2024/2025
Алгоритмы как математическое исследование
Лучший по критерию «Полезность курса для Вашей будущей карьеры»
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Статус:
Дисциплина общефакультетского пула
Кто читает:
Факультет математики
Где читается:
Факультет математики
Когда читается:
3, 4 модуль
Охват аудитории:
для всех кампусов НИУ ВШЭ
Преподаватели:
Клименко Алексей Владимирович
Язык:
русский
Кредиты:
6
Программа дисциплины
Аннотация
Слово "Алгоритм" часто оказывается мостом между программированием и математикой. Мы расскажем о том, в чём заключается и как оценивается эффективность алгоритмов, при этом мы уделим должное внимание структурам данных, выбор которых существенно влияет на сложность алгоритмов. Курс включает лекции, решение задач на алгоритмы, а также участники получат опыт практической реализации алгоритмов в виде программ: без этой работы было бы слишком трудно по настоящему понять алгоритмы. Курс ориентирован на математическую составляющую построения и анализа алгоритмов, в которых теоремы и другие утверждения не менее важны, чем сами алгоритмы.
Содержание учебной дисциплины
- Начальные примеры алгоритмических задач. Понятие сложности алгоритма и сложности задачи. Нижние оценки сложности алгоритмов. Навыки: алгоритмы на множествах чисел, оценка их сложности.
- Стандартные структуры данных: массив, стек, очередь, список, дерево, хэш таблица. Навыки: умение программировать некоторые методы структур данных и выбирать подходящую структуру для задачи.
- Неориентированные графы и их обходы. Поиск в ширину и его применения. Навык: умение решать алгоритмические задачи на графах методом построения структуры данных и по- иска в ширину.
- Ориентированные графы и порядки на множествах. Поиск в глубину. Топологическая сортировка, поиск сильно связных компонент, перечисление всех ориентированных циклов. Навык: построение полных порядков из предпорядка.
- Потоки на графах. Алгоритмы поиска максимального потока и минимального разреза. Многопродуктовые потоки, алгоритмы поиска максимального конкурентного потока. Навык: решение задач методом построения и максимизации потока на графе.
- Динамическое программирование
- Жадные алгоритмы и их применимость. Матроиды и субмодулярные функции. Примеры (минимальное покрывающее дерево, упаковка рюкзака, оптимальное расписание, покраски графов). Навык: умение видеть задачи, допускающие точные жадные алгоритмы
Промежуточная аттестация
- 2024/2025 4th moduleОценка складывается из 3 составляющих. 50% составит оценка за выполнение периодически анонсируемых упражнений по решению задач, как в виде текстового решения, так и на программирование; 15% — оценка за коллоквиум в конце третьего модуля; 35% — оценка за устный экзамен в конце курса.
