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

Вероятностные методы в вычислениях
Санкт-Петербург / весна 2015, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

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

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

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

Дата и время Занятие Место Материалы
15 февраля
11:15–12:50
Введение в теорию вероятностей и вероятностный метод, Лекция ПОМИ РАН видео
15 февраля
13:00–14:35
Введение в теорию вероятностей и вероятностный метод, Лекция ПОМИ РАН видео
22 февраля
11:15–12:50
Маленькие k-независимые множества, Лекция ПОМИ РАН видео
22 февраля
13:00–14:35
k-независимые хеш-функции и их применения, Лекция ПОМИ РАН видео,  файлы
15 марта
11:15–12:50
Применения хеш-функций: генерация равномерного распределения на множестве подсказок, Лекция ПОМИ РАН видео
15 марта
13:00–14:35
Немного смещенные распределения, Лекция ПОМИ РАН видео
22 марта
11:15–12:50
Конструкция и применение немного смещенных распределений, Лекция ПОМИ РАН видео
22 марта
13:00–14:35
Анализ Фурье, Лекция ПОМИ РАН видео,  файлы
29 марта
11:15–12:50
Экспандеры и случайные блуждания по экспандерам, Лекция ПОМИ РАН видео
29 марта
13:00–14:35
Сэмплеры, Лекция ПОМИ РАН видео
19 апреля
11:15–12:50
Сэмплеры и их применения, Лекция ПОМИ РАН видео
19 апреля
13:00–14:35
Экстракторы, Лекция ПОМИ РАН видео,  файлы