• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

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

2022/2023
Учебный год
RUS
Обучение ведется на русском языке
9
Кредиты
Статус:
Курс обязательный
Когда читается:
1-й курс, 2, 4 модуль

Преподаватели

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

Аннотация

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

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

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

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

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

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

  • Алгоритмы: Классификация, сложность.
  • Теория чисел.
  • Рекурсивные алгоритмы.
  • Поиск и сортировка.
  • Структуры данных: стек, очередь, дек.
  • Динамическое программирование.
  • Куча
  • Задача RMQ и RSQ. Запросы на подотрезках массива.
  • Обработка событий.
  • Дерево поиска
  • Задача RMQ / RSQ. Дерево отрезков. Декартово дерево.
  • Представление сетей в компьютере.
  • Обход в глубину.
  • Задача нахождения кратчайших путей в графе.
  • Задача union - find.
  • Занача нахождения минимального островного дерева.
Элементы контроля

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

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

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

  • 2022/2023 учебный год 2 модуль
    0.3 * Домашние задание + 0.3 * Экзамен + 0.1 * Работа на семинарах + 0.3 * Контрольная работа
  • 2022/2023 учебный год 4 модуль
    0.3 * Контрольная работа + 0.3 * Экзамен + 0.1 * Работа на семинарах + 0.3 * Домашнее задание
Список литературы

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

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

  • Алгоритмы : построение и анализ, пер. с англ., 3-е изд., 1323 с., Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К., 2018

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

  • 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
  • Искусство программирования. Т. 3: Сортировка и поиск, Кнут, Д., 1978
  • Искусство программирования. Т.2: Получисленные алгоритмы, Кнут, Д. Э., 2012