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

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

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Направление: 01.03.02. Прикладная математика и информатика
Когда читается: 2-й курс, 1 модуль
Формат изучения: без онлайн-курса
Охват аудитории: для своего кампуса
Язык: русский
Кредиты: 3
Контактные часы: 56

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

Аннотация

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

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

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

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

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

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

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

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

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

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

  • 2023/2024 учебный год 1 модуль
    0.3 * Домашнее задание 1 + 0.3 * Домашнее задание 2 + 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
  • Вычислительные машины и труднорешаемые задачи, Гэри, М., 1982

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

  • 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
  • Алгоритмы : построение и анализ : пер. с англ., Кормен, Т., 2000

Авторы

  • Фисенко Анна Сергеевна
  • Густокашин Михаил Сергеевич
  • Алиева Эльмира Махир Кызы