Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

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

Что: Лекция
Когда: Среда, 14 апреля 2021, 18:10–19:45
Где: НГУ, ауд. 5210, НГУ, новый корпус

Описание

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

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