Algorithms and Data Structures

2024/2025

Academic Year

RUS

Instruction in Russian

10

ECTS credits

Category 'Best Course for Career Development'

Category 'Best Course for Broadening Horizons and Diversity of Knowledge and Skills'

Delivered at:

Joint Department with Yandex (Big Data and Information Retrieval School)

Course type:

Elective course

When:

1 year, 2, 4 module

Instructors

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

Брызгалов Остап Вячеславович

Galitskii, Boris

Golovin, Leonid

Gustokashin, Mikhail

Иванов Максим Юрьевич

Крапивин Богдан Александрович

Kurenkov, Vladimir

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

Manuylenko, Nikita

Осадчий Александр Ильич

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

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

Temirkhanov, Aziz

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

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

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

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

Аннотация

"Курс дает базовые знания в области алгоритмов и структур данных. В явном виде они, может быть, не пригодятся, но очень важны для понимания работы библиотек, алгоритмов и языков программирования. Домашние задания по курсу закрепляют полученные знания и воспитывают хороший стиль написания кода, который позволяет избежать стандартных, но от этого ничуть не менее распространенных даже у опытных разработчиков, ошибок."

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

• Цель курса — обучить основам алгоритмического программирования, привить практические навыки решения задач с помощью базовых алгоритмов и структур данных, сформировать правильное представление о времени работы и эффективности различных алгоритмов и структур данных.

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

• Иметь представление о быстрых методах поиска k-й порядковой статистики
• Иметь представление о задачах LCA и RMQ и об связи между ними
• Иметь представление о кучах. Уметь использовать кучи для решения практических задач
• Иметь представление о персистентных структурах данных
• Иметь представление об основных алгоритмах сортировки. Понимать их преимущества и недостатки.
• Иметь представление об основных структурах данных
• Иметь представления о хэш-функциях и их свойствах. Уметь выбирать хэш-функцию для работы с заданным типом данных.
• Уметь интерпретировать практические задачи в терминах теории графах, решать эти задачи с использованием графовых алгоритмах
• Уметь находить кратчайшие пути в графах
• Уметь обходить графы в ширину и в глубину
• Уметь строить и эффективно использовать деревья поиска, выбирать правильную стратегию балансировки
• Уметь строить остовные деревья для графов.
• Уметь устранять коллизии при использовании хэш-таблиц
• Уметь эффективно реализовывать структуры данных в виде структур на языке С++
• Понимать устройство массивов переменного размера.
• Уметь оценивать сложность алгоритмов и объём дополнительной памяти.

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

• Введение
• Введение в структуры данных
• Сортировки
• Кучи
• Хэширование
• Графы
• Деревья поиска
• Кратчайшие пути в графах
• LCA & RMQ
• Графы: продвинутые темы

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

• Работа на семинаре
• Домашнее задание
• Контрольная работа
• Экзамен

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

• 2024/2025 2nd module
  0.3 * Домашнее задание + 0.2 * Контрольная работа + 0.1 * Работа на семинаре + 0.4 * Экзамен
• 2024/2025 4th module
  0.3 * Домашнее задание + 0.2 * Контрольная работа + 0.1 * Работа на семинаре + 0.4 * Экзамен

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

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

• Комбинаторика и теория графов : учеб. пособие, Кочетков, Ю. Ю., 2009

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

• Теория графов : учеб. пособие для втузов, Белов, В. В., 1976
• Язык С#. Базовый курс : учеб. пособие для вузов, Подбельский, В. В., 2013
• Язык С#. Решение задач : учеб. пособие для вузов, Подбельский, В. В., 2014

Авторы

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