Обзор поточных алгоритмов (Всеволод Опарин)
Семинар по сублинейным алгоритмам


Что: Лекция
Когда: Пятница, 11 ноября 2016, 19:00–20:20
Где: ПОМИ РАН, аудитория 106

Описание

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

На семинаре я расскажу, как посчитать число различных элементов в массиве, \(F_2\) момент, а также про скетчи для подсчета частотных статистик. Если останется время, расскажу про \(L_0\)-сэмплирование и поиск компонент связности в графе в поточной модели.