Город: Тест Санкт-Петербург Новосибирск Казань Язык: Русский English

Вероятностный метод и дерандомизация
Рандомизированные алгоритмы

Что: Лекция
Когда: Среда, 17 марта 2021, 14:10–15:45
Где: НГУ, ауд. 5210, НГУ, новый корпус

Описание

В этой лекции поглубже познакомимся с вероятностным методом доказательства: доказав, что случайно выбранный объект удовлетворяет некоторому свойству с ненулевой вероятностью, можно доказать, что такой объект существует. Однако это ещё не говорит о том, как такой объект эффективно построить. Мы посмотрим, как строить такие объекты рандомизированными алгоритмами и впервые обсуждаем дерандомизацию алгоритмов --- то есть превращение рандомизированного алгоритма в детерминированного, когда это возможно и какой ценой.