Адрес e-mail:

Псевдослучайность и дерандомизация (Д.В. Мусатов, осень 2019)

Лектор - Д.В. Мусатов


Время и место: четверг 16:00 - 17:30, ШАД, Сорбона, первое занятие: 5 сентября.

Аннотация

Для некоторых задач известны быстрые вероятностные алгоритмы, но неизвестно быстрых детерминированных. Что это - неотъемлемое свойство этих задач, или просто никто не смог придумать нужный алгоритм? Можно ли хотя бы сократить необходимое число случайных битов, не сильно замедлив работу? Краткий ответ таков: большинство учёных верит, что все алгоритмы можно дерандомизировать, т.е. избавиться от вероятности, но доказывать это не умеют. В курсе будет дан развёрнутый ответ: мы познакомимся с различными техниками дерандомизации, способами построения псевдослучайных объектов и их использования в алгоритмах. Будет рассказано о причинах уверенности учёных и препятствиях к построению доказательства.
Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

МФТИ в социальных сетях