Рене Андреасович ван Беверн начинает читать спецкурс «Алгоритмы для анализа больших объёмов данных»

Память является одним из наиболее дорогих и дефицитных ресурсов в вычислительных центрах. Поэтому в этом курсе мы ознакомимся с алгоритмами для анализа данных, которые в силу их объёма невозможно хранить в памяти: их нужно анализировать «на лету», по мере поступления. Мы увидим, что в этом сценарии простейшие вычислительные задачи вдруг становятся неподъёмными. Например, мы докажем, что для определения медианы выборки или подсчёта разных записей в списке требуется объём памяти, соразмерный всему объёму входных данных. Дальше мы познакомимся со множеством подходов построения рандомизированных и приближённых алгоритмов с произвольно малыми заданными погрешностью и вероятностью ошибки, которые с логарифмической памятью решают многие фундаментальные задачи анализа численных данных и графов. Оценки качества алгоритмов будут гарантированы математическими доказательствами.