Algorithms and Data Structures-2

2024/2025

Academic Year

RUS

Instruction in Russian

5

ECTS credits

Delivered by:

School of Software Engineering

Type:

Elective course

When:

2 year, 3, 4 module

Instructors

Belaventsev, Valerii

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

Ignatov, Andrei

Nesterov, Roman

Terlych, Nikita

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

Аннотация

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

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

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

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

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

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

• Неделя 1. Анализ и свойства хеш-функций
• Неделя 2. Хеш-таблицы и их внутренняя огранизация
• Неделя 3. Вероятностные структуры данных
• Неделя 4. Графы-1. Обходы и топологическая сортировка.
• Неделя 5. Графы-2. Минимальное остовное дерево
• Неделя 6. Графы-3. Кратчайшие пути
• Неделя 7. Графы-4. Сети и потоки
• Неделя 8. Графы-5. Раскраска и планарность
• Неделя 10. Строковые алгоритмы-1
• Неделя 11. Строковые алгоритмы-2
• Неделя 12. Строковые алгоритмы-3
• Неделя 13. Строковые алгоритмы-4
• Неделя 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

Авторы

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