Бакалавриат
2024/2025
Алгоритмы и структуры данных 2
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Кто читает:
Базовая кафедра Яндекс
Где читается:
Факультет компьютерных наук
Когда читается:
2-й курс, 1 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Язык:
русский
Кредиты:
3
Программа дисциплины
Аннотация
Целями освоения дисциплины «Алгоритмы и структуры данных – 2» являются ознакомление студентов с основами теории вычислительной сложности, приближенными и вероятностными методами решения труднорешаемых задач, в том числе задач, возникающих в анализе данных. В курсе дается представление о классах сложности P, NP и coNP и NP-полных задачах, изучаются способы доказательства NP-полноты задач и подходы к решению таких задач, в т.ч. экспоненциальные алгоритмы, отличные от полного перебора, приближенные алгоритмы и эффективные алгоритмы для частных случаев. Также рассматриваются потоковые алгоритмы, алгоритмы эффективного перечисления последовательностей и способы оценки их вычислительной сложности (задержка, кумулятивная задержка, сложность относительно размера входа и выхода).
Цель освоения дисциплины
- ознакомление студентов с основами алгоритмической теории сложности, приближенными и вероятностными методами решения труднорешаемых задач, в том числе задач, возникающих в анализе данных
Планируемые результаты обучения
- Уметь адаптировать известные и проектировать новые алгоритмы для решения вычислительно сложных задач на практике
- Уметь проводить анализ корректности и временной сложности алгоритмов; распознавать класс сложности задач
- Уметь разбить задачу на подзадачи, эффективно реализовать программные компоненты для отдельных подзадач и связать их воедино
Содержание учебной дисциплины
- Префикс-функция и Алгоритм Ахо-Корасик
- Сжатие и кодирование данных: алгоритмы Хаффмана и Лемпела-Зива, кодирование с исправлением ошибок
- Персистентные структуры (двоичное дерево, дерево отрезков)
- Потоки, метод Форда-Фалкерсона (Паросочетания, алгоритм Куна)
- Классы P и NP
- Эвристики в рекурсивном переборе
- Быстрое преобразование Фурье
- Вычислительная геометрия
Промежуточная аттестация
- 2024/2025 1st module0.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