ExtMem 23 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
TurtlePU (обсуждение | вклад) (→Домашние задания) |
TurtlePU (обсуждение | вклад) (→Лекции и семинары) |
||
| Строка 45: | Строка 45: | ||
| 11 окт 23 | | 11 окт 23 | ||
|| Решение теоретических задач на List Ranking; Distribution sweeping | || Решение теоретических задач на List Ranking; Distribution sweeping | ||
| − | || [https://jamboard.google.com/d/1qE7_D1UW3acVOB4c29eoSmuvvXvVH0DYpHwpQW2TRmE/edit?usp=sharing Доска] | + | || [https://jamboard.google.com/d/1qE7_D1UW3acVOB4c29eoSmuvvXvVH0DYpHwpQW2TRmE/edit?usp=sharing Доска]; [https://disk.yandex.ru/d/zl7DgU7FmuJKLg/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B%20%D0%B2%D0%BE%20%D0%B2%D0%BD%D0%B5%D1%88%D0%BD%D0%B5%D0%B9%20%D0%BF%D0%B0%D0%BC%D1%8F%D1%82%D0%B8/%D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F%202023-10-11T13-37-49Z.mp4 Запись] |
|- | |- | ||
| 12 окт 23 | | 12 окт 23 | ||
|| External memory hash table; Linear hashing; Partial extensions | || External memory hash table; Linear hashing; Partial extensions | ||
|| [https://disk.yandex.ru/d/oKjH_1vZHP1x1Q/%D0%A1%D0%B5%D0%BC%D0%B8%D0%BD%D0%B0%D1%80%202023-10-12T15-08-04Z.mp4 Запись]; [https://link.springer.com/article/10.1007/s00453-007-9155-x Статья] | || [https://disk.yandex.ru/d/oKjH_1vZHP1x1Q/%D0%A1%D0%B5%D0%BC%D0%B8%D0%BD%D0%B0%D1%80%202023-10-12T15-08-04Z.mp4 Запись]; [https://link.springer.com/article/10.1007/s00453-007-9155-x Статья] | ||
| + | |- | ||
| + | | 18 окт 23 | ||
| + | || Буферизованные деревья | ||
| + | || [https://jamboard.google.com/d/1Osx58e4TG4vVtD7FE-pDf6dChxKMknNO_JM4VfyQ1Ug/edit?usp=sharing Доска]; [Запись] | ||
| + | |- | ||
| + | | 1 ноя 23 | ||
| + | || Piecewise geometric model index | ||
| + | || [https://jamboard.google.com/d/1bxyjRP4eJsvSNqDhPU_brBNiZsRcLVbEogcZ7_3UoUo/edit?usp=sharing Доска]; [https://disk.yandex.ru/d/zl7DgU7FmuJKLg/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B%20%D0%B2%D0%BE%20%D0%B2%D0%BD%D0%B5%D1%88%D0%BD%D0%B5%D0%B9%20%D0%BF%D0%B0%D0%BC%D1%8F%D1%82%D0%B8/%D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F%202023-11-01T13-40-44Z.mp4 Запись] | ||
| + | |- | ||
| + | | 8 ноя 23 | ||
| + | || Log-structured merge trees | ||
| + | || [https://jamboard.google.com/d/1-I8n1QHY6ZVdNNx5HMs6UM9VeSHm81YnIZPZfjcibBY/edit?usp=sharing Доска]; [https://disk.yandex.ru/d/zl7DgU7FmuJKLg/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B%20%D0%B2%D0%BE%20%D0%B2%D0%BD%D0%B5%D1%88%D0%BD%D0%B5%D0%B9%20%D0%BF%D0%B0%D0%BC%D1%8F%D1%82%D0%B8/%D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F%202023-11-08T13-30-40Z.mp4 Запись] | ||
|- | |- | ||
| 9 ноя 23 | | 9 ноя 23 | ||
|| Write-optimized data structures: B-eps trees, COLA | || Write-optimized data structures: B-eps trees, COLA | ||
| − | || [http://supertech.csail.mit.edu/papers/BenderFaJa15.pdf B-eps tree]; [http://supertech.csail.mit.edu/papers/sbtree.pdf COLA] | + | || [http://supertech.csail.mit.edu/papers/BenderFaJa15.pdf B-eps tree]; [http://supertech.csail.mit.edu/papers/sbtree.pdf COLA]; [https://disk.yandex.ru/d/zl7DgU7FmuJKLg/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B%20%D0%B2%D0%BE%20%D0%B2%D0%BD%D0%B5%D1%88%D0%BD%D0%B5%D0%B9%20%D0%BF%D0%B0%D0%BC%D1%8F%D1%82%D0%B8/%D0%A1%D0%B5%D0%BC%D0%B8%D0%BD%D0%B0%D1%80%202023-11-09T15-39-28Z.mp4 Запись] |
| + | |- | ||
| + | | 15 ноя 23 | ||
| + | || Модель устройства кэша; Лемма об оптимальном кэшировании; Cache-oblivious алгоритмы | ||
| + | || [https://jamboard.google.com/d/1EWySD7lvGtBH9F02cq7pkPWKcQGDxFLaei77h4b7-YQ/edit?usp=sharing Доска]; [https://disk.yandex.ru/d/zl7DgU7FmuJKLg/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B%20%D0%B2%D0%BE%20%D0%B2%D0%BD%D0%B5%D1%88%D0%BD%D0%B5%D0%B9%20%D0%BF%D0%B0%D0%BC%D1%8F%D1%82%D0%B8/%D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F%202023-11-15T13-40-22Z.mp4 Запись] | ||
| + | |- | ||
| + | | 22 ноя 23 | ||
| + | || Решение теоретических задач в модели кэширования: транспонирование, бинарный поиск, COLA | ||
| + | || [https://jamboard.google.com/d/17pc-ovckwCtgRcxuK3Db6Eh02C6IGKsicbH33Bdt7P4/edit?usp=sharing Доска]; [Запись] | ||
| + | |- | ||
| + | | 29 ноя 23 | ||
| + | || Модель для стриминговых алгоритмов; Count (Min) Sketch; Алгоритм Misra-Gries | ||
| + | || [https://jamboard.google.com/d/1KeUdEOjc2WtT6C-bnlmvGPXST2kzLxvAh4H6KsRFSfA/edit?usp=sharing Доска]; [Запись] | ||
| + | |- | ||
| + | | 6 дек 23 | ||
| + | || Коммуникационная сложность; Задача EQ; Коммуникационная сложность и стриминг | ||
| + | || [https://jamboard.google.com/d/1Ii17txcUQn63PNcn9RmFmF48H5EiT9mknaJ7i6m5jBk/edit?usp=sharing Доска]; [Запись] | ||
|} | |} | ||
Версия 03:52, 7 декабря 2023
Содержание
Алгоритмы во внешней памяти
Осенний курс по выбору для студентов 3-4 курсов ПМИ ФКН ВШЭ.
Преподаватели:
- Павел Соколов aka @TurtlePU;
- Михаил Анопренко aka @manoprenko.
Полезные ссылки
Лекции и семинары
| Дата | Тема | Информация, ссылки |
|---|---|---|
| 27 сен 23 | Организационная информация; Модель вычислений во внешней памяти; Сортировка во внешней памяти | Доска; Запись |
| 28 сен 23 | Практические аспекты вычислений во внешней памяти: операционная система, файловая система, системные вызовы | Запись |
| 4 окт 23 | Решение теоретических задач в модели внешней памяти: стек, очередь, суммы на отрезках | Доска; Запись |
| 5 окт 23 | List Ranking; Time Forward Processing | Запись |
| 11 окт 23 | Решение теоретических задач на List Ranking; Distribution sweeping | Доска; Запись |
| 12 окт 23 | External memory hash table; Linear hashing; Partial extensions | Запись; Статья |
| 18 окт 23 | Буферизованные деревья | Доска; [Запись] |
| 1 ноя 23 | Piecewise geometric model index | Доска; Запись |
| 8 ноя 23 | Log-structured merge trees | Доска; Запись |
| 9 ноя 23 | Write-optimized data structures: B-eps trees, COLA | B-eps tree; COLA; Запись |
| 15 ноя 23 | Модель устройства кэша; Лемма об оптимальном кэшировании; Cache-oblivious алгоритмы | Доска; Запись |
| 22 ноя 23 | Решение теоретических задач в модели кэширования: транспонирование, бинарный поиск, COLA | Доска; [Запись] |
| 29 ноя 23 | Модель для стриминговых алгоритмов; Count (Min) Sketch; Алгоритм Misra-Gries | Доска; [Запись] |
| 6 дек 23 | Коммуникационная сложность; Задача EQ; Коммуникационная сложность и стриминг | Доска; [Запись] |
Домашние задания
- Домашнее задание 1 (практическое). Задание Disk Measurement, условия в телеграм-канале. Дедлайн 19 ноября 23:59 MSK
- Домашнее задание 2 (теоретическое). Доступно в classroom. Дедлайн 15 ноября в 16:20.
- Домашнее задание 3 (практическое). TBA
- Домашнее задание 4 (теоретическое). Доступно в classroom. Дедлайн 20 декабря в 23:59.
- Домашнее задание 5 (практическое). TBA
Итоговая оценка за курс
Итог = Округление(0.2 * ДЗ1 + 0.2 * ДЗ2 + 0.2 * ДЗ3 + 0.2 * ДЗ4 + 0.2 * ДЗ5), где ДЗN — оценка за домашнее задание N.
Округление арифметическое.
