Алгоритмы и структуры данных-1

2024/2025

Учебный год

RUS

Обучение ведется на русском языке

5

Кредиты

Лучший по критерию «Полезность курса для Вашей будущей карьеры»

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

Кто читает:

Департамент программной инженерии

Статус:

Курс по выбору

Когда читается:

2-й курс, 1, 2 модуль

Преподаватели

Белавенцев Валерий Евгеньевич

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

Игнатов Андрей Дмитриевич

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

Терлыч Никита Андреевич

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

Аннотация

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

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

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

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

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

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

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

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

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

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

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

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

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

• 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/products/364142 - 364142 - iBOOKS

Авторы

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