# 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 | Модель вычислений во внешней памяти. Сканирование. Буферизация при чтении и записи. Оптимальая сортировка во внешней памяти. Задача ранжирования списка. Джойны. Рандомизированный поиск независимого множества в списке.
1. Clicking ▼&► to (un)fold the tree menu may facilitate locating what you want to find. 2. Videos embedded here do not necessarily represent my viewpoints or preferences. 3. This is just one of my several websites. Please click the category-tags below these two lines to go to each independent website.
No comments:
Post a Comment