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

Весна 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: Введение в курс. Массивы.  

Анализ алгоритмов и понятие вычислительной сложности задачи. 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 ак. ч. СР

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

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

РАСПИСАНИЕ

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

Посмотрите, чему еще учатся наши студенты

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

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

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

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