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