Алгоритмы как математическое исследование

2024/2025

Учебный год

RUS

Обучение ведется на русском языке

6

Кредиты

Кто читает:

Факультет математики

Статус:

Дисциплина общефакультетского пула

Когда читается:

3, 4 модуль

Преподаватель

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

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

Аннотация

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

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

• -

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

• --

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

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

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

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

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

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

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

Рекомендуемая основная литература

• Алгоритмы: построение и анализ : пер.с англ., Кормен, Т., 2013

Рекомендуемая дополнительная литература

• Алгоритмы, Дасгупта, С., 2023

Авторы

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