Data Structures and Algorithms

2019/2020

Category 'Best Course for Career Development'

Category 'Best Course for Broadening Horizons and Diversity of Knowledge and Skills'

Type: Optional course (faculty)

Delivered by: Big Data and Information Retrieval School

Where: Faculty of Mathematics

When: 3, 4 module

Instructors: Nikolay Chuykin

Language: English

ECTS credits: 7

Contact hours: 10

Full Syllabus

Abstract

В рамках данной дисциплины студенты могут познакомиться с основными алгоритмами и структурами данными, а также с основными подходами построения алгоритмов. Данные знания могут быть полезны, как для развития алгоритмического мышления, так и для практического применения полученных знаний при разработке ПО. Дисциплина реализуется в формате смешанного обучения и представляет собой набор on-line курсов, реализованных на базе платформы Coursera для НИУ ВШЭ: https://www.coursera.org/specializations/data-structures-algorithms

Learning Objectives

Научить студентов решать алгоритмические задачи используя различные подходы.
Показать студентам различные методы построения и анализа алгоритмов.
Предоставить возможность студенту отработать на практике полученные навыки.

Expected Learning Outcomes

Умеет реализовывать простые алгоритмы на выбранном языке программирования. Знает подходы тестирования и отладки программы, в том числе стрессовое тестирование.
Знает как оценивается асимптотическая сложность алгоритмов. Знает что такое O-нотация. Может оценить по алгоритму его асимптотическую сложность.
Знает основные определения и алгоритмы на графах.
Знает основные подходы приближенного решения NP-полных задач.
Знает основные структуры данных, их достоинства и недостатки,
Умеет решать задачи в рамках которых необходимо использовать графы.
Знает и умеет использовать основные подходы для построения алгоритмов.
Знает основные определения и алгоритмы на графах.
Знает основные структуры данных, их достоинства и недостатки,
Знает различные способы решения типовых задач (сортировки, динамическое программирование и т.д.)
Умеет определять по условию задачи какую структуру данных необходимо использовать с учётом заданных ограничений по памяти и по времени.
Умеет применять полученные знания при решении практических заданий.
Умеет решать задачи в которых необходимо использовать алгоритмы на строках.
Умеет решать задачи в рамках которых необходимо использовать графы.

Course Contents

Простые алгоритмы. Тестирование и отладка программ.
Решение задачи о сумме максимальная попарного произведения. Написание тестов. Тестирование и отладка программ.
Эффективность алгоритмов. Асимптотическая сложность.
Простые алгоритмы. Эффективность алгоритмов. Вычислительное время. Асимптотическая сложность. Оценка сложности алгоритмов.
«Жадные» алгоритмы. Задача о рюкзаке.
«Жадные» алгоритмы. Применение «Жадных» алгоритмов при решении задач. Задача о рюкзаке.
Метод «Разделяй и властвуй».
Линейный поиск. Бинарный поиск. Метод «Разделяй и властвуй». Основная теорема о рекуррентных соотношениях. Сортировка выбором. Сортировка слиянием. Быстрая сортировка.
Динамические массивы.
Динамические массивы. Амортизационный анализ и его методы.
Динамическое программирование.
Динамическое программирование. Применение методов динамического программирования при решении задач. Задача о рюкзаке с повторами. Задача о рюкзаке без повторов.
Базовые структуры данных.
Массивы. Односвязные списки. Двусвязные списки. Стек. Очередь. Деревья. Обходы деревьев.
Очереди с приоритетом.
Простая реализация очереди с приоритетом. Двоичное дерево и базовые операции с ним. Сортировка кучей. Создание кучи.
Системы непересекающихся множеств.
Простая реализация системы непересекающихся множеств. Использование деревьев при построении системы непересекающихся множеств.
Хеширование.
Хеширование. Применения хеширования. Адресация памяти. Хеш-функции. Хеш- таблицы. Хеширование строк. Поиск в тексте по шаблону.
Двоичное дерево поиска.
Деревья поиска. Базовые операции. Балансировка. AVL дерево. Расширяющееся дерево.
Графы.
Графы. Орграфы. Основные определения. Представление графов. Связность. Направленный ациклический граф. Топологическая сортировка. Компонента сильной связности в орграфе.
Пути в графе.
Наикратчайший путь в графе. Поиск в ширину. Дерево кратчайших путей. Наикратчайший путь во взвешенном графе. Алгоритм Дейкстры. Алгориитм Форда-Беллмана. Циклы с отрицательным весом.
Минимальное остовное дерево.
Минимальное остовное дерево. Жадный алгоритм поиска минимального остовного дерева. Алгоритм Краскала. Алгоритм Прима.
Строки. Суффиксные деревья.
Строки. Задача о сопоставлении с образцом и её применения. Использование полного перебора для сопоставления с образцом. Суффиксные деревья.
Преобразование Барроуза — Уилера. Суффиксные массивы.
Преобразование Барроуза — Уилера. Применение преобразования Барроуза — Уилера для решения задачи сопоставления с образцом. Суффиксные массивы.
Алгоритм Кнута — Морриса — Пратта.
Сдвиг в строке. Префиксная функция. Вычисление префиксной функции. Алгоритм Кнута — Морриса — Пратта.
Создание суффиксных массивов и суффиксных деревьев.
Суффиксные массивы. Суффиксные массивы и суффиксные деревья. LCP массивы. Построение LCP массивов. Построение LCP массивов. Построение суффиксных массивов и деревьев по LCP массивам.
Линейное программирование.
Линейное программирование. Метод замены. Метод Гаусса. Симплекс метод.
Транспортные сети.
Транспортные сети. Максимальный поток. Алгоритм Форда-Фалкерсона. Алгоритм Эдмонда-Карпа.
NP-полные задачи.
Метод полного перебора. Задача поиска. Задача коммивояжёра. Задача о Гамильтоновом цикле. NP-полные задачи.
Итоговый проект
Итоговый проект позволяет применить все полученные знания на практике, и состоит из трёх прикладных задач.

Assessment Elements

Онлайн курс
Точная дата выгрузки оценок онлайн курса сообщается студентам преподавателем по электронной почте, задания выполненные после этой даты не учитываются в оценке. Выгрузка оценок производится примерно за три-пять дней до экзамена.
Самостоятельная работа 1
Самостоятельная работа 2
Самостоятельная работа 3
Экзамен
Для выполнения предложены 5 задач по программированию. Каждая из задач относится к одному из пяти курсов специализации.

Interim Assessment

Interim assessment (4 module)
0.3 * Онлайн курс + 0.1 * Самостоятельная работа 1 + 0.1 * Самостоятельная работа 2 + 0.1 * Самостоятельная работа 3 + 0.4 * Экзамен

Bibliography

Recommended Core Bibliography

Алгоритмы: построение и анализ, Кормен, Т., 2005
Алгоритмы: построение и анализ, Кормен, Т., 2011
Фундаментальные алгоритмы на С : ч. 1-5: анализ структуры данных, сортировка, поиск, алгоритмы на графах: пер. с англ., Седжвик, Р., 2003

Recommended Additional Bibliography

C/C++. Программирование на языке высокого уровня : учебник для вузов, Павловская, Т. А., 2003

Course Syllabus