2020/2021





Структуры данных и алгоритмы
Лучший по критерию «Полезность курса для Вашей будущей карьеры»
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Дисциплина общефакультетского пула
Где читается:
Факультет математики
Когда читается:
3, 4 модуль
Преподаватели:
Чуйкин Николай Константинович
Язык:
русский
Кредиты:
7
Контактные часы:
12
Программа дисциплины
Аннотация
В рамках данной дисциплины студенты могут познакомиться с основными алгоритмами и структурами данными, а также с основными подходами построения алгоритмов. Данные знания могут быть полезны, как для развития алгоритмического мышления, так и для практического применения полученных знаний при разработке ПО. Дисциплина реализуется в формате смешанного обучения и представляет собой набор on-line курсов, реализованных на базе платформы Coursera для НИУ ВШЭ: https://www.coursera.org/specializations/data-structures-algorithms
Цель освоения дисциплины
- Научить студентов решать алгоритмические задачи используя различные подходы.
- Показать студентам различные методы построения и анализа алгоритмов.
- Предоставить возможность студенту отработать на практике полученные навыки.
Планируемые результаты обучения
- Умеет реализовывать простые алгоритмы на выбранном языке программирования. Знает подходы тестирования и отладки программы, в том числе стрессовое тестирование.
- Знает как оценивается асимптотическая сложность алгоритмов. Знает что такое O-нотация. Может оценить по алгоритму его асимптотическую сложность.
- Знает различные способы решения типовых задач (сортировки, динамическое программирование и т.д.)
- Знает и умеет использовать основные подходы для построения алгоритмов.
- Знает основные структуры данных, их достоинства и недостатки,
- Умеет определять по условию задачи какую структуру данных необходимо использовать с учётом заданных ограничений по памяти и по времени.
- Знает основные структуры данных, их достоинства и недостатки,
- Умеет решать задачи в рамках которых необходимо использовать графы.
- Знает основные определения и алгоритмы на графах.
- Умеет решать задачи в рамках которых необходимо использовать графы.
- Знает основные определения и алгоритмы на графах.
- Умеет решать задачи в которых необходимо использовать алгоритмы на строках.
- Знает основные подходы приближенного решения NP-полных задач.
- Умеет применять полученные знания при решении практических заданий.
Содержание учебной дисциплины
- Простые алгоритмы. Тестирование и отладка программ.Решение задачи о сумме максимальная попарного произведения. Написание тестов. Тестирование и отладка программ.
- Эффективность алгоритмов. Асимптотическая сложность.Простые алгоритмы. Эффективность алгоритмов. Вычислительное время. Асимптотическая сложность. Оценка сложности алгоритмов.
- «Жадные» алгоритмы. Задача о рюкзаке.«Жадные» алгоритмы. Применение «Жадных» алгоритмов при решении задач. Задача о рюкзаке.
- Метод «Разделяй и властвуй».Линейный поиск. Бинарный поиск. Метод «Разделяй и властвуй». Основная теорема о рекуррентных соотношениях. Сортировка выбором. Сортировка слиянием. Быстрая сортировка.
- Динамические массивы.Динамические массивы. Амортизационный анализ и его методы.
- Динамическое программирование.Динамическое программирование. Применение методов динамического программирования при решении задач. Задача о рюкзаке с повторами. Задача о рюкзаке без повторов.
- Базовые структуры данных.Массивы. Односвязные списки. Двусвязные списки. Стек. Очередь. Деревья. Обходы деревьев.
- Очереди с приоритетом.Простая реализация очереди с приоритетом. Двоичное дерево и базовые операции с ним. Сортировка кучей. Создание кучи.
- Системы непересекающихся множеств.Простая реализация системы непересекающихся множеств. Использование деревьев при построении системы непересекающихся множеств.
- Хеширование.Хеширование. Применения хеширования. Адресация памяти. Хеш-функции. Хеш- таблицы. Хеширование строк. Поиск в тексте по шаблону.
- Двоичное дерево поиска.Деревья поиска. Базовые операции. Балансировка. AVL дерево. Расширяющееся дерево.
- Графы.Графы. Орграфы. Основные определения. Представление графов. Связность. Направленный ациклический граф. Топологическая сортировка. Компонента сильной связности в орграфе.
- Пути в графе.Наикратчайший путь в графе. Поиск в ширину. Дерево кратчайших путей. Наикратчайший путь во взвешенном графе. Алгоритм Дейкстры. Алгориитм Форда-Беллмана. Циклы с отрицательным весом.
- Минимальное остовное дерево.Минимальное остовное дерево. Жадный алгоритм поиска минимального остовного дерева. Алгоритм Краскала. Алгоритм Прима.
- Строки. Суффиксные деревья.Строки. Задача о сопоставлении с образцом и её применения. Использование полного перебора для сопоставления с образцом. Суффиксные деревья.
- Преобразование Барроуза — Уилера. Суффиксные массивы.Преобразование Барроуза — Уилера. Применение преобразования Барроуза — Уилера для решения задачи сопоставления с образцом. Суффиксные массивы.
- Алгоритм Кнута — Морриса — Пратта.Сдвиг в строке. Префиксная функция. Вычисление префиксной функции. Алгоритм Кнута — Морриса — Пратта.
- Создание суффиксных массивов и суффиксных деревьев.Суффиксные массивы. Суффиксные массивы и суффиксные деревья. LCP массивы. Построение LCP массивов. Построение LCP массивов. Построение суффиксных массивов и деревьев по LCP массивам.
- Линейное программирование.Линейное программирование. Метод замены. Метод Гаусса. Симплекс метод.
- Транспортные сети.Транспортные сети. Максимальный поток. Алгоритм Форда-Фалкерсона. Алгоритм Эдмонда-Карпа.
- NP-полные задачи.Метод полного перебора. Задача поиска. Задача коммивояжёра. Задача о Гамильтоновом цикле. NP-полные задачи.
- Итоговый проектИтоговый проект позволяет применить все полученные знания на практике, и состоит из трёх прикладных задач.
Элементы контроля
- Онлайн курсТочная дата выгрузки оценок онлайн курса сообщается студентам преподавателем по электронной почте, задания выполненные после этой даты не учитываются в оценке. Выгрузка оценок производится примерно за три-пять дней до экзамена.
- Самостоятельная работа 1
- Самостоятельная работа 2
- Самостоятельная работа 3
- ЭкзаменДля выполнения предложены 5 задач по программированию. Каждая из задач относится к одному из пяти курсов специализации.
Промежуточная аттестация
- Промежуточная аттестация (4 модуль)0.4 * Онлайн курс + 0.06 * Самостоятельная работа 1 + 0.07 * Самостоятельная работа 2 + 0.07 * Самостоятельная работа 3 + 0.4 * Экзамен
Список литературы
Рекомендуемая основная литература
- Алгоритмы: построение и анализ, Кормен, Т., 2005
- Алгоритмы: построение и анализ, Кормен, Т., 2011
- Фундаментальные алгоритмы на С : ч. 1-5: анализ структуры данных, сортировка, поиск, алгоритмы на графах: пер. с англ., Седжвик, Р., 2003
Рекомендуемая дополнительная литература
- C/C++. Программирование на языке высокого уровня : учебник для вузов, Павловская, Т. А., 2003