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

Генерируй и меняй, локальная лемма Ловаса
Рандомизированные алгоритмы

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

Описание

В этой лекции сначала увидим ещё больше примеров применения вероятностного подхода. Применяя аргументы, основывающиеся на математическом ожидании, докажем нижнюю оценку на число пересечений рёбер в рисунке графа на плоскости. С помощью подхода генерируй и меняй докажем нижнюю оценку на мощность наибольшего независимого множества в графе.

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