ExtMem 23 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
TurtlePU (обсуждение | вклад) (→Полезные ссылки) |
TurtlePU (обсуждение | вклад) (→Лекции и семинары) |
||
| Строка 84: | Строка 84: | ||
|| Коммуникационная сложность; Задача EQ; Коммуникационная сложность и стриминг | || Коммуникационная сложность; Задача EQ; Коммуникационная сложность и стриминг | ||
|| [https://jamboard.google.com/d/1Ii17txcUQn63PNcn9RmFmF48H5EiT9mknaJ7i6m5jBk/edit?usp=sharing Доска]; [Запись] | || [https://jamboard.google.com/d/1Ii17txcUQn63PNcn9RmFmF48H5EiT9mknaJ7i6m5jBk/edit?usp=sharing Доска]; [Запись] | ||
| + | |- | ||
| + | | 13 дек 23 | ||
| + | || Счётчик Морриса и Count Sketch | ||
| + | || [https://jamboard.google.com/d/1NE-0iIKXrvI_9Y58wBCsspAJ_4gYwVFk1KVYMfNzSI8/edit?usp=sharing Доска]; [Запись] | ||
|} | |} | ||
Текущая версия на 18:10, 15 декабря 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; Коммуникационная сложность и стриминг | Доска; [Запись] |
| 13 дек 23 | Счётчик Морриса и Count Sketch | Доска; [Запись] |
Домашние задания
- Домашнее задание 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.
Округление арифметическое.
