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

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

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

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

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

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

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

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

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

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

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

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

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

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

Кредиты: 9

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

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

Аннотация

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

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

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

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

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

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

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

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

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

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

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

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

Авторы

Куренков Владимир Вячеславович

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