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

Бакалавриат 2024/2025

Статус: Курс по выбору (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

Где читается: Факультет компьютерных наук

Когда читается: 1-й курс, 2, 4 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для всех кампусов НИУ ВШЭ

Преподаватели: Акулин Максим Владимирович, Галицкий Борис Васильевич, Головин Леонид Олегович, Густокашин Михаил Сергеевич, Карпов Владимир Евгеньевич, Мамай Игорь Борисович, Мануйленко Никита Сергеевич, Осадчий Александр Ильич, Панькова Марина Геннадьевна, Петров Андрей Иванович, Сафонов Иван Андреевич, Темирханов Азиз Арсенович, Фолунин Владимир Александрович, Широкин Константин Павлович

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

Кредиты: 10

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

Аннотация

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

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

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

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

Иметь представление о быстрых методах поиска 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 * Экзамен

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

Авторы

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

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