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

Доказательство локальной леммы Ловаса, поиск подсроки алгоритмом Карпа-Рабина
Randomized Algorithms

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

Description

В этой лекции докажем локальную лемму Ловаса и посмотрим ещё примеры для её применения. Потом откроем серию лекций об алгоритмических подходах к построению рандомизированных алгоритмов. Для начала рассматриваем алгоритм Карпа-Рабина для поиска слова в тексте. Главные преимущества данного алгоритма являются его простота, возможность легко обобщить для поиска двухмерного образца в двухмерных данных (например, подматрицы), и что искать можно несколько слов одновременно, не увеличивая при этом трудоёмкость алгоритм.