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

В рамках данного доклада планируется рассмотреть несколько принципиально различных примеров алгоритмов, в которых наличие рандомизации в том или ином виде позволяет добиться существенного ускорения по сравнению со случаем, когда такая рандомизация отсутствует. Все приводимые примеры можно разбить на три категории: детерминированные алгоритмы, применённые к случайным данным; рандомизированные алгоритмы, математическое ожидание времени работы которых для любого входа асимптотически оптимальнее, чем время работы в худшем случае; и, собственно, вероятностные алгоритмы, время работы которых определяется только размеров входных данных, но правильный ответ выдаётся лишь с некоторой константной вероятностью. Приведём некоторые из алгоритмов, которые планируется рассмотреть в докладе:
1. Сортировка последовательности случайных чисел за линейное время.
2. Вычисление результата антагонистической игры для двух игроков на полном двоичном дереве за сублинейное время (без посещения всех листьев).
3. Линейный алгоритм проверки непустоты пересечения множества полуплоскостей.
4. Алгоритм Каргера-Штайна поиска глобального минимального разреза.
5. Задача о поиске свидетелей булева умножения при перемножении двух булевых матриц.