Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

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


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

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

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

Прочтения курсов

Семестр
весна 2012
весна 2015