Алгоритмы и структуры данных 2

2026/2027

Учебный год

RUS

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

3

Кредиты

Кто читает:

Базовая кафедра Яндекс (Департамент больших данных и информационного поиска)

Статус:

Курс обязательный

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

2-й курс, 1 модуль

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

Богданов Сергей Юрьевич

Горшков Даниил Александрович

Густокашин Михаил Сергеевич

Кубарев Александр Сергеевич

Куренков Владимир Вячеславович

Лоредо Андрей Александрович

Любимов Яков Александрович

Мануйленко Никита Сергеевич

Нестеренко Алиса Вадимовна

Плетенев Борис Александрович

Урьев Максим Дмитриевич

Фолунин Владимир Александрович

Цивин Сергей Владимирович

Шинкарев Елисей Сергеевич

Шубников Кирилл Сергеевич

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

Аннотация

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

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

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

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

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

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

• Жадные алгоритмы
• Префикс-функция и Алгоритм Ахо-Корасик
• Сжатие и кодирование данных: алгоритмы Хаффмана и Лемпела-Зива, кодирование с исправлением ошибок
• Персистентные структуры (двоичное дерево, дерево отрезков)
• Параллельность в C++ (Параллельные алгоритмы)
• Потоки, метод Форда-Фалкерсона (Паросочетания, алгоритм Куна)
• Классы P и NP
• Эвристики в рекурсивном переборе
• Быстрое преобразование Фурье
• Вычислительная геометрия

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

• Домашнее задание
• Работа на семинаре
• Экзамен
• Внешний экзамен компетенций образовательной программы топ-уровня

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

• 2026/2027 1st module
  0.1 * Работа на семинаре + 0.25 * Экзамен + 0.6 * Домашнее задание + 0.05 * Внешний экзамен компетенций образовательной программы топ-уровня

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

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

• Cormen, T. H. (2009). Introduction to Algorithms (Vol. 3rd ed). Cambridge, Mass: The MIT Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=343613
• Вычислительные машины и труднорешаемые задачи, Гэри, М., 1982

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

• Arora, S., & Barak, B. (2009). Computational Complexity : A Modern Approach. Cambridge: Cambridge eText. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=304712
• Алгоритмы : построение и анализ : пер. с англ., Кормен, Т., 2000

Авторы

• Фисенко Анна Сергеевна
• Густокашин Михаил Сергеевич
• Алиева Эльмира Махир Кызы