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

Осень 2021

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

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

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

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

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

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

Закончил МГТУ им.Баумана в 2009 году.
Работаю руководителем группы разработки в Mail.ru Group.

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

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

Литература

1. Алгоритмы: построение и анализ, 2-е издание. : Пер. с англ. –М.: Издательский дом «Вильямс» / Кормэн Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. / 2005 г.
ISBN ISBN 5-8459-0857-4 (рус.)
2. Алгоритмы и структуры данных. — М.: Мир / Вирт Н. / 1989 г.
3. Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск. — М.: Диасофт / Седжвик Р. / 2003 г.
4. http://e-maxx.ru/algo/
http://e-maxx.ru/algo/
Показать все

Программа

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

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

4 ак. ч.

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

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

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

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

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

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

Семинар №3: Динамическое программирование и жадные алгоритмы.  

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

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

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

Лекция №3: Хеш-функции. Хеш-таблицы. Деревья общего вида.  

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

РАСПИСАНИЕ

Полное расписание