Евстропов Г.О. “Обзорный доклад по вероятностным алгоритмам“

Аннотация: В рамках данного доклада планируется рассмотреть несколько принципиально различных примеров алгоритмов, в которых наличие рандомизации в том или ином виде позволяет добиться существенного ускорения по сравнению со случаем, когда такая рандомизация отсутствует. Все приводимые примеры можно разбить на три категории: детерминированные алгоритмы, применённые к случайным данным; рандомизированные алгоритмы, математическое ожидание времени работы которых для любого входа асимптотически оптималь