City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Полиномиальные скользящие хэш-функции, параллельный алгоритм для существования совершенного паросочетания
Randomized Algorithms

What: Lecture
When: Wednesday, 14 April 2021, 14:10–15:45
Where: НГУ, ауд. 5210, НГУ, новый корпус

Description

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

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