Бакалавриат
2020/2021
Алгоритмы и структуры данных 2 (углубленный курс)
Лучший по критерию «Полезность курса для Вашей будущей карьеры»
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс обязательный (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Кто читает:
Базовая кафедра Яндекс
Где читается:
Факультет компьютерных наук
Когда читается:
2-й курс, 1 модуль
Формат изучения:
без онлайн-курса
Преподаватели:
Артюхин Станислав Геннадьевич,
Евстропов Глеб Олегович,
Попов Максим Павлович,
Резников Григорий Михайлович,
Сендерович Никита Леонидович,
Смирнов Иван Федорович
Язык:
русский
Кредиты:
4
Контактные часы:
56
Программа дисциплины
Аннотация
Целями освоения дисциплины «Алгоритмы и структуры данных – 2» являются углубленное ознакомление студентов с основами теории вычислительной сложности, приближенными и вероятностными методами решения труднорешаемых задач, в том числе задач, возникающих в анализе данных. В курсе дается представление о классах сложности P, NP и coNP и NP-полных задачах, изучаются способы доказательства NP-полноты задач и подходы к решению таких задач, в т.ч. экспоненциальные алгоритмы, отличные от полного перебора, приближенные алгоритмы и эффективные алгоритмы для частных случаев. Также рассматриваются потоковые алгоритмы, алгоритмы эффективного перечисления последовательностей и способы оценки их вычислительной сложности (задержка, кумулятивная задержка, сложность относительно размера входа и выхода).
Цель освоения дисциплины
- ознакомление студентов с основами алгоритмической теории сложности, приближенными и вероятностными методами решения труднорешаемых задач, в том числе задач, возникающих в анализе данных
Планируемые результаты обучения
- Уметь проводить анализ корректности и временной сложности алгоритмов; распознавать класс сложности задач
- Уметь адаптировать известные и проектировать новые алгоритмы для решения вычислительно сложных задач на практике
- Уметь разбить задачу на подзадачи, эффективно реализовать программные компоненты для отдельных подзадач и связать их воедино
Содержание учебной дисциплины
- Основы теории вычислительной сложностиМашины Тьюринга. Классы P, NP, coNP, примеры задач из этих классов. NP-полнота. Полиномиальные сведения. Теорема Кука – Левина. NP-полные задачи: 3-SAT, Not-All-Equal-3- SAT, задачи о клике, вершинном покрытии, независимом множестве, гамильтоновом пути, максимальном разрезе, сумме подмножества, рюкзаке и др. Теорема об иерархии классов сложности по времени.
- Методы решения труднорешаемых задачЛокальный поиск, градиентный спуск, алгоритм Метрополиса, имитация отжига. Рандомизированные и приближенные алгоритмы. Приближенное решение задачи о максимальном разрезе. Алгоритмы типа Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ.
- Задачи и алгоритмы анализа данныхСегментация изображений (передний/задний план) с помощью минимального разреза. NP-трудность задачи сегментации изображений на три класса. Приближенный алгоритм сегментации изображений на несколько классов. Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние. NP-трудность кластеризации, минимизирующей максимальное внутрикластерное расстояние. Приближенный алгоритм кластеризации, минимизирующий максимальное расстояние до центра кластера. Потоковые алгоритмы. Эффективное перечисление последовательностей. Полиномиальная задержка, кумулятивная задержка, сложность алгоритма относительно размера входа и выхода.
Список литературы
Рекомендуемая основная литература
- Седжвик Р. - Алгоритмы на С++ - Национальный Открытый Университет "ИНТУИТ" - 2016 - 1772с. - ISBN: - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/100565
Рекомендуемая дополнительная литература
- Вирт Н. - Алгоритмы и структуры данных. Новая версия для Оберона - Издательство "ДМК Пресс" - 2010 - 272с. - ISBN: 978-5-94074-584-6 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/1261