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

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

Язык: русский
Кредиты: 4

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

Аннотация

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

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

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

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

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

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

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

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

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

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

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

  • 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

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

  • 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