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

Course type:: Elective course

When:: 1 year, 2, 4 module

Instructors

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

Golovin, Leonid

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

Manuylenko, Nikita

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

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

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 * Экзамен

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

Авторы

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

Bachelor’s Programme 'Applied Mathematics and Information Science'

Algorithms and Data Structures

Instructors

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