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

Algorithms and Data Structures

2023/2024
Academic Year
RUS
Instruction in Russian
9
ECTS credits
Course type:
Elective course
When:
1 year, 2, 4 module

Instructors


Галицкий Борис Васильевич


Golovin, Leonid


Климовицкий Роман Григорьевич


Мамаев Алексей Александрович


Мамай Игорь Борисович


Manuylenko, Nikita


Панькова Марина Геннадьевна


Петров Андрей Иванович


Плотников Алексей Валерьевич


Trubachev, Ivan


Фолунин Владимир Александрович


Широкин Константин Павлович

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

Аннотация

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

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

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

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

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

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

  • Рекурсивные алгоритмы и рекуррентные соотношения
  • Асимптотический анализ
  • Динамическое программирование
  • Сортировки
  • Разделяй и властвуй
  • Алгоритмы на графах
  • Структуры данных
  • Жадные алгоритмы
  • Хэш таблицы
  • Деревья
Элементы контроля

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

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

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

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

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

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

  • 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

Авторы

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