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

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

Лучший по критерию «Полезность курса для Вашей будущей карьеры»

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

Статус: Курс по выбору (Программная инженерия)

Направление: 09.03.04. Программная инженерия

Кто читает: Базовая кафедра «Системное программирование» Института системного программирования им. В.П. Иванникова РАН (ИСП РАН)

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

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

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

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

Преподаватели: Мамай Игорь Борисович, Серянин Александр Константинович

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

Кредиты: 4

Контактные часы: 56

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

Аннотация

Учебный курс «Алгоритмы и структуры данных» предлагается студентам бакалавриата по направлению «Программная инженерия» на факультете компьютерных наук НИУ ВШЭ. Курс относится к обязательным предметам. В рамках данного курса студенты изучат основные алгоритмы сортировок, теории графов и комбинаторики, теории кодирования и сжатия, динамическое программирование. В курсе студент освоит основные структуры данных и алгоритмы, которые послужат фундаментом для всех дальнейших знаний в области компьютерных наук и программной инженерии.

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

• Дисциплина формирует понимание устройства основных алгоритмов и структур данных, необходимое при разработке программного обеспечения. Дает навыки правильного выбора подходящих по различным параметрам структур данных при работе в промышленном программировании.

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

• Знание основных структур данных.
• Умение оценивать асимптотику работы
• Умение подбирать подходящий алгоритм или структуру данных под конкретную задачу
• Умение реализовывать на языке C++ изученные алгоритмы и структуры данных.
• Умение проводить сравнительный анализ различных алгоритмов, решающих одинаковую задачу, в зависимости от размера и структуры входных данных.

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

• Введение
• Концепция абстрактной структуры данных
• Асимптотический анализ алгоритма. Подходы к проектированию алгоритмов-1
• Разделяй и властвуй-2
• Детерминированные vs стохастические алгоритмы
• Нелинейные алгоритмы сортировки
• Линейные алгоритмы сортировки
• Бинарные деревья-1
• Бинарные деревья-2
• Бинарные деревья-3
• Бинарные деревья-4
• Система непересекающихся множеств. Отношение эквивалентности между объектами

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

• КДЗ
  Будет дана работа по анализу сортировок. Студентам нужно будет сдать отчет и код на языке C++.
• Экз
  Экзамен будем устно принимать по билетам
• Контест
  количество контестов может скорректироваться в зависимости от успеваемости группы

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

• 2023/2024 2nd module
  Накоп = 0.2 * КДЗ + 0.8 * (Среднее всех домашних заданий) Если накоп меньше 4 после округления, то сдается экзамен и итог вычисляется по формуле 0.5 * Экзамен + 0.5 * Накоп. Иначе ставится экзамен автоматом.

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

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

• Алгоритмы : построение и анализ, 2-е изд., 1290 с., Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К., 2012
• Алгоритмы : построение и анализ, пер. с англ., 3-е изд., 1323 с., Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К., 2018
• Алгоритмы. Построение и анализ : пер. с англ., Кормен Т., Лейзерсон Ч., 2012
• Искусство программирования. Т.1: Основные алгоритмы : учеб. пособие: пер. с англ., Кнут Д.Э., Козаченко Ю.В., 2012
• Искусство программирования. Т.1: Основные алгоритмы, Кнут, Д. Э., 2005
• Искусство программирования. Т.1: Основные алгоритмы, Кнут, Д. Э., 2011

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

• Алгоритмы : построение и анализ : пер. с англ., Кормен, Т., 2000
• Искусство программирования. Т. 1: Основные алгоритмы, Кнут, Д., 1976

Авторы

• Лебедев Сергей Аркадьевич
• Буцкая Евгения Александровна