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

2021/2022

Учебный год

RUS

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

8

Кредиты

Кто читает:

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

Статус:

Курс по выбору

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

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

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

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

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

Аннотация

"Курс дает базовые знания в области алгоритмов и структур данных. В явном виде они, может быть, не пригодятся, но очень важны для понимания работы библиотек, алгоритмов и языков программирования. Домашние задания по курсу закрепляют полученные знания и воспитывают хороший стиль написания кода, который позволяет избежать стандартных, но от этого ничуть не менее распространенных даже у опытных разработчиков, ошибок."

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

• Цель курса — обучить основам алгоритмического программирования, привить практические навыки решения задач с помощью базовых алгоритмов и структур данных, сформировать правильное представление о времени работы и эффективности различных алгоритмов и структур данных.

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

• Владеть концепцией динамического программирования
• Иметь представление о быстрых методах поиска k-й порядковой статистики
• Иметь представление о задачах LCA и RMQ и об связи между ними
• Иметь представление о кучах. Уметь использовать кучи для решения практических задач
• Иметь представление о персистентных структурах данных
• Иметь представление об основных алгоритмах сортировки. Понимать их преимущества и недостатки.
• Иметь представление об основных структурах данных
• Иметь представления о хэш-функциях и их свойствах. Уметь выбирать хэш-функцию для работы с заданным типом данных.
• Понимать устройство массивов переменного размера
• Уметь интерпретировать практические задачи в терминах теории графах, решать эти задачи с использованием графовых алгоритмах
• Уметь находить кратчайшие пути в графах
• Уметь обходить графы в ширину и в глубину
• Уметь оценивать сложность алгоритмов и объём дополнительной памяти
• Уметь строить и эффективно использовать деревья поиска, выбирать правильную стратегию балансировки
• Уметь строить остовные деревья для графов.
• Уметь устранять коллизии при использовании хэш-таблиц
• Уметь эффективно реализовывать алгоритмы на языке С++
• Уметь эффективно реализовывать структуры данных в виде структур на языке С++
• Уметь эффективно решать практические задачи с помощью динамического программирования

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

• Введение
• Динамическое программирование
• Введение в структуры данных
• Сортировки
• Кучи
• Хэширование
• Графы
• Деревья поиска
• Кратчайшие пути в графах
• LCA & RMQ
• Графы: продвинутые темы

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

• Домашняя работа 1
• Домашняя работа 2
• Экзамен

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

• 2021/2022 учебный год 2 модуль
  0.3 * Домашняя работа 1 + 0.3 * Домашняя работа 2 + 0.4 * Экзамен

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

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

• Комбинаторика и теория графов. Ч.1: ., Григорьев, Б. В., 2005
• Сахибназарова Виктория Бахтиёровна, Сайгак Кристина Олеговна, & Saygak Kristina Olegovna. (2016). Разработка и анализ алгоритма сортировки на основе использования бинарных деревьев. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.8368E341
• Суркова, А., & Буденков, С. (2012). Построение Модели И Алгоритма Кластеризации В Интеллектуальном Анализе Данных. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.E4300A4

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

• ВИТИСКА НИКОЛАЙ ИВАНОВИЧ, & ПОПОВ РОМАН АНАТОЛЬЕВИЧ. (2014). Разработка Учебной Программы На Ассемблере Для Демонстрации Скорости Реализации Программных И Быстрых Сортировок Массивов. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.36D9DE1C
• Комбинаторика и теория графов : учеб. пособие, Кочетков, Ю. Ю., 2009