Algorithms and Data Structures-1

2024/2025

Academic Year

RUS

Instruction in Russian

5

ECTS credits

Delivered by:

School of Software Engineering

Type:

Elective course

When:

2 year, 1, 2 module

Instructors

Belaventsev, Valerii

Бутаков Дмитрий Викторович

Ignatov, Andrei

Nesterov, Roman

Terlych, Nikita

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

Аннотация

Учебный курс "Алгоритмы и структуры данных" является обязательной дисциплиной для студентов второго курса по направлению "Программная инженерия" факультета компьютерных наук НИУ ВШЭ. Основная цель курса заключается в формировании у студентов навыков анализа производительности алгоритмов, работающих с различными структурами данных, и выбора оптимальных решений для конкретных практических задач. В ходе обучения рассматриваются методы асимптотического анализа сложности как детерминированных, так и стохастических алгоритмов, изучаются алгоритмы сортировки, методы эффективного хранения и поиска данных, включая организацию хеш-таблиц и деревьев, а также графовые и строковые алгоритмы. Особое внимание уделяется различным парадигмам разработки алгоритмов, таким как жадные методы, приближенные алгоритмы и динамическое программирования. Кроме того, рассматриваются фундаментальный вопросы разрешимости и вычислимости. Лекции направлены на систематическое освоение материала, тогда как практические занятия позволяют закрепить полученные знания через решение задач и реализацию изученных алгоритмов и структур данных на языке программирования С++. Тесная взаимосвязь лекционного материала и практической работы обеспечивает глубокое и всестороннее освоение курса.

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

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

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

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

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

• Неделя 1. Введение
• Неделя 2. Линейные
• Неделя 3. Асимптотический
• Неделя 4. Асимптотический-2
• Неделя 5. Мастер-теорема
• Неделя 6-7. Стохастические
• Неделя 8. Сортировка, основанная
• Неделя 9. Линейная
• Неделя 10. Бинарные
• Неделя 11. AVL
• Неделя 12. Случай
• Неделя 13. Splay

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

• НАКОП
  Формализуемая часть накопленной оценки
• ЭКЗАМЕН
  Экзамен по курсу
• ПР_ЗАН
  Регулярная работа на практических занятиях

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

• 2024/2025 2nd module
  0.48 * НАКОП + 0.17 * ПР_ЗАН + 0.35 * ЭКЗАМЕН

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

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

• Data structures and algorithm analysis in C++, Weiss, M. A., 2006
• Introduction to algorithms, Cormen, T. H., 2009

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

• Алгоритмы на С++ : анализ структуры данных, сортировка, поиск, алгоритмы на графах, Седжвик, Р., 2014
• Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих. - 978-5-496-02541-6 - Бхаргава А. - 2017 - Санкт-Петербург: Питер - https://ibooks.ru/bookshelf/364142 - 364142 - iBOOKS

Авторы

• Нестеров Роман Александрович