Весна 2023

Алгоритмы и структуры данных (ML-23)

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

Наверх

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

Рассказывается о базовых структурах данных: стек, очередь, списки, куча. Также в курс включены различные деревья поиска и хеш-таблицы. Дается представление о жадных алгоритмах и динамическом программировании. Отдельно в курсе рассматриваются алгоритмы на графах. Курс дает представление о том, как оценивать эффективность алгоритмов, все алгоритмы курса оцениваются по времени работы и по количеству используемой дополнительной памяти.
Подробнее
Чему научитесь

В результате освоения дисциплины обучающиеся должны знать:
  • Основные структуры данных: массив, стек, очередь, дек, очередь с приоритетом;
  • Алгоритмы сортировки: квадратичные, пирамидальную, сортировку слиянием, QuickSort, поразрядную;
  • Алгоритмы поиска порядковых статистик;
  • Методы оптимизации в задачах динамического программирования;
  • Жадные алгоритмы;
  • Структуры данных для создания эффективных контейнеров: хеш-таблицы, двоичные деревья поиска, АВЛ-деревья, декартовы деревья;
  • Алгоритм кодирования Хаффмана для сжатия данных;
Уметь:
  • Реализовывать алгоритмы и их комбинации на языке C++ для решения поставленных задач;
  • Находить применения классическим алгоритмам в задачах, возникающих в процессе разработки ПО;
Владеть:
  • Методами отладки кода на языке C++;
  • Навыками оценки сложности алгоритмов;
  • Алгоритмы на графах: обходы в глубину и ширину, поиск циклов, топологическую сортировку, поиск кратчайших путей.
Подробнее

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

Алексей Крымов Алексей Крымов

Выпускник МГТУ им. Н.Э. Баумана.
Руководитель группы разработки в Mail.ru

Дмитрий Корепанов Дмитрий Корепанов

Закончил ФизТех, работаю в ABBYY.

Дмитрий Глушенков Дмитрий Глушенков

Закончил МАИ, работаю ведущим программистом в проекте Поиск VK.

Программа

Занятие Часы в ауд. + сам. работа

Лекция №1: Введение в курс. Массивы.  

4 ак. ч.

Семинар №1: Элементарные алгоритмы и структуры данных  
+ ДЗ №1

4 ак. ч. + 2 ак. ч. СР

Лекция №2: Двоичная куча. Сортировки  

4 ак. ч.

Семинар №2: Работа с массивами и базовыми структурами данных.  

4 ак. ч. + 2 ак. ч. СР

Семинар №3: Порядковые статистики. Сортировка подсчетом. Устойчивость сортировок.  

4 ак. ч.

Контрольное занятие №1: Рубежный контроль №1. Проверка знаний  

4 ак. ч. + 2 ак. ч. СР

Лекция №3: Хеш-функции. Хеш-таблицы.  

4 ак. ч.

Семинар №4: Хеш-таблицы  
+ ДЗ №2

4 ак. ч. + 2 ак. ч. СР

Лекция №4: Деревья поиска  

4 ак. ч.

Семинар №5: Деревья поиска  

4 ак. ч.

Семинар №6: Коды Хаффмана  
+ ДЗ №3

4 ак. ч. + 2 ак. ч. СР

Контрольное занятие №2: Рубежный контроль №2. Проверка знаний  

4 ак. ч. + 2 ак. ч. СР

Лекция №5: Графы  

4 ак. ч.

Семинар №7: Графы. Обходы  
+ ДЗ №4 + ДЗ №5

4 ак. ч.

Семинар №8: Кратчайшие пути  
+ ДЗ №6

4 ак. ч. + 2 ак. ч. СР

Лекция №6: Кратчайшие пути. Остовные деревья  

4 ак. ч.

Семинар №9: Остовные деревья. Задача коммивояжера  
+ ДЗ №7

4 ак. ч. + 2 ак. ч. СР

Контрольное занятие №3: Итоговое занятие  

4 ак. ч. + 2 ак. ч. СР

Итого 18 занятий, 7 ДЗ

72 ак. ч. + 18 ак. ч. СР

Чему еще учатся студенты

Первый семестр

Второй семестр

Третий семестр