Category 'Best Course for Career Development'

Category 'Best Course for Broadening Horizons and Diversity of Knowledge and Skills'

Delivered at:: Joint Department with Yandex (Big Data and Information Retrieval School)

Course type:: Compulsory course

When:: 1 year, 2, 4 module

Instructors

Bragin, Sergey

Гаглоев Александр Владимирович

Gustokashin, Mikhail

Кильянов Александр Андреевич

Киракосян Вазген Валерикович

Kurenkov, Vladimir

Михеев Александр Георгиевич

Наймушин Вячеслав Иванович

Петров Тимур Александрович

Плотников Алексей Валерьевич

Погодина Екатерина Валерьевна

Popov, Maksim

Samonenko, Ilya

Федоров Михаил Антонович

Фолунин Владимир Александрович

Яковлев Даниил Дмитриевич

Дополнительные материалы в LMS Задать вопрос

Аннотация

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

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

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

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

Знать о наиболее важных алгоритмах и структурах данных и основных принципах их проектирования и анализа
Иметь навыки реализации алгоритмов на языках 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.4 * Экзамен (письменный) 1 + 0.3 * Домашнее задание + 0.2 * Контрольная работа 1 + 0.1 * Работа на семинаре 1
2021/2022 учебный год 4 модуль
0.33 * 2021/2022 учебный год 2 модуль + 0.33 * Экзамен (письменный) 1 + 0.07 * Контрольная работа 1 + 0.07 * Работа на семинаре 1 + 0.2 * Домашнее задание

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

Авторы

Объедков Сергей Александрович
Погудин Глеб Александрович

Bachelor’s Programme 'Applied Mathematics and Information Science'

Algorithms and Data Structures

Instructors

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