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

Весна 2020

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

Описание
На курсе изучаем базовые алгоритмы и структуры данных, необходимые программистам для качественного решения ежедневных задач. Исследуем базовые алгоритмы для работы с массивами, сортировки, порядковые статистики. Разбираемся в базовых структурах данных: стек, очередь, списки, куча. Затрагиваем различные деревья поиска и хеш-таблицы, формируем представление о жадных алгоритмах и динамическом программировании. Отдельно рассматриваем алгоритмы на графах. 
Курс состоит из 16 занятий, включает рубежные контроли и домашние задания.
 
Подробнее
Чему научитесь
Сможете реализовывать алгоритмы и их комбинации на языке 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 часа СР

РАСПИСАНИЕ

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