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

Алгоритмы и структуры данных 2 (углубленный курс)

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

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

Аннотация

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

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

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

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

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

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

  • Основы теории вычислительной сложности
  • Методы решения труднорешаемых задач
  • Задачи и алгоритмы анализа данных
Элементы контроля

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

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

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

  • 2021/2022 учебный год 1 модуль
    0.6 * Накопленная оценка + 0.4 * Экзамен
Список литературы

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

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

  • Седжвик Р. - Алгоритмы на С++ - Национальный Открытый Университет "ИНТУИТ" - 2016 - ISBN: - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/100565

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

  • Вирт Н. - Алгоритмы и структуры данных. Новая версия для Оберона - Издательство "ДМК Пресс" - 2010 - ISBN: 978-5-94074-584-6 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/1261