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

2024/2025

Учебный год

RUS

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

5

Кредиты

Кто читает:

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

Статус:

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

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

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

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

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

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

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

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

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

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

Аннотация

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

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

• формирование основ профессионального каркаса в области проектирования и анализа эффективности алгоритмов, а также разработки структур данных

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

• овладеть различными стратегиями разработки алгоритмов
• овладеть подходами к реализации различных структур данных и их применению в разработке алгоритмов
• получить опыт в реализации алгоритмов и структур данных на языке программирования С++

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

• Неделя 14. Хеширование. Хеш-функции
• Неделя 15. Хеш-таблицы
• Неделя 16. Вероятностные структуры данных
• Неделя 17. Графы. Базовые аспекты
• Неделя 18. Остовное дерево графа
• Неделя 19. Поиск кратчайших путей в графе
• Неделя 20. Сети и потоки
• Неделя 22-23. Раскраска и укладка графа
• Неделя 24. Поиск точного вхождения строки в текст
• Неделя 25. Редакционные расстояния
• Неделя 27. Хранение и сортировка строк
• Неделя 28. Кодирование и сжатие строк
• Неделя 14-18. Стратегии разработки алгоритмов

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

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

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

• 2024/2025 4th module
  0.45 * НАКОП + 0.2 * ПР_ЗАН + 0.35 * ЭКЗАМЕН

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

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

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

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

• Алгоритмы на С++ : анализ структуры данных, сортировка, поиск, алгоритмы на графах, Седжвик, Р., 2014
• Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих. - 978-5-4461-0923-4 - Бхаргава А. - 2022 - Санкт-Петербург: Питер - https://ibooks.ru/bookshelf/376971 - 376971 - iBOOKS
• Теория графов, Оре, О., 2009
• Теория графов, Харари, Ф., 2015

Авторы

• Нестеров Роман Александрович
• Буцкая Евгения Александровна
• Лебедев Сергей Аркадьевич