Algorithms and Data Structures

2024/2025

Academic Year

RUS

Instruction in Russian

10

ECTS credits

Delivered at:

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

Course type:

Elective course

When:

1 year, 2, 4 module

Instructors

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

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

Safonov, Ivan

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

Авторы

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