City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Нижние оценки трудоёмкости рандомизированных алгоритмов -- принцип Яо
Randomized Algorithms

What: Lecture
When: Wednesday, 12 May 2021, 14:10–15:45
Where: НГУ, ауд. 5210, НГУ, новый корпус

Description

На этой лекции ознакомимся с принципом Яо, который гласит, что ожидаемое время работы рандомизированного алгоритма в худшем случае не меньше, чем ожидаемое время работы наилучшего детерминированного алгоритма на наихудшем распределении на входных данных. Мы его используем для доказательства нижних оценок трудоёмкости рандомизированных алгоритмов для упорядочивания массива и распознавания планарных графов.