• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Algorithms and Data Structures

2021/2022
Academic Year
RUS
Instruction in Russian
9
ECTS credits
Course type:
Compulsory course
When:
1 year, 2, 4 module

Instructors


Bragin, Sergey


Гаглоев Александр Владимирович


Кильянов Александр Андреевич


Киракосян Вазген Валерикович


Михеев Александр Георгиевич


Наймушин Вячеслав Иванович


Погодина Екатерина Валерьевна


Popov, Maksim


Яковлев Даниил Дмитриевич

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

Аннотация

В курсе рассматриваются основные подходы к анализу и проектированию алгоритмов и структур данных. Среди тем, изучаемых в курсе, — асимптотическая оценка сложности алгоритма в худшем случае, эффективные алгоритмы сортировки и выбора порядковых статистик, структуры данных (двоичные деревья поиска, кучи, хеш-таблицы), способы проектирования алгоритмов (разделяй и властвуй, динамическое программирование, жадная стратегия), основные алгоритмы на графах (кратчайшие пути, топологическая сортировка, компоненты связности, минимальные остовные деревья).
Цель освоения дисциплины

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

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

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

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

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

  • Рекурсивные алгоритмы и рекуррентные соотношения
  • Асимптотический анализ
  • Динамическое программирование
  • Сортировки
  • Разделяй и властвуй
  • Алгоритмы на графах
  • Структуры данных
  • Жадные алгоритмы
  • Потоки в сетях
  • Конечные автоматы, регулярные выражения, контекстно-свободные грамматики
Элементы контроля

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

  • неблокирующий Домашнее задание
    Итоговая оценка за выполнение домашних заданий определяется по формуле round((A + 0.5B - 2C) / 47 * 10), где: A — количество задач, сданных до дедлайнов; B — количество задач, сданных после дедлайнов; C — количество штрафных баллов за нарушение академических норм. Итоговая оценка за выполнение домашних заданий выражается целым числом от 0 до 10 (если результат получился меньше 0 или больше 10, то он заменяется на 0 или 10 соответственно). Всего в домашних заданиях было выдано 52 задачи. Для получения итоговой оценки 10 достаточно решить 47 из них.
  • неблокирующий Контрольная работа 1
  • неблокирующий Работа на семинаре 1
  • неблокирующий Экзамен (письменный) 1
  • неблокирующий Домашнее задание 2
  • неблокирующий Контрольная работа 2
  • неблокирующий Работа на семинаре 2
  • неблокирующий Экзамен (устный)
    Экзамен проводится дистанционно через Zoom. Технические требования: web-камера, микрофон, наушники / колонки, Zoom.
Промежуточная аттестация

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

  • 2021/2022 учебный год 2 модуль
    0.4 * Экзамен (письменный) 1 + 0.3 * Домашнее задание + 0.2 * Контрольная работа 1 + 0.1 * Работа на семинаре 1
  • 2021/2022 учебный год 4 модуль
    0.33 * 2021/2022 учебный год 2 модуль + 0.33 * Экзамен (письменный) 1 + 0.07 * Контрольная работа 1 + 0.07 * Работа на семинаре 1 + 0.2 * Домашнее задание
Список литературы

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

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

  • 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