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

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

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

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

Статус: Курс обязательный (Компьютерные науки и анализ данных)

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

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

Где читается: Факультет компьютерных наук

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

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

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

Преподаватели: Густокашин Михаил Сергеевич, Захаров Павел Александрович, Куренков Владимир Вячеславович, Тяпкин Даниил Николаевич

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

Кредиты: 9

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

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

Аннотация

В курсе рассматриваются основные подходы к анализу и проектированию алгоритмов и структур данных. Среди тем, изучаемых в курсе, — асимптотическая оценка сложности алгоритма в худшем случае, эффективные алгоритмы сортировки и выбора порядковых статистик, структуры данных (двоичные деревья поиска, кучи, хеш-таблицы), способы проектирования алгоритмов (разделяй и властвуй, динамическое программирование, жадная стратегия), основные алгоритмы на графах (кратчайшие пути, топологическая сортировка, компоненты связности, минимальные остовные деревья).

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

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

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

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

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

Рекурсивные алгоритмы и рекуррентные соотношения
Асимптотический анализ
Динамическое программирование
Сортировки
Разделяй и властвуй
Алгоритмы на графах
Структуры данных
Жадные алгоритмы
Потоки в сетях
Конечные автоматы, регулярные выражения, контекстно-свободные грамматики

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

Домашнее задание
Итоговая оценка за выполнение домашних заданий определяется по формуле round((A + 0.5B - 2C) / 47 * 10), где: A — количество задач, сданных до дедлайнов; B — количество задач, сданных после дедлайнов; C — количество штрафных баллов за нарушение академических норм. Итоговая оценка за выполнение домашних заданий выражается целым числом от 0 до 10 (если результат получился меньше 0 или больше 10, то он заменяется на 0 или 10 соответственно). Всего в домашних заданиях было выдано 52 задачи. Для получения итоговой оценки 10 достаточно решить 47 из них.
Контрольная работа 1
Работа на семинаре 1
Экзамен (письменный) 1
Домашнее задание 2
Контрольная работа 2
Работа на семинаре 2
Экзамен (устный)
Экзамен проводится дистанционно через Zoom. Технические требования: web-камера, микрофон, наушники / колонки, Zoom.

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

2021/2022 учебный год 2 модуль
0.3 * Домашнее задание + 0.1 * Работа на семинаре 1 + 0.2 * Контрольная работа 1 + 0.4 * Экзамен (письменный) 1
2021/2022 учебный год 4 модуль
0.2 * Домашнее задание + 0.33 * Экзамен (письменный) 1 + 0.07 * Работа на семинаре 1 + 0.07 * Контрольная работа 1 + 0.33 * 2021/2022 учебный год 2 модуль

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

Авторы

Андронова Екатерина Юрьевна
Соколов Евгений Андреевич

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