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

Рандомизированный подсчёт
Рандомизированные алгоритмы

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

Описание

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