Algorithms and Data Structures

2024/2025

Academic Year

RUS

Instruction in Russian

8

ECTS credits

Delivered at:

Joint Department with MERA Group (Faculty of Informatics, Mathematics, and Computer Science (HSE Nizhny Novgorod))

Course type:

Compulsory course

When:

1 year, 2-4 module

Instructors

Bychkov, Ilya S.

Железин Михаил Михайлович

Захаров Максим Алексеевич

Naumov, Nikita

Тараканов Кирилл Сергеевич

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

Аннотация

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

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

• Знакомство с существующими алгоритмами для решения различных задач
• Знакомство с существующими структурами данных и их основными операциями
• Получение навыков проектирования, анализа и тестирования алгоритмов

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

• Доказывать оценки сложности алгоритмов
• Доказывать оценки сложности алгоритмов поиска
• Доказывать оценки сложности алгоритмов сортировки
• Доказывать сложность алгоритмов обхода графов
• Доказывать сложность алгоритмов поиска в тексте
• Доказывать сложность алгоритмов поиска кратчайших путей
• Доказывать сложность основных операций с массивами, связными списками, стеками, очередями
• Объяснять и и уметь реализовывать основные операции с массивами, связными списками, стеками, очередями
• Объяснять и уметь реализовывать алгоритмы обхода графов
• Описывать и уметь реализовывать алгоритмы поиска
• Описывать и уметь реализовывать алгоритмы поиска в тексте
• Описывать и уметь реализовывать алгоритмы поиска кратчайших путей
• Описывать и уметь реализовывать алгоритмы сортировки
• Описывать работу метода разделяй и властвуй, алгоритмов динамического программирования и жадных алгоритмов
• Описывать различные варианты построения и использования графовых моделей
• Определять сложность алгоритмов по их описанию
• Разрабатывать алгоритмы в соответствии с рассмотренными парадигмами для решения задач
• Формулировать задачи о кратчайших путях в различных постановках
• Формулировать задачи о поиске в тексте, поиске подстроки в строке
• Формулировать задачу поиска
• Формулировать задачу сортировки
• Формулировать понятие алгоритма, программы.
• Формулировать понятие графа, представления графа;
• Формулировать понятие переменной, массива.
• Формулировать понятия массива, связного списка, стека, очереди и их вариаций
• Формулировать понятия пространственной и временной сложности алгоритма.

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

• Введение в алгоритмы. Понятие алгоритма и программы. Переменные, массивы.
• Задача сортировки. Простые алгоритмы сортировки.
• Задача сортировки. Эффективные алгоритмы сортировки.
• Сложность алгоритмов.
• Алгоритмы поиска.
• Базовые структуры данных.
• Понятие графа. Алгоритмы на графах.
• Задачи о кратчайших путях. Алгоритмы нахождения кратчайших путей в графах.
• Алгоритмические парадигмы.
• Строковые алгоритмы

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

• Модуль 2 - Контесты
  Практические задания в модуле 2
• Модуль 2 - Контрольные работы
  Контрольные работы в модуле 1
• Модуль 3 - Контесты
  Практические работы в модуле 3
• Модуль 4 - Контесты
  Практические задание в модуле 4
• Модуль 3 - Контрольные работы
  Контрольные работы в модуле 3
• Модуль 4 - Контрольные работы
• Модуль 2 - Активность
  Активность по курсу в модуле 2
• Модуль 3 - Активность
  Активность по курсу в модуле 3
• Модуль 4 - Активность
  Активность по курсу в модуле 4
• Модуль 3 - Экзамен
  Экзамен за модули 2-3
• Модуль 4 - Экзамен

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

• 2024/2025 3rd module
  0.03 * Модуль 2 - Активность + 0.09 * Модуль 2 - Контесты + 0.18 * Модуль 2 - Контрольные работы + 0.03 * Модуль 3 - Активность + 0.09 * Модуль 3 - Контесты + 0.18 * Модуль 3 - Контрольные работы + 0.4 * Модуль 3 - Экзамен
• 2024/2025 4th module
  0.06 * Модуль 4 - Активность + 0.18 * Модуль 4 - Контесты + 0.36 * Модуль 4 - Контрольные работы + 0.4 * Модуль 4 - Экзамен

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

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

• C#. Алгоритмы и структуры данных : учеб. пособие, Тюкачёв, Н. А., 2018
• Cormen, T. H. (2009). Introduction to Algorithms (Vol. 3rd ed). Cambridge, Mass: The MIT Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=343613
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms (3rd edition). – MIT Press, 2009. – 1292 pp.
• Robert Sedgewick, & Kevin Wayne. (2014). Algorithms : Part I. [N.p.]: Addison-Wesley Professional. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1600534
• Алгоритмы : введение в разработку и анализ, Левитин, А. В., 2018
• Алгоритмы ГИС : теория и применение геоинформационных систем и технологий, Сяо, Нинчуань, 2021
• Информационная чувствительность компьютерных алгоритмов, Петрушин, В. Н., 2010
• Седжвик, Р. Алгоритмы на С++ : учебное пособие / Р. Седжвик. — 2-е изд. — Москва : ИНТУИТ, 2016. — 1772 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100565 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.

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

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

Авторы

• Асеева Наталья Владимировна
• Конаваленак Ирина Александровна
• Бычков Илья Сергеевич