Бакалавриат
2024/2025
Алгоритмы и структуры данных-2
Лучший по критерию «Полезность курса для Вашей будущей карьеры»
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Статус:
Курс по выбору (Программная инженерия)
Направление:
09.03.04. Программная инженерия
Кто читает:
Департамент программной инженерии
Где читается:
Факультет компьютерных наук
Когда читается:
2-й курс, 3, 4 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Язык:
русский
Кредиты:
5
Программа дисциплины
Аннотация
Учебный курс «Алгоритмы и структуры данных-2» предлагается студентам бакалавриата по направлению «Программная инженерия» на факультете компьютерных наук НИУ ВШЭ. Курс относится к обязательным предметам. Основная задача данного курса лежит в формировании основ профессионального каркаса в области проектирования и анализа эффективности алгоритмов, а также разработки структур данных. В рамках курса, в частности, рассматриваются: различные стратегии разработки алгоритмов (динамическое программирование, жадные алгоритмы, поиск с возвратом и приближенные алгоритмы), подходы к организации хеш-таблиц, алгоритмы на графовых и строковых структурах данных, а также предельные вопросы разрешимости и вычислимости. Лекции и практические занятия тесно взаимосвязаны. Лекции, в первую очередь, предназначены для знакомства с новыми темами, тогда как практические занятия предназначены для решения конкретных задач — аналитически, а также путем реализации алгоритмов на языке С++.
Цель освоения дисциплины
- формирование основ профессионального каркаса в области проектирования и анализа эффективности алгоритмов, а также разработки структур данных
Планируемые результаты обучения
- овладеть различными стратегиями разработки алгоритмов
- овладеть подходами к реализации различных структур данных и их применению в разработке алгоритмов
- получить опыт в реализации алгоритмов и структур данных на языке программирования С++
Содержание учебной дисциплины
- Неделя 14. Хеширование. Хеш-функции
- Неделя 15. Хеш-таблицы
- Неделя 16. Вероятностные структуры данных
- Неделя 17. Графы. Базовые аспекты
- Неделя 18. Остовное дерево графа
- Неделя 19. Поиск кратчайших путей в графе
- Неделя 20. Сети и потоки
- Неделя 22-23. Раскраска и укладка графа
- Неделя 24. Поиск точного вхождения строки в текст
- Неделя 25. Редакционные расстояния
- Неделя 27. Хранение и сортировка строк
- Неделя 28. Кодирование и сжатие строк
- Неделя 14-18. Стратегии разработки алгоритмов
Элементы контроля
- ПР_ЗАНРегулярная активность на практических занятиях
- НАКОПФормализуемая часть накопленной оценки
- ЭКЗАМЕН
Список литературы
Рекомендуемая основная литература
- 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