MAX-SAT: дерандомизация/Задачи/ex-derand-maxsat-f0-f1 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: добавление Категория:Теоретические задачи)
 
(не показано 14 промежуточных версий 2 участников)
Строка 4: Строка 4:
 
</latex>
 
</latex>
  
[[Category:На проверку]]
+
 
 
<!--Вообще-то, решения уже есть-->
 
<!--Вообще-то, решения уже есть-->
  
===Стенина Мария, группа 974===
+
[[Категория:Решенные задачи]]
 
+
[[Категория:Теоретические задачи]]
<latex>
+
Организуем вычисления следующим образом. После получения решения задачи линейной релаксации $(p_1, \ldots, p_n)$ заполним две таблицы. Первую назовем $C$, она будет содержать $m$ строк и $n$ столбцов. Каждая строка будет соответствовать одной скобке. В ячейке $(j, k)$ будет записана 1, если в $j$-тую скобку входит $x_k$, 0, если в $j$-тую скобку входит $\bar{x}_k$, и "-", если $k$-тая переменная не входит в $j$-тую скобку. Заполнение такой таблицы, очевидно, займет время $O(nm)$. Вторую таблицу назовем $P$, она будет содержать один столбец длины $m$. В каждой ячейке будет записана $P_j$, которую вычислим по формуле
+
$$
+
    P_j = \prod_{k:C_{jk}=1} (1-p_k) \prod_{k:C_{jk}=0} p_k.
+
$$
+
Заполнение этой таблицы тоже займет время не более $O(nm)$.
+
 
+
Далее на каждой итерации будем производить следующие действия. Обозначим номер итерации $k$.
+
$$
+
    P^0 = P;
+
$$
+
для всех $j = 1, \ldots, m$
+
$$
+
  \text{если } C_{jk} = 0, \text{то } P^0_j = 0;
+
$$
+
$$
+
  \text{если } C_{jk} = 1, \text{то } P^0_j = P^0_j / p_k;
+
$$
+
$$
+
    P^1 = P;
+
$$
+
для всех $j = 1, \ldots, m$
+
$$
+
  \text{если } C_{jk} = 1, \text{то } P^0_j = 0;
+
$$
+
$$
+
  \text{если } C_{jk} = 0, \text{то } P^0_j = P^0_j / p_k;
+
$$
+
Все эти манипуляции занимают время $O(m)$. Далее
+
$$
+
    f_0 = \sum_{j=1}^m P^0_j, \quad f_1 = \sum_{j=1}^m P^1_j.
+
$$
+
Это тоже $O(m)$. Ну и наконец, если $f_0 < f_1$, то $P = P^0$, иначе $P = P^1$. Это можно реализовать за $O(1)$.
+
 
+
Итого имеем заполнение двух таблиц за $O(nm)$ и $n$ итераций по $O(m)$, значит всего $O(nm)$, что и требовалось.
+
</latex>
+

Текущая версия на 06:50, 4 мая 2023