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

Probabilistic methods in computations
Saint Petersburg / spring 2015, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

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

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

Date and time Class|Name Venue|short Materials
15 February
11:15–12:50
Введение в теорию вероятностей и вероятностный метод, Lecture ПОМИ РАН video
15 February
13:00–14:35
Введение в теорию вероятностей и вероятностный метод, Lecture ПОМИ РАН video
22 February
11:15–12:50
Маленькие k-независимые множества, Lecture ПОМИ РАН video
22 February
13:00–14:35
k-независимые хеш-функции и их применения, Lecture ПОМИ РАН video,  files
15 March
11:15–12:50
Применения хеш-функций: генерация равномерного распределения на множестве подсказок, Lecture ПОМИ РАН video
15 March
13:00–14:35
Немного смещенные распределения, Lecture ПОМИ РАН video
22 March
11:15–12:50
Конструкция и применение немного смещенных распределений, Lecture ПОМИ РАН video
22 March
13:00–14:35
Анализ Фурье, Lecture ПОМИ РАН video,  files
29 March
11:15–12:50
Экспандеры и случайные блуждания по экспандерам, Lecture ПОМИ РАН video
29 March
13:00–14:35
Сэмплеры, Lecture ПОМИ РАН video
19 April
11:15–12:50
Сэмплеры и их применения, Lecture ПОМИ РАН video
19 April
13:00–14:35
Экстракторы, Lecture ПОМИ РАН video,  files