Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Алгоритмы во внешней памяти
Казань / осень 2014, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

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

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

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

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

Дата и время Занятие Место Материалы
10 сентября
18:00–19:20
Лекция, Лекция 2-й учебный корпус К(П)ФУ Нет
10 сентября
19:35–20:55
Лекция, Лекция 2-й учебный корпус К(П)ФУ Нет
11 сентября
18:00–19:20
Лекция, Лекция 2-й учебный корпус К(П)ФУ Нет
11 сентября
19:35–20:55
Лекция, Лекция 2-й учебный корпус К(П)ФУ Нет
12 сентября
18:00–19:20
Лекция, Лекция 2-й учебный корпус К(П)ФУ Нет
12 сентября
19:35–20:55
Лекция, Лекция 2-й учебный корпус К(П)ФУ Нет