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

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

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

Описание

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