MAX-SAT: вероятностное округление/Задачи/eupce-6-1-a — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «{{проверено|}} <!-- Probability and Computing --> Рассмотрим K-ESAT, SAT, когда в каждой скобке ровно k литерало…») |
|||
| Строка 5: | Строка 5: | ||
Предложите [https://ru.wikipedia.org/wiki/%D0%9B%D0%B0%D1%81-%D0%92%D0%B5%D0%B3%D0%B0%D1%81_(%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC) Лас-Вегас алгоритм] выполняющий минимум | Предложите [https://ru.wikipedia.org/wiki/%D0%9B%D0%B0%D1%81-%D0%92%D0%B5%D0%B3%D0%B0%D1%81_(%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC) Лас-Вегас алгоритм] выполняющий минимум | ||
<m>m(1-2^{-k})</m> скобок, и проанализируйте матожидание его времени выполнения. | <m>m(1-2^{-k})</m> скобок, и проанализируйте матожидание его времени выполнения. | ||
| + | {{reserve-task|[[Участник:NikitaAkshaev|NikitaAkshaev]] 11:28, 18 декабря 2024 (UTC)}} | ||
[[Категория:Теоретические задачи]] | [[Категория:Теоретические задачи]] | ||
Текущая версия на 11:28, 18 декабря 2024
Рассмотрим K-ESAT, SAT, когда в каждой скобке ровно k литералов.
Предложите Лас-Вегас алгоритм выполняющий минимум скобок, и проанализируйте матожидание его времени выполнения.
Задача зарезервирована: NikitaAkshaev 11:28, 18 декабря 2024 (UTC)