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

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

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

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

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

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

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

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

Преподаватели: Анопренко Михаил Валентинович, Грибов Филипп Юрьевич, Ковальков Дмитрий Андреевич, Сафонов Иван Андреевич, Смирнов Иван Федорович

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

Кредиты: 4

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

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

Аннотация

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

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

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

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

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