Алгоритмы и структуры данных (углубленный курс)

Бакалавриат 2024/2025

Статус: Курс по выбору (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Базовая кафедра Яндекс

Где читается: Факультет компьютерных наук

Когда читается: 1-й курс, 2-4 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для своего кампуса

Преподаватели: Волков Иван Андреевич, Голиков Никита Русланович, Грибов Филипп Юрьевич

Язык: русский

Кредиты: 14

Контактные часы: 216

Дополнительные материалы в LMS Задать вопрос

Аннотация

Целями освоения дисциплины «Алгоритмы и структуры данных – 2» являются углубленное ознакомление студентов с основами теории вычислительной сложности, приближенными и вероятностными методами решения труднорешаемых задач, в том числе задач, возникающих в анализе данных. В курсе дается представление о классах сложности P, NP и coNP и NP-полных задачах, изучаются способы доказательства NP-полноты задач и подходы к решению таких задач, в т.ч. экспоненциальные алгоритмы, отличные от полного перебора, приближенные алгоритмы и эффективные алгоритмы для частных случаев. Также рассматриваются потоковые алгоритмы, алгоритмы эффективного перечисления последовательностей и способы оценки их вычислительной сложности (задержка, кумулятивная задержка, сложность относительно размера входа и выхода).

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

ознакомление студентов с основами алгоритмической теории сложности, приближенными и вероятностными методами решения труднорешаемых задач, в том числе задач, возникающих в анализе данных

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

Уметь адаптировать известные и проектировать новые алгоритмы для решения вычислительно сложных задач на практике
Уметь разбить задачу на подзадачи, эффективно реализовать программные компоненты для отдельных подзадач и связать их воедино
Уметь проводить анализ корректности и временной сложности алгоритмов; распознавать класс сложности задач

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

Основы теории вычислительной сложности
Методы решения труднорешаемых задач
Задачи и алгоритмы анализа данных

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

Листки
Контесты
Экзамен
Контрольная работа
Экзамен
Контрольная работа
Бонус
Контесты
Листки

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

2024/2025 2nd module
0.429 * Контесты + 0.214 * Контрольная работа + 0.357 * Листки
2024/2025 3rd module
0.15 * Контрольная работа + 0.3 * Контесты + 0.3 * Экзамен + 0.25 * Листки
2024/2025 4th module
0.15 * Контрольная работа + 0.25 * Листки + 0.3 * Экзамен + 0.3 * Контесты

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

Авторы

Евстропов Глеб Олегович
Алиева Эльмира Махир Кызы
Смирнов Иван Федорович
Фисенко Анна Сергеевна

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