City: Saint-Petersburg Kazan Language: Русский English

Algorithms in the external memory
Kazan / autumn 2014, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Традиционные курсы по алгоритмам, несмотря на подчеркнутую заботу об эффективности и практичности, часто предполагают, что обрабатываемые данные достаточно малы, чтобы поместиться в оперативную память компьютера. Последняя же обычно представляется одним большим массивом ячеек, доступ к любой из которых имеет одинаковую цену.

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

В данном курсе будет дан обзор текущего состояния в области вычислений с учетом иерархической структуры памяти. Мы рассмотрим базовые примитивы (буферизация при чтении и записи, сортировка) и структуры данных (B-деревья и их вариации, буферизованные деревья, приоритетные очереди), поговорим о некоторых стандартных приемах и подзадачах (time forward processing, list ranking).

Подробно будут рассмотрены алгоритмы на графах во внешней памяти (BFS, DFS, поиск связных компонент, MST). Будет затронута тема кеширования и cache-oblivious алгоритмов.

Date and time Class|Name Venue|short Materials
10 September
18:00–19:20
Лекция, lecture 2-й учебный корпус К(П)ФУ No
10 September
19:35–20:55
Лекция, lecture 2-й учебный корпус К(П)ФУ No
11 September
18:00–19:20
Лекция, lecture 2-й учебный корпус К(П)ФУ No
11 September
19:35–20:55
Лекция, lecture 2-й учебный корпус К(П)ФУ No
12 September
18:00–19:20
Лекция, lecture 2-й учебный корпус К(П)ФУ No
12 September
19:35–20:55
Лекция, lecture 2-й учебный корпус К(П)ФУ No