Бакалавриат
2024/2025
Алгоритмы и структуры данных
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Кто читает:
Базовая кафедра Яндекс
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 2, 4 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для всех кампусов НИУ ВШЭ
Язык:
русский
Кредиты:
10
Контактные часы:
136
Программа дисциплины
Аннотация
"Курс дает базовые знания в области алгоритмов и структур данных. В явном виде они, может быть, не пригодятся, но очень важны для понимания работы библиотек, алгоритмов и языков программирования. Домашние задания по курсу закрепляют полученные знания и воспитывают хороший стиль написания кода, который позволяет избежать стандартных, но от этого ничуть не менее распространенных даже у опытных разработчиков, ошибок."
Цель освоения дисциплины
- Цель курса — обучить основам алгоритмического программирования, привить практические навыки решения задач с помощью базовых алгоритмов и структур данных, сформировать правильное представление о времени работы и эффективности различных алгоритмов и структур данных.
Планируемые результаты обучения
- Иметь представление о быстрых методах поиска k-й порядковой статистики
- Иметь представление о задачах LCA и RMQ и об связи между ними
- Иметь представление о кучах. Уметь использовать кучи для решения практических задач
- Иметь представление о персистентных структурах данных
- Иметь представление об основных алгоритмах сортировки. Понимать их преимущества и недостатки.
- Иметь представление об основных структурах данных
- Иметь представления о хэш-функциях и их свойствах. Уметь выбирать хэш-функцию для работы с заданным типом данных.
- Уметь интерпретировать практические задачи в терминах теории графах, решать эти задачи с использованием графовых алгоритмах
- Уметь находить кратчайшие пути в графах
- Уметь обходить графы в ширину и в глубину
- Уметь строить и эффективно использовать деревья поиска, выбирать правильную стратегию балансировки
- Уметь строить остовные деревья для графов.
- Уметь устранять коллизии при использовании хэш-таблиц
- Уметь эффективно реализовывать структуры данных в виде структур на языке С++
- Понимать устройство массивов переменного размера.
- Уметь оценивать сложность алгоритмов и объём дополнительной памяти.
Содержание учебной дисциплины
- Введение
- Введение в структуры данных
- Сортировки
- Кучи
- Хэширование
- Графы
- Деревья поиска
- Кратчайшие пути в графах
- LCA & RMQ
- Графы: продвинутые темы
Промежуточная аттестация
- 2024/2025 2nd module0.3 * Домашнее задание + 0.2 * Контрольная работа + 0.1 * Работа на семинаре + 0.4 * Экзамен
- 2024/2025 4th module0.3 * Домашнее задание + 0.2 * Контрольная работа + 0.1 * Работа на семинаре + 0.4 * Экзамен
Список литературы
Рекомендуемая основная литература
- Комбинаторика и теория графов : учеб. пособие, Кочетков, Ю. Ю., 2009
Рекомендуемая дополнительная литература
- Теория графов : учеб. пособие для втузов, Белов, В. В., 1976
- Язык С#. Базовый курс : учеб. пособие для вузов, Подбельский, В. В., 2013
- Язык С#. Решение задач : учеб. пособие для вузов, Подбельский, В. В., 2014