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

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

Литература

Лекционный материалы по аналогичному курсу Дармутского Колледжа
S. Muthukrishnan Data Streams: Algorithms and Applications (выбрать Book: pdf)

Правила получения зачёта: rules.pdf