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

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

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



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



                  • Реализовывать алгоритмы и их комбинации на языке C++ для решения поставленных задач;
                    • Находить применения классическим алгоритмам в задачах, возникающих в процессе разработки ПО;
                    • Владеть:



                      • Методами отладки кода на языке C++;
                        • Навыками оценки сложности алгоритмов;

Подробнее

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

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

Подробнее

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

Степан Мацкевич Степан Мацкевич

Руководитель одной из подгрупп бэкенда в Яндекс.Такси. Был руководитель группы извлечения онтоло...


Подробнее

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

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

Яков Любимов Яков Любимов

Закончил МГУ имени Ломоносова факультет вычислительной математики и кибернетики (ВМиК). Уже на тр...


Подробнее

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

Закончил МГТУ им.Баумана в 2009 году, кафедра РК9. С 2010 года в Mail.ru Group. В настоящее вре...


Подробнее

Литература

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).
Стратегии выбора разделяющего элемента быстрой сортировки.
Порядковые статистики.
Сортировка подсчетом, карманная сортировка. Устойчивость сортировки.
Поразрядная сортировка.
4 часа + 3 часа СР

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

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

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

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

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

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

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

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

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

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

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

Деревья поиска. Методы вставки, удаления, поиска элементов. Декартовы деревья. Сбалансированные деревья. АВЛ деревья. Сплей-деревья. Структура данных «Ассоциативный массив».
4 часа + 3 часа СР

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

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

Семинар №6: АВЛ и Сплей-деревья   + ДЗ №6

Решение задач: Использование АВЛ-дерева. Использование Сплей-деревьев.
Домашнее задание №6: ДЗ №6
4 часа + 3 часа СР

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

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

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

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

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

Решение задач: Реализация графа, обходы графов.
Домашнее задание №3: ДЗ №3
ДЗ №3
Домашнее задание №9: ДЗ №7
4 часа + 2 часа СР

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

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

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

Решение задач: Алгоритм Дейкстры.
Домашнее задание №7: ДЗ №8
4 часа + 2 часа СР

Семинар №9: Остовные деревья   + ДЗ №8

Решение задач: Алгоритм Крускала.
Домашнее задание №8: ДЗ №9
4 часа + 2 часа СР

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

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