Вероятностные методы в вычислениях

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