Вероятность в алгоритмах, 16 марта 2013

Заместитель директора отделения Computer Science Школы Анализа Данных, руководитель группы разработки компании «Яндекс», доцент базовой кафедры Яндекса НИУ ВШЭ, ассистент кафедры математической логики и теории алгоритмов МГУ, кандидат физико-математических наук.

Многие алгоритмы являются детерминированными – то есть последовательность их действий зависит лишь от входных данных и программы. Но что будет, если разрешить алгоритму по ходу работы использовать случайные числа?

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

Обо всём этом мы и поговорим на лекции.