На этой лекции оценим вероятность ошибки алгоритма Карпа-Рабина для поиска подстроки. Для этого ознакомимся с полиномиальнми скользящими хэщ-функциями, который в принципе пригодны для хэширования строк.

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