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

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

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

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

Экзамен состоится в воскресенье 17 мая 2015 года. Запишитесь на экзамен тут.

Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Лекция 1. Введение в теорию вероятностей и вероятностный метод
(15.02.2015 - 11:15 - 12:50)

Вероятностное пространство. Простейшие свойства вероятности. Вероятностный метод. Эффективная монотонная схема для функции голосования. Линейность математического ожидания. Набор, выполняющий 7/8 дизъюнктов, неравенство Маркова.

https://www.youtube.com/watch?t=20&v=T8BUOmE05m4
2. Лекция 2. Введение в теорию вероятностей и вероятностный метод
(15.02.2015 - 13:00 - 14:35)

Независимые события и случайные величины, неравенство Чебышева, закон больших чисел для попарно независимых случайных величин, закон больших чисел для t-независимых случайных величин. Закон больших чисел для независимых случайных величин: оценки Чернова-Хоефдинга, объяснение экспоненциальнного убывания через сравнение распределений.

https://www.youtube.com/watch?v=givVwqq1unM
3. Лекция 3. Маленькие k-независимые множества.
(22.02.2015 - 11:15 - 12:50)

Маленькие k-независимые множества и их применение для поиска набора, выполняющего 7/8 дизъюнктов. Конструкция 2-независимого множества. Конструкция k-независимого множества. Матричные конструкции 2-независимых множеств.

https://www.youtube.com/watch?v=yJxZ3zcE3_8
4. Лекция 4. k-независимые хеш-функции и их применения.
(22.02.2015 - 13:00 - 14:35)

Использование матрицы Теплица для построения 2-независимого множества. Семейство k-независимых хеш-функций, конструкции. Основная лемма о хешировании для попарно независимых хеш-функций. Сравнение сложности NP-задач. Приближенный подсчет числа подсказок.

Домашнее задание 1, срок сдачи 15.03.2015 (27 апреля исправлены задачи 6б и 9).

https://www.youtube.com/watch?v=6KBx5oXYSY4
5. Лекция 5. Применения хеш-функций: генерация равномерного распределения на множестве подсказок
(15.03.2015 - 11:15 - 12:50)

Лемма о хешировании для 2t-независимых хеш-функций. Генерация равномерного распределения на множестве подсказок с помощью k-независимых хеш-функций.

https://www.youtube.com/watch?v=6In4kyuNnhc
6. Лекция 6. Немного смещенные распределения
(15.03.2015 - 13:00 - 14:35)

Статистическое расстояние между распределениями. epsilon-смещенные распределения, их расстояние от равномерного. (epsilon, k)-независимые множества.

https://www.youtube.com/watch?v=ksnsm1F20ME
7. Лекция 7. Конструкция и применение немного смещенных распределений
(22.03.2015 - 11:15 - 12:50)

Доказательство существования маленького epsilon-мещенного множества вероятностным методом. Явная конструкция. NP-полнота задачи о выполнимости системы квадратичных уравнений (QE). Сложность приближения задачи MAXQE.

https://www.youtube.com/watch?v=ozczNCebvK4
8. Лекция 8. Анализ Фурье
(22.03.2015 - 13:00 - 14:35)

Представление функций мультилинейными многочленами, существование и единственность. Базис Фурье, скалярное произведение. Плотность распределения. Коэффициенты Фурье плотности k-независимого распределения. Коэффициенты Фурье epsilon-смещенного распределения. BLR-тест функции на линейность.

Домашние задание 2, срок сдачи 12 апреля 2015.

https://www.youtube.com/watch?v=pc_iez5lnW4
9. Лекция 9. Экспандеры и случайные блуждания по экспандерам
(29.03.2015 - 11:15 - 12:50)

Комбинаторный и алгебраические экспандеры. Матрица смежности графа. Лемма о перемешивании. Блуждание по экспандеру, вероятность блуждания по множеству. Аналог оценок Чернова на экспандерах.

https://www.youtube.com/watch?v=-uGju_DFDeU
10. Лекция 10. Сэмплеры
(29.03.2015 - 13:00 - 14:35)

Сэмплеры: наивный сэмплер, попарно-независимый сэмплер, сэмплер,основанный на медиане усреднений.

https://www.youtube.com/watch?v=_7Ei6OTWxpM
11. Лекция 11. Сэмплеры и их применения
(19.04.2015 - 11:15 - 12:50)

Булев сэмплер из экспандера, сэмплер из булева сэмплера. Усредняющие сэмплеры, "самый лучший" сэмплер без графов Рамануджана. Хиттер из сэмплера. Использование сэмплера для понижения ошибки в вероятностных алгоритмах с экономией случайных битов.

https://www.youtube.com/watch?v=CKiYydCzDF8
12. Лекция 12. Экстракторы
(19.04.2015 - 13:00 - 14:35)

Минимальная энтропия, экстракторы, существование экстракторов. Представление источника в виде выпуклой комбинации плоских. Построение экстрактора из усредняющего сэмплера. Экстрактор из случайного блуждания по экспандеру.

Домашнее задание 3, срок сдачи 17 мая 2015 года.

https://www.youtube.com/watch?v=rlDm8pt3hxU
Голосов пока нет
Share |