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. Асимптотический анализ. Разделяй-и-властвуй 1.
• Неделя 4. Разделяй-и-властвуй 2. Рекуррентные соотношения
• Неделя 5. Разделяй-и-властвуй 3. Master-теорема
• Неделя 6. Стохастические алгоритмы
• Неделя 9. Порядковая статистика и нелинейные сортировки
• Неделя 10. Сортировка за линейное время
• Неделя 11. Бинарные деревья-1
• Неделя 12. Бинарные деревья-2
• Неделя 13. Бинарные деревья-3
• Неделя 14. Бинарные деревья-4

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

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

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

• 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

Авторы

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