2018-04-28

(русский / in Russian) Алгоритмы во внешней памяти | Максим Бабенко (Algorithms in external memory by Maxim Babenko)

# playlist (click the video's upper-left icon)

source: Лекториум        2013年7月24日
Подписывайтесь на канал: https://www.lektorium.tv/ZJA
Следите за новостями:
https://vk.com/openlektorium
https://www.facebook.com/openlektorium
Традиционные курсы по алгоритмам, несмотря на подчеркнутую заботу об эффективности и практичности, часто предполагают, что обрабатываемые данные достаточно малы, чтобы поместиться в оперативную память компьютера. Последняя же обычно представляется одним большим массивом ячеек, доступ к любой из которых имеет одинаковую цену.
В реальных приложениях эта модель оказывается не слишком подходящей. Во-первых, существует большое число случаев, когда необходимо уметь обрабатывать данные на внешнем носителе, обычно жестком диске. Во-вторых, используемые сейчас повсеместно многоуровневые системы кеширования делают фактическое время исполнения алгоритма существенно менее предсказуемым. Память не является гомогенной средой, и хороший алгоритм должен заботиться о том, чтобы располагать данные правильным с точки зрения локальности образом.
В данном курсе будет дан обзор текущего состояния в области вычислений с учетом иерархической структуры памяти. Мы рассмотрим базовые примитивы (буферизация при чтении и записи, сортировка) и структуры данных (B-деревья и их вариации, буферизованные деревья, приоритетные очереди), поговорим о некоторых стандартных приемах и подзадачах (time forward processing, list ranking). Подробно будут рассмотрены алгоритмы на графах во внешней памяти (BFS, DFS, поиск связных компонент, MST). Будет затронута тема кеширования и cache-oblivious алгоритмов.
Страница курса на сайте Computer Science клуба.logic.pdmi.ras.ru/csclub/courses/hugedataalgorithms

Лекция 1 | Модель вычислений во внешней памяти. Сканирование. Буферизация при чтении и записи. Оптимальая сортировка во внешней памяти. Задача ранжирования списка. Джойны. Рандомизированный поиск независимого множества в списке.

No comments: