MAX-SAT: вероятностное округление/Задачи/eupce-6-1-a — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «{{проверено|}} <!-- Probability and Computing --> Рассмотрим K-ESAT, SAT, когда в каждой скобке ровно k литерало…») |
StasFomin (обсуждение | вклад) (тотальный сброс резервирования) |
||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 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> скобок, и проанализируйте матожидание его времени выполнения. | ||
| + | |||
[[Категория:Теоретические задачи]] | [[Категория:Теоретические задачи]] | ||
Текущая версия на 12:58, 25 сентября 2025
Рассмотрим K-ESAT, SAT, когда в каждой скобке ровно k литералов.
Предложите Лас-Вегас алгоритм выполняющий минимум скобок, и проанализируйте матожидание его времени выполнения.