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

2024/2025

Статус: Маго-лего

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

Когда читается: 3, 4 модуль

Охват аудитории: для своего кампуса

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

Язык: русский

Кредиты: 6

Полная версия программы учебной дисциплины Задать вопрос

Аннотация

В рамках курса "Алгоритмы и структуры данных" студенты познакомятся с основами алгоритмов, их классификацией и оценкой сложности, а также освоят ключевые структуры данных, включая массивы, стеки, множества и деревья. Особое внимание уделяется особенностям работы алгоритмов на реальных компьютерах: управлению кэшем, векторным инструкциям, обращению к диску и использованию 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). Алгоритмы хэширования
Хэш-таблицы
Разбор конкурса по хэш-таблицам

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

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

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

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

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

Авторы

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

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