Лекция 7. Локальная лемма Ловаса

https://compscicenter.ru/

Лекция №7 курса «Рандомизированные алгоритмы», весна 2021 (Новосибирск).

В контексте вероятностного метода локальная лемма Ловаса позволяет нам доказать, что конкретное множество нежелательных событий можно избежать, если каждое из них достаточно невероятно и каждое из них зависит от немногих других событий.

Мы с помощью локальной леммы Ловаса покажем, что маленькие формулы в конъюнктивной нормальной форме всегда выполнимы и как подобрать коммуникационные пути между парами узлов в коммуникационной сети.

Преподаватель курса: Рене Андреасович ван Беверн, заведующий лабораторией алгоритмики ММФ НГУ, старший преподаватель ММФ НГУ.

Подробное описание занятия: https://nsk.compsciclub.ru/courses/rand-algorithms/2021-spring/classes/7177/

Видео Лекция 7. Локальная лемма Ловаса канала Computer Science Center