Сайт в процессе наполнения. Архив всех прошедших курсов доступен на старой версии сайта по адресу old.compsciclub.ru
Город: Санкт-Петербург Казань Язык: Русский 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
Экстракторы, лекция ПОМИ РАН видеофайлы
15 июня 2015

Оценка за курс «Вероятностные методы в вычислениях»

Добрый день!

Если вы сдаёте или уже сдали курс «Вероятностные методы в вычислениях», напишите о состоянии сдачи на curators@compscicenter.ru. Если вы передумали сдавать этот курс, отпишитесь от него, пожалуйста, на сайте.

Катя Лебедева