MAX-SAT: вероятностное округление/Задачи/MAX-SAT-random-t-samples — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 7: Строка 7:
 
Какова вероятность, что будет выполнено более половины скобок?
 
Какова вероятность, что будет выполнено более половины скобок?
  
[[Категория:На проверку]]
+
[[Category:Решенные задачи]]
 
+
===Стенина Мария, группа 974===
+
 
+
<latex>
+
Оценим вероятность, что после $t$ выборов выполнено не более половины скобок. Это значит, что каждый выбранный набор переменных обеспечивает выполнение не более $\frac{m}{2}$ скобок.
+
Обозначим количество итераций $\alpha = \mathbb{P}(\sum\limits_{i=1}^m z_i \leq \frac{m}{2})$, где $z_i$ --- значение $i$-той скобки (0 или 1).
+
Теперь оценим $\alpha$. Пусть $i$-тая скобка содержит $k_i$ литералов. Чтобы значение скобки было равно нулю, необходимо, чтобы значения всех литералов были равны нулю. Вероятность такого события $2^{-k_i}$. Следовательно, вероятность $\mathbb{P}(z_i = 0) \leq \frac{1}{2}$. Если предположить, что все $z_i$ независимые случайные величины, то $\alpha = \mathbb{P}(\sum\limits_{i=1}^m z_i \leq \frac{m}{2}) \leq \frac{1}{2}$. Если же $z_i$ зависимы, то из неравенства $\mathbb{P}(A, B) \leq \mathbb{P}(A) + \mathbb{P}(B)$ получаем ту же оценку на $\alpha$. Отсюда имеем оценку вероятности выполнения не более половины скобок не больше $2^{-t}$. Поэтому искомая вероятность не меньше, чем $1 - 2^{-t}$.
+
</latex>
+

Версия 10:10, 24 декабря 2014

Рассмотрим следующий алгоритм для задачи MAX-SAT.

  • t раз, случайно (равномерное распределение) выбираем набор — значения переменных
  • выбираем лучший результат

Какова вероятность, что будет выполнено более половины скобок?