Вероятностные методы в вычислениях Год выпуска: 2015 Производитель: lektorium.tv Сайт производителя: www.lektorium.tv Автор: Дмитрий Ицыксон Продолжительность: 08:28:27 Тип раздаваемого материала: Видеоурок Язык: Русский Описание: Вероятностные конструкции и рассуждения очень часто используются в различных разделах теоретической информатики: при построении и анализе алгоритмов, в теории кодирования, в теории сложности, вычислительной криптографии и пр. В курсе мы познакомимся с основными вероятностными методами, которые применяются в теоретической информатике, и продемонстрируем эти методы на различных интересных примерах. В курсе будет много результатов из различных областей теоретической информатики, но акцент будет сделан на методы. Не все рассмотренные в курсе результаты будут вероятностными, иногда вероятность используется неявно. Акцент будет сделан на построение и использование псевдослучайных конструкций, таких как как независимое множество, попарно-независимые хеш-функции, сэмплеры, хиттеры, экспандеры, экстракторы, смещенное множество. Для понимания курса требуется знание основ алгебры (многочлены, поля, линейные пространства, собственные числа), знание основ теории вероятностей будет полезно, но все нужные понятия и факты из теории вероятностей будут напоминаться по мере необходимости. Содержание курса основано на курсе О. Голдрейха Randomized methods in computations.
Содержание
Лекция 1. Введение в теорию вероятностей и вероятностный метод. Лекция 2. Введение в теорию вероятностей и вероятностный метод. Лекция 3. Маленькие k-независимые множества. Лекция 4. k-независимые хеш-функции и их применения. Лекция 5. Применения хеш-функций: генерация равномерного распределения на множестве подсказок. Лекция 6. Немного смещенные распределения.
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum You cannot attach files in this forum You can download files in this forum
![[Quote]](./templates/default/images/lang/en/icon_quote.gif "Reply with quote"){kind=icon}
![[Profile]](./templates/default/images/lang/en/icon_profile.gif "View user's profile"){kind=icon}
![[PM]](./templates/default/images/lang/en/icon_pm.gif "Send private message"){kind=icon}
