Algorithms and Data Structures

2023/2024

Academic Year

RUS

Instruction in Russian

4

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
• Геометрические задачи

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

• Задачи по теме "Поиск в ширину"
  Задачи в формате ICPC
• Задачи по теме "Хэш-таблицы"
  Задачи в формате ICPC
• Задачи по теме "Сортировки"
  Задачи в формате ICPC
• Задачи по теме "Динамическое программирование"
• Задачи по теме "Алгоритмы на графах"
  Задачи в формате ICPC
• Задачи по теме "Геометрические задачи"
  Задачи в формате ICPC

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

• 2023/2024 учебный год 2 модуль
  0.166 * Задачи по теме "Алгоритмы на графах" + 0.166 * Задачи по теме "Геометрические задачи" + 0.166 * Задачи по теме "Динамическое программирование" + 0.166 * Задачи по теме "Поиск в ширину" + 0.17 * Задачи по теме "Сортировки" + 0.166 * Задачи по теме "Хэш-таблицы"

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

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

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

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

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

Авторы

• Пономаренко Александр Александрович