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

2025/2026

Учебный год

RUS

Обучение ведется на русском языке

6

Кредиты

Кто читает:

Департамент прикладной математики

Статус:

Курс обязательный

Когда читается:

1-й курс, 3, 4 модуль

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

Быстров Иван Дмитриевич

Петряйкин Федор Алексеевич

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

Аннотация

В рамках курса "Алгоритмы и структуры данных" студенты познакомятся с основами алгоритмов, их классификацией и оценкой сложности, а также освоят ключевые структуры данных, включая массивы, стеки, множества и деревья. Особое внимание уделяется особенностям работы алгоритмов на реальных компьютерах: управлению кэшем, векторным инструкциям, обращению к диску и использованию GPU. На курсе будут изучены алгоритмы сортировки, поиска, сжатия данных и хэширования, а также методы обработки текстов, такие как алгоритмы Ахо-Корасик и Кнут-Моррис-Пратт. Практические задания включают разработку и профилировку собственных реализаций алгоритмов, оптимизацию кода, построение хэш-таблиц и реализацию алгоритмов работы с текстами, JSON и XML. Отдельные занятия посвящены реализации алгоритмов сжатия, параллельной обработке данных и задачам машинного обучения, таким как KNN. Для закрепления знаний проводятся практические задания, разборы и конкурсы. Контроль знаний реализован через домашние задания, проведение конкурсов и экзамена, предполагающего защиту студентами своих решений.

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

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

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

• Знать базовые концепции языка c++, основы работы со строками, контейнерами stl, итераторами, std::span, string_view, iostream, std::format, fstream, unique_ptr.
• Знать общую теорию алгоритмов, принципы оценки сложности, основы рекурсии, конечные автоматы, абстракции структур данных.
• Знать основы работы кэша, векторных инструкций, обращения к диску, пропускной способности шины, кратко — основы GPU.
• Уметь анализировать и объяснять сложность алгоритма; понимать принципы представления чисел с плавающей точкой.
• Знать подходы к разработке и оптимизации деревьев решений, различия между "наивной" и "качественной" реализациями алгоритмов.
• Знать виды сортировок, их реализацию и сложности; принципы нахождения медианы в потоковых данных;
• Знать структуры данных, поддерживающие сортированность (куча), агрегирующие структуры (skip list, дерево отрезков);
• Знать деревья поиска (b-деревья, красно-черные деревья — кратко)
• Знать префиксные деревья
• Знать разбор по конечному автомату. Алгоритмы ахо-карасик и кнут-морис-прата
• Знать грамматики и рекурсивный спуск (обзорно)
• Знать основные алгоритмы и подходы, использованные в решениях
• Знать принципы работы с префиксными деревьями и конечными автоматами
• Знать основы генерации кода разбора грамматики с помощью lexer и bison
• Уметь аргументированно защищать свои решения, демонстрируя понимание алгоритмов и структур данных
• Знать алгоритмы сжатия без потерь: varbyte, simple14, pfor, код хаффмана, deflate, сжатие со словарем
• Знать принципы работы алгоритмов сжатия и их применение в различных контекстах
• Знать алгоритмы сжатия с потерями и их отличия от алгоритмов без потерь
• Знать сжатие чисел с плавающей точкой (квантование)
• Знать алгоритмы хэширования: sha, md5, murmur. Распределение хэшей и коллизии хэш-функций
• Знать краткие сведения о криптографических алгоритмах
• Знать векторные инструкции и их применение в алгоритмах сжатия и хэширования
• Знать устройство хэш-таблиц: бакеты, хэш-функции и методы разрешения коллизий
• Знать принципы работы методов разрешения коллизий и их влияние на производительность хэш-таблиц
• Уметь аргументированно защищать свои решения

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

• Введение в С++ (1)
• Введение в алгоритмы (1). Теория алгоритмов и структур данных
• Введение в алгоритмы (2)
• Сортировка, поиск, отображение
• Задача разбора текста
• Разбор конкурса по задаче разбора текста
• Сжатие и хэширование (1). Алгоритмы сжатия без потерь
• Сжатие и хэширование (2). Алгоритмы хэширования
• Хэш-таблицы
• Разбор конкурса по хэш-таблицам

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

• Конкурсы
• Экзамен
  Экзамен представляет собой защиту студентами решений (то есть развернутого обоснования) домашних заданий и конкурсов. Отдельно баллы за экзамен не присваиваются, но подтверждаются баллы за сданные домашние задания и конкурсы, либо не подтверждаются в зависимости от успешности защиты. Защита - это обязательное условие для присвоения баллов.
• Домашние задания

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

• 2025/2026 4th module
  Формула расчета итоговой оценки: SUM_5_ДОМАШНИЙ ЗАДАНИЙ + SUM_3_КОНКУРСОВ

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

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

• Алгоритмические трюки для программистов, Уоррен-мл., Г., 2014
• Алгоритмы : разработка и применение, Клейнберг, Дж., 2018
• Грокаем алгоритмы : иллюстрированное пособие для программистов и любопытствующих, Бхаргава, А., 2023
• Совершенный алгоритм : графовые алгоритмы и структуры данных, Рафгарден, Т., 2019
• Совершенный алгоритм. Основы - 978-5-4461-0907-4 - Рафгарден Тим - 2020 - Санкт-Петербург: Питер - https://ibooks.ru/bookshelf/365286 - 365286 - iBOOKS

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

• Совершенный алгоритм. Основы : пер. с англ., Рафгарден, Т., 2020

Авторы

• Смольникова Юлия Валерьевна
• Сластников Сергей Александрович
• Князева Ирина Васильевна