Экскурсии в офис Mail.ru. Успейте записаться!

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

Осень 2019

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

В результате освоения дисциплины обучающиеся должны знать:

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

Подробнее

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

Контроль знаний по курсу проводится в балльно-рейтинговой форме с 2 тематическими рубежными контролями и экзаменом. На практических занятиях студентам раздаются задачи, обсуждаются детали реализации алгоритмов, выделяется время для решения задач и выполняется проверка задач семинаристом. Перед тем как сдать задачу семинаристу студент отправляет решение задачи в тестирующую систему.

Подробнее

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

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

Закончил ФизТех, работаю в 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: Введение в курс. Массивы.  

Анализ алгоритмов и понятие вычислительной сложности задачи. O-нотация.
Вычисление n-ого числа Фибоначчи.
Проверка числа на простоту.
Быстрое возведение числа в целую степень (за log(n)).
Массивы. Линейный поиск. Бинарный поиск.
Структура данных «Динамический массив». Амортизированное время добавления элемента.
Однонаправленные, двунаправленные списки.
Структуры данных «Стек», «Очередь», «Дек».
Динамические алгоритмы. Жадные алгоритмы.
4 часа

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

Решение задач: Простые алгоритмы с целыми числами. Использование бинарного поиска. Реализация структур данных «Стек», «Очередь», «Дек». Использование стека.
Домашнее задание №1: ДЗ №1
.
4 часа + 2 часа СР

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

Двоичная куча.
Структура данных «Очередь с приоритетом».
Квадратичные сортировки.
Анализ алгоритмов сортировки по количеству сравнений.
Недостижимость линейной оценки времени для алгоритмов сортировок, основанных на сравнениях элементов.
Пирамидальная сортировка (Heap sort).
Сортировка слиянием.
Слияние упорядоченных списков.
Быстрая сортировка Хоара (Quick sort).
Стратегии выбора разделяющего элемента быстрой сортировки.
Порядковые статистики.
Сортировка подсчетом, карманная сортировка. Устойчивость сортировки.
Поразрядная сортировка.
TimSort.
Сравнение сортировок.
4 часа + 3 часа СР

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

Решение задач: Использование СД «Куча» как очереди с приоритетом. Использование сортировок.
4 часа + 2 часа СР

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

Решение задач: Использование сортировки слиянием. Поиск порядковых статистик. Вариации поразрядных сортировок.
4 часа + 2 часа СР

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

Проверка знаний по темам «Элементарные алгоритмы и структуры данных, сортировки».
4 часа + 2 часа СР

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

Хеш-функции. Хеш-функции для строк.
Хеш-таблица. Стоимость добавления элементов.
Разрешение коллизий методом цепочек.
Разрешение коллизий методом открытой адресации. Двойное хеширование.
 
4 часа + 3 часа СР

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

Решение задач: Реализация хеш-таблицы методом открытой адресации.
Домашнее задание №2: ДЗ №2
ДЗ №2
4 часа + 2 часа СР

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

Построение дерева поиска наивным алгоритмом. Декартовы деревья. 
Реализация АВЛ-дерева.
4 часа + 3 часа СР

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

Построение дерева поиска наивным алгоритмом. Сравнение наивного дерева поиска и декартового дерева.
4 часа + 2 часа СР

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

Решение задач: Коды Хаффмана.
Домашнее задание №3: ДЗ №6
4 часа + 3 часа СР

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

Проверка знаний по темам «Хеш-таблицы» и «Деревья».
4 часа + 3 часа СР

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

Терминология. 
Обходы графов.
Поиск циклов.
Поиск компонент связности.
Топологическая сортировка.
4 часа + 3 часа СР

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

Решение задач: Реализация графа, обходы графов.
Количество кратчайших путей.
Топологическая сортировка.
Домашнее задание №4: ДЗ №3
ДЗ №3
Домашнее задание №5: ДЗ №7
4 часа + 2 часа СР

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

Поиск кратчайших путей в графе. Постановка задач.
Алгоритм Дейкстры.
Алгоритм Форда-Беллмана.
Алгоритм A*.
Задача нахождения минимального остовного дерева.
Алгоритм Прима.
Алгоритм Крускала.
Системы непересекающихся множеств.
Задача коммивояжера.
4 часа + 3 часа СР

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

Решение задач: Алгоритм Дейкстры. Реализация решения восьминашек.
Алгоритм A*. Пятнашки.
Домашнее задание №6: ДЗ №8
4 часа + 2 часа СР

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

Решение задач: Алгоритм Крускала. Реализация системы непересекающихся множеств. Приближенное решение задачи коммивояжера.
Домашнее задание №7: ДЗ №9
4 часа + 2 часа СР

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

Проверка знаний по теме «Графы».
4 часа + 3 часа СР