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

2022/2023

Учебный год

RUS

Обучение ведется на русском языке

9

Кредиты

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

Кто читает:

Базовая кафедра Яндекс (Департамент больших данных и информационного поиска)

Статус:

Курс обязательный

Когда читается:

1-й курс, 2, 4 модуль

Преподаватели

Бадмаев Тингир Мингиянович

Васина Олеся Игоревна

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

Галицкий Борис Васильевич

Головин Леонид Олегович

Грибов Филипп Юрьевич

Густокашин Михаил Сергеевич

Елисеев Владислав Юрьевич

Каймаков Кирилл Владимирович

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

Косакин Даниил Юрьевич

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

Мамаев Алексей Александрович

Марина Оксана Леонидовна

Петров Андрей Иванович

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

Сикалов Никита Сергеевич

Темирханов Азиз Арсенович

Тибилов Таймураз Валерьевич

Фадеева Екатерина Сергеевна

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

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

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

Аннотация

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

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

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

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

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

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

• Рекурсивные алгоритмы и рекуррентные соотношения
• Асимптотический анализ
• Динамическое программирование
• Сортировки
• Разделяй и властвуй
• Алгоритмы на графах
• Структуры данных
• Жадные алгоритмы
• Хэш таблицы
• Деревья

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

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

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

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

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

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

• Cormen, T. H. (2009). Introduction to Algorithms (Vol. 3rd ed). Cambridge, Mass: The MIT Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=343613

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

• Arora, S., & Barak, B. (2009). Computational Complexity : A Modern Approach. Cambridge: Cambridge eText. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=304712

Авторы

• Алиева Эльмира Махир Кызы
• Густокашин Михаил Сергеевич