ExtMem 23 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(→‎Домашние задания)
(→‎Лекции и семинары)
 
(не показано 6 промежуточных версии 2 участников)
Строка 20: Строка 20:
 
[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 Записи занятий (Я.Диск)]
 
[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 Записи занятий (Я.Диск)]
  
−
== Лекции и семинары ==
+
[https://classroom.google.com/c/NjM2MTE4MTkxNDQ5?cjc=r4r4bcg Курс в classroom]
  
−
* '''Лекция 27 сен 23'''. Организационная информация; Модель вычислений во внешней памяти; Сортировка во внешней памяти. [https://jamboard.google.com/d/1BUTRq3ePWB4UzAUDrjB_BU8ei6J7glv6WDJ86-54Wa8/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-09-27T13-17-54Z.mp4 Запись].
+
[https://docs.google.com/spreadsheets/d/12oOWxDVIQ-c0_qAeIqRWM3oveTmQuHerW769LGJoucQ/edit?usp=sharing Таблица с оценками]
−
* '''Семинар 28 сен 23'''. Практические аспекты вычислений во внешней памяти: операционная система, файловая система, системные вызовы. [https://disk.yandex.ru/d/oKjH_1vZHP1x1Q/28.09.mp4 Запись].
+
 
−
* '''Семинар 4 окт 23'''. Решение теоретических задач в модели внешней памяти: стек, очередь, суммы на отрезках. [https://jamboard.google.com/d/1nXLq9S61A85AZGju-O4KPgp_mhcU2eB_KgudYa6Mi88/edit?usp=sharing Доска]; [https://disk.yandex.ru/d/oKjH_1vZHP1x1Q/04.10.mp4 Запись].
+
== Лекции и семинары ==
−
* '''Лекция 5 окт 23'''. List Ranking; Решение теоретических задач на List Ranking. [https://disk.yandex.ru/d/oKjH_1vZHP1x1Q/05.10.mp4 Запись].
+
{| class="wikitable"
−
* '''Семинар 11 окт 23'''. Решение теоретических задач на List Ranking; Distribution sweeping. [https://jamboard.google.com/d/1qE7_D1UW3acVOB4c29eoSmuvvXvVH0DYpHwpQW2TRmE/edit?usp=sharing Доска].
+
|-
 +
! Дата !! Тема !! Информация, ссылки
 +
|-
 +
| 27 сен 23
 +
|| Организационная информация; Модель вычислений во внешней памяти; Сортировка во внешней памяти
 +
|| [https://jamboard.google.com/d/1BUTRq3ePWB4UzAUDrjB_BU8ei6J7glv6WDJ86-54Wa8/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-09-27T13-17-54Z.mp4 Запись]
 +
|-
 +
| 28 сен 23
 +
|| Практические аспекты вычислений во внешней памяти: операционная система, файловая система, системные вызовы
 +
|| [https://disk.yandex.ru/d/oKjH_1vZHP1x1Q/28.09.mp4 Запись]
 +
|-
 +
| 4 окт 23
 +
|| Решение теоретических задач в модели внешней памяти: стек, очередь, суммы на отрезках
 +
|| [https://jamboard.google.com/d/1nXLq9S61A85AZGju-O4KPgp_mhcU2eB_KgudYa6Mi88/edit?usp=sharing Доска]; [https://disk.yandex.ru/d/oKjH_1vZHP1x1Q/04.10.mp4 Запись]
 +
|-
 +
| 5 окт 23
 +
|| List Ranking; Time Forward Processing
 +
|| [https://disk.yandex.ru/d/oKjH_1vZHP1x1Q/05.10.mp4 Запись]
 +
|-
 +
| 11 окт 23
 +
|| Решение теоретических задач на List Ranking; Distribution sweeping
 +
|| [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
 +
|| 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 Статья]
 +
|-
 +
| 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
 +
|| 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]; [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 Доска]; [Запись]
 +
|-
 +
| 13 дек 23
 +
|| Счётчик Морриса и Count Sketch
 +
|| [https://jamboard.google.com/d/1NE-0iIKXrvI_9Y58wBCsspAJ_4gYwVFk1KVYMfNzSI8/edit?usp=sharing Доска]; [Запись]
 +
|}
  
 
== Домашние задания ==
 
== Домашние задания ==
  
−
* Домашнее задание 1 (практическое). TBA
+
* Домашнее задание 1 (практическое). Задание Disk Measurement, условия в телеграм-канале. Дедлайн '''19 ноября 23:59 MSK'''
 
* Домашнее задание 2 (теоретическое). Доступно в classroom. Дедлайн '''15 ноября в 16:20'''.
 
* Домашнее задание 2 (теоретическое). Доступно в classroom. Дедлайн '''15 ноября в 16:20'''.
 
* Домашнее задание 3 (практическое). TBA
 
* Домашнее задание 3 (практическое). TBA
−
* Домашнее задание 4 (теоретическое). TBA
+
* Домашнее задание 4 (теоретическое). Доступно в classroom. Дедлайн '''20 декабря в 23:59'''.
 
* Домашнее задание 5 (практическое). TBA
 
* Домашнее задание 5 (практическое). TBA
  

Текущая версия на 18:10, 15 декабря 2023

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

Осенний курс по выбору для студентов 3-4 курсов ПМИ ФКН ВШЭ.

Преподаватели:

Полезные ссылки

Канал курса (Telegram)

Чат курса (Telegram)

Ссылка на среды (Zoom)

Ссылка на четверги (Zoom)

Записи занятий (Я.Диск)

Курс в classroom

Таблица с оценками

Лекции и семинары

Дата Тема Информация, ссылки
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.

Округление арифметическое.

Источник — «http://wiki.cs.hse.ru/index.php?title=ExtMem_23&oldid=82387»