Магистратура
2026/2027
Алгоритмы во внешней памяти
ID 1231076
Статус:
Курс по выбору (Современные компьютерные науки)
Кто читает:
Базовая кафедра Яндекс
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 1, 2 модуль
Охват аудитории:
для своего кампуса
Язык:
русский
Кредиты:
6
Контактные часы:
56
Программа дисциплины
Аннотация
Учебная дисциплина «Алгоритмы во внешней памяти» знакомит студентов с основными методами разработки и анализа алгоритмов решения задач обработки, хранения и эффективного использования массивов данных и информационных структур, размещенных на твердотельных (SSD) и дисковых (HDD) устройствах. Цель учебной дисциплины — создание базы для разработки эффективных алгоритмов решения прикладных задач, возникающих при использовании больших объемов информации и формирование у студентов умения использовать современные научные достижения в области адаптации эффективных алгоритмов для решения конкретных прикладных.
Цель освоения дисциплины
- В данном курсе будет дан обзор текущего состояния в области вычислений с учетом иерархической структуры памяти. Мы рассмотрим базовые примитивы (буферизация при чтении и записи, сортировка) и структуры данных (B-деревья и их вариации, буферизованные деревья, приоритетные очереди), поговорим о некоторых стандартных приемах и подзадачах (time forward processing, list ranking). Также мы поговорим про практические подходы к работе с дисками в разных структурах данных, расскажем про Log structured merge trees. Будет затронута тема кеширования и cache-oblivious алгоритмов. Также во второй части курса мы рассмотрим модель streaming-вычислений, в которой данные на вход поступают итеративно и их количество такого, что сохранить их в оперативной памяти или на диске не представляется возможным. Тем не менее, даже в такой модели многие задачи оказываются решаемыми (зачастую лишь приближенно и с некоторой вероятностью); мы подробно рассмотрим такие классические задачи, как поиск порядковой статистики, построение структуры данных для подсчета частот встречаемости элементов, задачу поиска числа различных элементов и многие другие. Часть семинаров будет посвящена решению теоретических задач и рассказу различных тем, не помещающихся в лекционный материал, но тем не менее важных для получения целостной картины изучаемого курса. На оставшейся части семинаров мы рассмотрим вопросы устройства оперативной памяти и жесткого диска в современных компьютерах, а также научимся эффективно реализовывать на практике часть алгоритмов, рассказанных на лекциях. Будет несколько практических домашних заданий, в рамках которых вам предстоит поработать с дисками в операционной системе Linux, реализовать эффективную сортировку во внешней памяти и научиться существенно обгонять стандартный std::binary_search за счет эффективной работы с cache-ом процессора.
Содержание учебной дисциплины
- Модель вычислений во внешней памяти и базовые алгоритмы
- Техники проектирования алгоритмов во внешней памяти
- Деревья и write-optimized структуры данных
- Хеширование и фильтрация запросов
- Кеши и cache-efficient алгоритмы
- Экспериментальный анализ производительности
- Потоковые алгоритмы
