City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

From compact representations to algorithms for big data


В курсе будет рассказано про несколько красивых математических идей, широко используемых в современных (теоретических и практических) алгоритмах для обработки больших данных. Мы (поверхностно) затронем четыре больших раздела:

  • Понижение размерности (dimensionality reduction): как отобразить точки в многомерном пространстве в маломерное пространство, теряя как можно меньше информации?
  • Алгоритмы обработки потоковых данных (streaming algorithms): как оценить количество различных слов в большом тексте, храня маленькое количество информации (несколько сотен байт)?
  • Вероятностные алгоритмы линейной алгебры для больших матриц (randomized linear algebra): как быстро решить задачу о наименьших квадратах для матрицы размера 1 000 000 000 на 1000?
  • Поиск похожих объектов (similarity search): как быстро найти картинку (текст, и т. д.) в большой базе данных, которая наиболее похожа на картинку-запрос?

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

    От слушателей потребуется знание основ теории вероятностей и линейной алгебры. В зависимости от интереса, возможно разное соотношение теоретического и практического материала.

  • Course Offerings

    Semester Branch
    spring 2016 Saint Petersburg