Бакалавриат
2024/2025
Алгоритмы и структуры данных (углубленный курс)
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Кто читает:
Базовая кафедра Яндекс
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 2-4 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Язык:
русский
Кредиты:
14
Программа дисциплины
Аннотация
Целями освоения дисциплины «Алгоритмы и структуры данных – 2» являются углубленное ознакомление студентов с основами теории вычислительной сложности, приближенными и вероятностными методами решения труднорешаемых задач, в том числе задач, возникающих в анализе данных. В курсе дается представление о классах сложности P, NP и coNP и NP-полных задачах, изучаются способы доказательства NP-полноты задач и подходы к решению таких задач, в т.ч. экспоненциальные алгоритмы, отличные от полного перебора, приближенные алгоритмы и эффективные алгоритмы для частных случаев. Также рассматриваются потоковые алгоритмы, алгоритмы эффективного перечисления последовательностей и способы оценки их вычислительной сложности (задержка, кумулятивная задержка, сложность относительно размера входа и выхода).
Цель освоения дисциплины
- ознакомление студентов с основами алгоритмической теории сложности, приближенными и вероятностными методами решения труднорешаемых задач, в том числе задач, возникающих в анализе данных
Планируемые результаты обучения
- Уметь адаптировать известные и проектировать новые алгоритмы для решения вычислительно сложных задач на практике
- Уметь разбить задачу на подзадачи, эффективно реализовать программные компоненты для отдельных подзадач и связать их воедино
- Уметь проводить анализ корректности и временной сложности алгоритмов; распознавать класс сложности задач
Содержание учебной дисциплины
- Основы теории вычислительной сложности
- Методы решения труднорешаемых задач
- Задачи и алгоритмы анализа данных
Элементы контроля
- Листки
- Контесты
- Экзамен
- Контрольная работа
- Экзамен
- Контрольная работа
- Бонус
- Контесты
- Листки
Промежуточная аттестация
- 2024/2025 2nd module0.429 * Контесты + 0.214 * Контрольная работа + 0.357 * Листки
- 2024/2025 3rd module0.3 * Контесты + 0.15 * Контрольная работа + 0.25 * Листки + 0.3 * Экзамен
- 2024/2025 4th module0.3 * Контесты + 0.15 * Контрольная работа + 0.25 * Листки + 0.3 * Экзамен
Список литературы
Рекомендуемая основная литература
- Седжвик, Р. Алгоритмы на С++ : учебное пособие / Р. Седжвик. — 2-е изд. — Москва : ИНТУИТ, 2016. — 1772 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100565 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
Рекомендуемая дополнительная литература
- Вирт, Н. Алгоритмы и структуры данных. Новая версия для Оберона : учебное пособие / Н. Вирт. — Москва : ДМК Пресс, 2010. — 272 с. — ISBN 978-5-94074-584-6. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/1261 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.