• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
2020/2021

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

Статус: Дисциплина общефакультетского пула
Когда читается: 3, 4 модуль
Язык: русский
Кредиты: 7

Программа дисциплины

Аннотация

В рамках данной дисциплины студенты могут познакомиться с основными алгоритмами и структурами данными, а также с основными подходами построения алгоритмов. Данные знания могут быть полезны, как для развития алгоритмического мышления, так и для практического применения полученных знаний при разработке ПО. Дисциплина реализуется в формате смешанного обучения и представляет собой набор 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