Algorithms and Data Structures

2021/2022

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++ в процессе реализации основных вычислительных алгоритмов и структур данных

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

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

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

• Понятие и свойство алгоритма. Способы записи алгоритма. Различные формализации понятия алгоритма.
• Сложность алгоритмов. Классы алгоритмов.
• Поиск в ширину. Поиск в глубину. Рекурсия.
• Двоичные деревья.
• Хеширование
• Построение различных комбинаторных объектов
• Жадные алгоритмы
• Динамическое программирование
• Динамическое программирование – разные задачи.
• Алгоритмы на графах
• Алгоритмы на графах – 2
• Геометрические задачи

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

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

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

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

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

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

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

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

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

Авторы

• Пономаренко Александр Александрович
• Калягин Валерий Александрович