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

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

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

Описание

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