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

Бакалавриат 2022/2023

Лучший по критерию «Новизна полученных знаний»

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

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

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

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

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

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

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

Преподаватели: Борзунов Александр Александрович, Гаглоев Александр Владимирович, Галицкий Борис Васильевич, Голиков Никита Русланович, Грибов Филипп Юрьевич, Густокашин Михаил Сергеевич, Киракосян Вазген Валерикович, Кравцов Дмитрий Александрович, Курилкин Александр Сергеевич, Тибилов Таймураз Валерьевич, Фолунин Владимир Александрович, Чабдаров Раиль Альфредович

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

Кредиты: 4

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

Полная версия программы учебной дисциплины

Аннотация

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

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

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

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

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

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

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

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

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

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

2022/2023 учебный год 1 модуль
0.3 * Домашнее задание + 0.1 * Работа на семинаре + 0.3 * Экзамен + 0.3 * Домашнее задание

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