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

Probabilistic methods in computations


Вероятностные конструкции и рассуждения очень часто используются в различных разделах теоретической информатики: при построении и анализе алгоритмов, в теории кодирования, в теории сложности, вычислительной криптографии и пр. В курсе мы познакомимся с основными вероятностными методами, которые применяются в теоретической информатике, и продемонстрируем эти методы на различных интересных примерах. В курсе будет много результатов из различных областей теоретической информатики, но акцент будет сделан на методы. Не все рассмотренные в курсе результаты будут вероятностными, иногда вероятность используется неявно. Акцент будет сделан на построение и использование псевдослучайных конструкций, таких как как \(k\)-независимое множество, попарно-независимые хеш-функции, сэмплеры, хиттеры, экспандеры, экстракторы, \(\epsilon\)-смещенное множество. Для понимания курса требуется знание основ алгебры (многочлены, поля, линейные пространства, собственные числа), знание основ теории вероятностей будет полезно, но все нужные понятия и факты из теории вероятностей будут напоминаться по мере необходимости.

Содержание курса основано на курсе О. Голдрейха Randomized methods in computations.

Страница курса 2012 года.

Course Offerings

Semester Branch
spring 2015 Saint Petersburg
spring 2012 Saint Petersburg