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

2024/2025

Учебный год

RUS

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

5

Кредиты

Кто читает:

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

Статус:

Курс по выбору

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

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

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

Мамай Игорь Борисович

Серянин Александр Константинович

Терлыч Никита Андреевич

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

Аннотация

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

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

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

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

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

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

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

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

• Коллоквиум
  Между 1 и 2 модулем будет проведен Коллоквиум. Коллоквиум сдается устно и состоит из сдачи теоретических вопросов и решения алгоритмических задач. Оценивается по 10-бальной шкале.
• Экз
  Экзамен будем устно принимать по билетам
• ПКР
  Во 2 модуле будет проведена письменная Контрольная Работа. Контрольная Работа сдается письменно и состоит в решении алгоритмических задач и задач на знание пройденного теоретического материала.
• Работа на семинаре
• Контест
  количество контестов может скорректироваться в зависимости от успеваемости группы

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

• 2024/2025 2nd module
  Накоп = 0.25 * Коллоквиум + 0.25 КР + 0.4 * (Среднее всех домашних заданий) + 0.1 * Работа на семинаре. Если студент не согласен на оценку автоматом, то сдается экзамен и итог вычисляется по формуле 0.5 * Экзамен + 0.5 * Накоп.

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

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

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

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

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

Авторы

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