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

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

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

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

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