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

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

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

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

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

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

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

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

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

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

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

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

Кредиты: 9

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

Полная версия программы учебной дисциплины Задать вопрос

Аннотация

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

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

Изучение базовых алгоритмов и структур данных
Развитие навыков обоснования корректности алгоритмов, их практической реализации, теоретической и экспериментальной оценки их временной сложности

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

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

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

Алгоритмы: Классификация, сложность.
Теория чисел.
Рекурсивные алгоритмы.
Поиск и сортировка.
Структуры данных: стек, очередь, дек.
Динамическое программирование.
Куча
Задача RMQ и RSQ. Запросы на подотрезках массива.
Обработка событий.
Дерево поиска
Задача RMQ / RSQ. Дерево отрезков. Декартово дерево.
Представление сетей в компьютере.
Обход в глубину.
Задача нахождения кратчайших путей в графе.
Задача union - find.
Занача нахождения минимального островного дерева.

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

Работа на семинарах
Домашние задания
Контрольная работа
Контрольная работа
Работа на семинарах
Домашнее задание
Экзамен
Экзамен

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

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

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

Авторы

Боднарук Иван Иванович

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