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

Общая информация
ЛекторД. М. Ицыксон
Семестрвесна 2012
Дата начала19.02.2012
Количество пар12
Язык курсарусский
Lecture notes
Вопросы к экзамену
Видеоhttp://www.lektorium.tv/course/?id=22854
Анонсы
Встреча на сайте T&Phttp://theoryandpractice.ru/courses/8005-veroyatnostnye-metody-v-vychisleniyakh
Анонс habrahabr.ruhttp://habrahabr.ru/events/416/
Аннотация

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

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

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

Вероятностное пространство. Простейшие свойства вероятности. Вероятностный метод. Эффективная монотонная схема для функции голосования. Линейность математического ожидания. Набор, выполняющий 7/8 дизъюнктов, неравенство Маркова. http://www.lektorium.tv/lecture/?id=13567
2. Лекция 2. Введение в теорию вероятностей и вероятностный метод
(19.02.2012 - 13:00 - 14:35)

Независимые события и случайные величины, неравенство Чебышева, закон больших чисел для попарно независимых случайных величин, закон больших чисел для t-независимых случайных величин. Оценки Чернова-Хоефдинга. Маленькие k-независимые множества и их применение для поиска набора, выполняющего 7/8 дизъюнктов. Конструкция 2-независимого множества. http://www.lektorium.tv/lecture/?id=13568
3. Лекция 3. Маленькие k-независимые множества
(26.02.2012 - 15:35 - 17:10)

Конструкция k-независимого множества. Матричные конструкции 2-независимых множеств. Матрицы Теплица. Семейства попарно независимых хеш-функций. http://www.lektorium.tv/lecture/?id=13585
4. Лекция 4. k-независимые хеш-функции и их применения
(11.03.2012 - 18:30 - 20:05)

k-независимые хеш-функции, конструкции. Основная лемма о хешировании для попарно независимых хеш-функций. Лемма о хешировании для 2t-независимых хеш-функций. Сравнение сложности NP-задач. Приближенный подсчет числа подсказок. http://www.lektorium.tv/lecture/?id=13629
5. Лекция 5. Применения хеш-функций: генерация равномерного распределения на множестве подсказок и лемма Вэлианта-Вазирани
(11.03.2012 - 20:15 - 21:50)

Генерация равномерного распределения на множестве подсказок с помощью k-независимых хеш-функций. Лемма Вэлианта-Вазирани. http://www.lektorium.tv/lecture/?id=13630
6. Лекция 6. Немного смещенные распределения
(08.04.2012 - 11:15 - 12:50)

Статистическое расстояние между распределениями. epsilon-смещенные распределения, их расстояние от равномерного. (epsilon, k)-независимые множества. http://www.lektorium.tv/lecture/?id=13720
7. Лекция 7. Немного смещенные распределения
(15.04.2012 - 11:15 - 12:50)

Существование маленького epsilon-смещенного множества, конструкция. Неприближаемость задачи MAXQE. http://www.lektorium.tv/lecture/?id=13738
8. Лекция 8. Экспандеры и блуждания по ним
(22.04.2012 - 11:15 - 12:50)

Комбинаторный и алгебраические экспандеры. Лемма о перемешивании. Блуждание по экспандеру, вероятность блуждания по множеству. Аналог оценок Чернова на экспандерах. http://www.lektorium.tv/lecture/?id=13754
9. Лекция 9. Сэмплеры и хиттеры
(22.04.2012 - 13:00 - 14:35)

Сэмплеры: наивный сэмплер, попарно-независимый сэмплер, медиана из усреднений. Булев сэмплер из экспандера, сэмплер из булева сэмплера. Хиттер из сэмплера. http://www.lektorium.tv/lecture/?id=13755
10. Лекция 10. Экстракторы
(29.04.2012 - 11:15 - 12:50)

Использование сэмплера для понижения ошибки в вероятностных алгоритмах с экономией случайных битов. Усредняющие сэмплеры, "самый лучший" сэмплер без графов Рамануджана. Минимальная энтропия, экстракторы, существование экстракторов. http://www.lektorium.tv/lecture/?id=13763
11. Лекция 11. Конструкция экстракторов. Локальная лемма Ловаса
(13.05.2012 - 11:15 - 12:50)

Представление источника в виде выпуклой комбинации плоских. Построение экстрактора из сэмплера. Локальная лемма Ловаса, ее симметричный вариант, пример о выполнимости формулы в k-КНФ.
12. Лекция 12. Конструктивное доказательство локальной леммы Ловаса
(13.05.2012 - 13:00 - 14:35)

Конструктивный вариант локальной леммы Ловаса, журнал алгоритма, правильные деревья. Процесс Гэлтона-Вэтсона. http://www.lektorium.tv/lecture/?id=13777
Ваша оценка: Пусто Средняя: 4.6 (10 votes)
Share |
Дмитрий Михайлович Ицыксон
Лекция "Вероятностные методы в вычислениях"
Дмитрий Михайлович Ицыксон
Дмитрий Михайлович