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

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

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

Описание

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