Algorithms and Data Structures 2

2024/2025

Academic Year

RUS

Instruction in Russian

3

ECTS credits

Delivered at:

Joint Department with Yandex (Big Data and Information Retrieval School)

Course type:

Elective course

When:

2 year, 1 module

Instructors

Бадмаев Тингир Мингиянович

Галицкий Борис Васильевич

Gribov, Philipp

Kurenkov, Vladimir

Мамай Игорь Борисович

Temirkhanov, Aziz

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

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

Аннотация

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

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

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

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

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

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

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

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

• Домашнее задание 1
• Домашнее задание 2
• Работа на семинаре
• Экзамен

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

• 2024/2025 1st module
  0.3 * Домашнее задание 1 + 0.3 * Домашнее задание 2 + 0.1 * Работа на семинаре + 0.3 * Экзамен

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

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

• 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

Авторы

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