Лекция 9. Полиномиальные скользящие хэш-функции, лемма Шварца-Зиппеля

Лекция №9 курса «Рандомизированные алгоритмы», весна 2021 (Новосибирск). На этой лекции оценим вероятность ошибки алгоритма Карпа-Рабина для поиска подстроки. Для этого ознакомимся с полиномиальнми скользящими хэш-функциями, который в принципе пригодны для хэширования строк. На этой лекции увидим простой алгоритм для проверки, существует ли в графе совершенное паросочетание. Он поддаётся массовому распараллеливанию. На его основе лежит лемма Шварца-Зиппеля, с помощью которой можно построить эффективный рандомизированный алгоритм для проверки тождественности полиномов. Много рандомизированных алгоритмов полагается на этой лемме, которую до сих пор неизвестно как дерандомизировать Преподаватель курса: Рене Андреасович ван Беверн, заведующий лабораторией алгоритмики ММФ НГУ, старший преподаватель ММФ НГУ. Подробное описание занятия: