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

Общая информация
ЛекторМ. А. Бабенко
Семестросень 2012
Дата начала15.09.2012
Количество пар5
Язык курсарусский
Вопросы к экзамену
Анонсы
Встреча на сайте T&Phttp://theoryandpractice.ru/courses/10856-algoritmy-vo-vneshney-pamyati
Анонс habrahabr.ruhttp://habrahabr.ru/events/962/
Аннотация

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

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

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

Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Лекция
(15.09.2012 - 17:20 - 18:55)

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

http://www.lektorium.tv/lecture/?id=13929
2. Лекция
(15.09.2012 - 19:05 - 20:40)

Стеки, очереди и списки во внешней памяти. B-деревья. Буферизованные деревья.

http://www.lektorium.tv/lecture/?id=13930
3. Лекция
(16.09.2012 - 11:15 - 12:50)

Кучи во внешней памяти. Вычисления на орграфах, time forward processing. Раскраски и независимые множества. Поиск в ширину. Связные компоненты.

http://www.lektorium.tv/lecture/?id=13931
4. Лекция
(16.09.2012 - 13:00 - 14:35)

Ускоренный поиск в ширину во внешней памяти. Рандомизированное разбиение графа.

http://www.lektorium.tv/lecture/?id=13932
5. Лекция
(16.09.2012 - 15:35 - 17:10)

Кеши: стратегии замещения, ассоциативность. Cache oblivious алгоритмы. Транспонирование матриц. Деревья van Emde Boas. Бинарный поиск. Алгоритмы на потоках данных. Подсчет числа различных элементов.

http://www.lektorium.tv/lecture/?id=13933
Ваша оценка: Пусто Средняя: 4.6 (9 votes)
Share |
Курс  "Алгоритмы во внешней памяти"
Студенты курса "Алгоритмы во внешней памяти"
Студенты курса "Алгоритмы во внешней памяти"