Алгоритмы во внешней памяти

Магистратура 2025/2026

Статус: Курс по выбору (Современные компьютерные науки)

Кто читает: Базовая кафедра Яндекс

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

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

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

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

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

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

Аннотация

Учебная дисциплина «Алгоритмы во внешней памяти» знакомит студентов с основными методами разработки и анализа алгоритмов решения задач обработки, хранения и эффективного использования массивов данных и информационных структур, размещенных на твердотельных (SSD) и дисковых (HDD) устройствах. Цель учебной дисциплины — создание базы для разработки эффективных алгоритмов решения прикладных задач, возникающих при использовании больших объемов информации и формирование у студентов умения использовать современные научные достижения в области адаптации эффективных алгоритмов для решения конкретных прикладных.

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

В данном курсе будет дан обзор текущего состояния в области вычислений с учетом иерархической структуры памяти. Мы рассмотрим базовые примитивы (буферизация при чтении и записи, сортировка) и структуры данных (B-деревья и их вариации, буферизованные деревья, приоритетные очереди), поговорим о некоторых стандартных приемах и подзадачах (time forward processing, list ranking). Также мы поговорим про практические подходы к работе с дисками в разных структурах данных, расскажем про Log structured merge trees. Будет затронута тема кеширования и cache-oblivious алгоритмов. Также во второй части курса мы рассмотрим модель streaming-вычислений, в которой данные на вход поступают итеративно и их количество такого, что сохранить их в оперативной памяти или на диске не представляется возможным. Тем не менее, даже в такой модели многие задачи оказываются решаемыми (зачастую лишь приближенно и с некоторой вероятностью); мы подробно рассмотрим такие классические задачи, как поиск порядковой статистики, построение структуры данных для подсчета частот встречаемости элементов, задачу поиска числа различных элементов и многие другие. Часть семинаров будет посвящена решению теоретических задач и рассказу различных тем, не помещающихся в лекционный материал, но тем не менее важных для получения целостной картины изучаемого курса. На оставшейся части семинаров мы рассмотрим вопросы устройства оперативной памяти и жесткого диска в современных компьютерах, а также научимся эффективно реализовывать на практике часть алгоритмов, рассказанных на лекциях. Будет несколько практических домашних заданий, в рамках которых вам предстоит поработать с дисками в операционной системе Linux, реализовать эффективную сортировку во внешней памяти и научиться существенно обгонять стандартный std::binary_search за счет эффективной работы с cache-ом процессора.