• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2020/2021

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

Статус: Курс обязательный (Прикладная математика и информатика)
Направление: 01.03.02. Прикладная математика и информатика
Когда читается: 2-й курс, 1 модуль
Формат изучения: без онлайн-курса
Охват аудитории: для своего кампуса
Язык: русский
Кредиты: 4

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

Аннотация

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

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

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

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

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

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

  • Основы теории вычислительной сложности
    Машины Тьюринга. Классы P, NP, coNP, примеры задач из этих классов. NP-полнота. Полиномиальные сведения. Теорема Кука – Левина. NP-полные задачи: 3-SAT, Not-All-Equal-3- SAT, задачи о клике, вершинном покрытии, независимом множестве, гамильтоновом пути, максимальном разрезе, сумме подмножества, рюкзаке и др. Теорема об иерархии классов сложности по времени.
  • Методы решения труднорешаемых задач
    Локальный поиск, градиентный спуск, алгоритм Метрополиса, имитация отжига. Рандомизированные и приближенные алгоритмы. Приближенное решение задачи о максимальном разрезе. Алгоритмы типа Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ.
  • Задачи и алгоритмы анализа данных
    Сегментация изображений (передний/задний план) с помощью минимального разреза. NP-трудность задачи сегментации изображений на три класса. Приближенный алгоритм сегментации изображений на несколько классов. Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние. NP-трудность кластеризации, минимизирующей максимальное внутрикластерное расстояние. Приближенный алгоритм кластеризации, минимизирующий максимальное расстояние до центра кластера. Потоковые алгоритмы. Эффективное перечисление последовательностей. Полиномиальная задержка, кумулятивная задержка, сложность алгоритма относительно размера входа и выхода.
Элементы контроля

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

  • неблокирующий Экзамен
  • неблокирующий Домашнее задание
  • неблокирующий Домашнее задание
  • неблокирующий Работа на семинаре
Промежуточная аттестация

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

  • Промежуточная аттестация (1 модуль)
    0.15 * Домашнее задание + 0.15 * Домашнее задание + 0.3 * Работа на семинаре + 0.4 * Экзамен
Список литературы

Список литературы

Рекомендуемая основная литература

  • 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
  • Rajaraman, A., & Ullman, J. D. (2012). Mining of Massive Datasets. New York, N.Y.: Cambridge University Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=408850

Рекомендуемая дополнительная литература

  • 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
  • David S. Johnson, Mihalis Yannakakis, & Christos H. Papadimitriou. (1987). North-Holland ON GENERATING ALL MAXIMAL INDEPENDENT SETS. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.5437CE76