2022/2023

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

Статус: Маго-лего

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

Когда читается: 3, 4 модуль

Охват аудитории: для всех кампусов НИУ ВШЭ

Преподаватели: Бабенко Максим Александрович

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

Кредиты: 6

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

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

Аннотация

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