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

2024/2025

Учебный год

RUS

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

10

Кредиты

Кто читает:

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

Статус:

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

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

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

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

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

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

Мамай Игорь Борисович

Мануйленко Никита Сергеевич

Панькова Марина Геннадьевна

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

Сафонов Иван Андреевич

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

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

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

Аннотация

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

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

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

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

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

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

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

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

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

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

• 2024/2025 2nd module
  0.3 * Домашнее задание + 0.2 * Контрольная работа + 0.1 * Работа на семинаре + 0.4 * Экзамен
• 2024/2025 4th module
  0.3 * Домашнее задание + 0.2 * Контрольная работа + 0.1 * Работа на семинаре + 0.4 * Экзамен

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

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

• Комбинаторика и теория графов : учеб. пособие, Кочетков, Ю. Ю., 2009

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

• Теория графов : учеб. пособие для втузов, Белов, В. В., 1976
• Язык С#. Базовый курс : учеб. пособие для вузов, Подбельский, В. В., 2013
• Язык С#. Решение задач : учеб. пособие для вузов, Подбельский, В. В., 2014

Авторы

• Фисенко Анна Сергеевна
• Алиева Эльмира Махир Кызы