Бакалавриат 2023/2024

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

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

Лучший по критерию «Новизна полученных знаний»

Статус: Курс по выбору (Вычислительные социальные науки)

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет социальных наук

Когда читается: 2-й курс, 1, 2 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для своего кампуса

Преподаватели: Горденко Мария Константиновна, Куренков Владимир Вячеславович

Язык: русский

Кредиты: 4

Контактные часы: 60

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

Аннотация

В курсе рассматриваются теоретические основы комбинаторных алгоритмов решения известных задач сетевой и дискретной оптимизации и изучаются часто используемые структуры данных. Особое внимание уделяется применению современных структур данных для эффективной реализации комбинаторных алгоритмов.

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

• Целью освоения дисциплины является формирование у студентов теоретических знаний и практических навыков в области теории алгоритмов, современных структур данных и их реализации на языке программирования C++.

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

• Понимание возможностей строковых алгоритмов, умение выбрать суффиксную структуру под конкретную задачу.
• Знает основые понятия теории алгоритмов и структур данных
• Использует базовые алгоритмы и подходы и модифицирует их, исходя из специфики решаемой задачи.
• Подбирает оптимальный алгоритм для конкретной практической задачи, анализирует его эффективность.
• Формализует и описывает алгоритм решения поставленных практических задач. Математически корректно и адекватно записывает алгоритмы, наиболее корректно описывающие дискретные объекты прикладной задачи.

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

• Алгоритмы на строках.
• Комбинаторная оптимизация.
• Потоки в сети.
• Параллельные алгоритмы.
• Персистентные структуры.

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

• Домашнее задания
  Решение задач с использованием системы автоматизированной проверки решений Яндекс.Контест.
• Работа на семинарах
• Экзамен

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

• 2023/2024 учебный год 2 модуль
  0.6 * Домашнее задания + 0.1 * Работа на семинарах + 0.3 * Экзамен

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

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

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms (3rd edition). – MIT Press, 2009. – 1292 pp.
• Алгоритмы : построение и анализ, пер. с англ., 3-е изд., 1323 с., Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К., 2018
• Комбинаторная оптимизация. Алгоритмы и сложность, Пападимитриу, Х., 1985

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

• Алгоритмы : построение и анализ, 2-е изд., 1290 с., Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К., 2012

Авторы

• Промыслов Валентин Валерьевич
• Куренков Владимир Вячеславович
• Боднарук Иван Иванович