Algorithms and Data Structures

2020/2021

Academic Year

RUS

Instruction in Russian

5

ECTS credits

Delivered at:

Department of Applied Mathematics and Informatics (Faculty of Informatics, Mathematics, and Computer Science (HSE Nizhny Novgorod))

Course type:

Compulsory course

When:

2 year, 1, 2 module

Instructor

Ponomarenko, Alexander

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

Аннотация

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

Цель освоения дисциплины

• знать основные структуры данных (список, дерево, хеш-таблицы, графы), базовые алгоритмы (поиск в глубину, поиск в ширину, принцип разделяй и властвуй, динамическое программирование, поиск с отсечением, генерирование комбинаторных объектов).
• развить алгоритмическое мышление
• овладеть навыками программирования на языке C++ в процессе реализации основных вычислительных алгоритмов и структур данных

Планируемые результаты обучения

• Знает различные формализации понятия алгоритма.
• Умеет использовать нотацию большого О
• Умеет оценивать вычислительную сложность алгоритмов
• Умеет реализовывать рекурсивные алгоритмы
• Владеет методом "поиск в ширину"
• Владеет методом "поиск в глубину"
• Понимает и умеет реализовывать "двоичное дерево"
• Понимает и умеет реализовывать различные методы хэширования
• Понимает когда можно использовать "жадные" алгоритмы.
• Умеет реализовывать различные комбинаторные объекты
• Умеет использовать метод динамического программирования
• Решает задачи методом динамического программирования
• Умеет реализовывать базовые алгоритмы на графах
• Умеет реализовывать алгоритмы поиска минимального остова, определения изоморфноти графов
• Умеет реализовывать алгоритмы построения выпуклой оболочки и вращения геометрических фигур

Содержание учебной дисциплины

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

Элементы контроля

• Лабораторная работа "Ход-конём"
• Лабораторная работа "Хамелеон"
  Поиск в ширину
• Лабораторная работа "Задача о сумме"
• Лабораторная работа "Сортировка подсчётом"
• Лабораторная работа "Хэширование цепочками"
• Лабораторная работа "Хэширование с открытой адресацией (двойное хэширование!)"
• Лабораторная работа "Поиск по интервалу в двоичном дереве"
• Лабораторная работа "Лабиринт с бомбами"
  Поиск в ширину/Динамическое программирование
• Лабораторная работа "Оптимальный порядок перемножения матриц"
  Динамическое программирование
• Лабораторная работа "Жук-инвалид"
• Лабораторная работа "Острова"
• Лабораторная работа "Количество правильных скобочных последовательностей"
• Лабораторная работа "Найти минимальный остов"
• Лабораторная работа "Взлом сети"
  Динамическое программирование
• Лабораторная работа "Быстрая сортировка"
  Разделяй и властвуй
• Лабораторная работа "Жадны до денег"
  Динамическое программирование
• Лабораторная работа "Ход-конём"
• Лабораторная работа "Хамелеон"
  Поиск в ширину
• Лабораторная работа "Задача о сумме"
• Лабораторная работа "Сортировка подсчётом"
• Лабораторная работа "Хэширование цепочками"
• Лабораторная работа "Хэширование с открытой адресацией (двойное хэширование!)"
• Лабораторная работа "Поиск по интервалу в двоичном дереве"
• Лабораторная работа "Лабиринт с бомбами"
  Поиск в ширину/Динамическое программирование
• Лабораторная работа "Оптимальный порядок перемножения матриц"
  Динамическое программирование
• Лабораторная работа "Жук-инвалид"
• Лабораторная работа "Острова"
• Лабораторная работа "Количество правильных скобочных последовательностей"
• Лабораторная работа "Найти минимальный остов"
• Лабораторная работа "Взлом сети"
  Динамическое программирование
• Лабораторная работа "Быстрая сортировка"
  Разделяй и властвуй
• Лабораторная работа "Жадны до денег"
  Динамическое программирование

Промежуточная аттестация

• Промежуточная аттестация (2 модуль)
  0.06 * Лабораторная работа "Быстрая сортировка" + 0.06 * Лабораторная работа "Взлом сети" + 0.06 * Лабораторная работа "Жадны до денег" + 0.06 * Лабораторная работа "Жук-инвалид" + 0.06 * Лабораторная работа "Задача о сумме" + 0.06 * Лабораторная работа "Количество правильных скобочных последовательностей" + 0.06 * Лабораторная работа "Лабиринт с бомбами" + 0.06 * Лабораторная работа "Найти минимальный остов" + 0.06 * Лабораторная работа "Оптимальный порядок перемножения матриц" + 0.06 * Лабораторная работа "Острова" + 0.06 * Лабораторная работа "Поиск по интервалу в двоичном дереве" + 0.06 * Лабораторная работа "Сортировка подсчётом" + 0.08 * Лабораторная работа "Хамелеон" + 0.08 * Лабораторная работа "Ход-конём" + 0.06 * Лабораторная работа "Хэширование с открытой адресацией (двойное хэширование!)" + 0.06 * Лабораторная работа "Хэширование цепочками"

Список литературы

Рекомендуемая основная литература

• Алгоритмы : построение и анализ, 2-е изд., 1290 с., Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К., 2012
• Алгоритмы : построение и анализ, пер. с англ., 3-е изд., 1323 с., Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К., 2018

Рекомендуемая дополнительная литература

• Апанасевич С.А. - Структуры и алгоритмы обработки данных. Линейные структуры: учебное пособие - Издательство "Лань" - 2019 - 136с. - ISBN: 978-5-8114-3366-7 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/113934