Comment estimer combien d'affectations satisfont une formule DNF donnée à l'aide de Monte Carlo?

Question

Certes, les devoirs.

Aux fins de cette question: $ phi $ est une formule DNF similaire à celle: $ (x_1 wedge neg x_3 wedge x_4) vee ( neg x_1 wedge x_2) $ aussi $ c_i $ est une clause Dans cette formule, par exemple $ c_1 = x_1 wedge neg x_3 wedge x_4 $

Les tâches consistent à le faire de manière un peu plus sophistiquée que de choisir une affectation aléatoire, voir si elle satisfait la formule, répétez n fois. Plus précisément, les tâches nous disent de:

• Uniformément au hasard, choisissez une clause $ c_i $ dans $ phi $.
• Définissez les valeurs des variables dans $ c_i $ pour que $ c_i $ soit satisfait.
• Définissez les valeurs des variables restantes au hasard.
• De cette manière, l'échantillon ne satisfait que les affectations et les échantillonnera tous.

Je ne comprends pas: tous? Si je veux goûter toutes les missions satisfaisantes, je ne suis pas à l'échantillonnage, mais plutôt je compte?

De plus, la tâche demande:

• Pour une affectation donnée $ p_i $ Quelle est la probabilité d'échantillonnage $ p_i $? C'est une question facile: $ frac1 {2 ^ {nm}} $ où $ n $ est le nombre ou des variables distinctes dans $ phi $ et $ m $ est le nombre de variables dans $ c_i $. Ou ai-je tort?
• Comment pouvez-vous utiliser le résultat de la question précédente (la question précédente était de goûter trivialement comme je l'ai décrit ci-dessus) pour construire une estimation du nombre de missions satisfaisantes? Je ne sais pas.

Eh bien, je peux vérifier si cette affectation aléatoire satisfait d'autres clauses que $ c_i $. Mais comment puis-je utiliser le résultat?

Mon Google a donné cette page: http://theoryapp.com/dnf-counting-and-the-monte-carlo-method/ Mais c'est encore plus déroutant pour moi. Au lieu de choisir la clause $ c_i $ uniformément, le site nous dit de "prendre une clause $ c_i $ avec probabilité $ p_i = frac { Left | s_i droite |} { sum_ {j = 1} {l} Left | s_j droite |} $, où $ s_i $ est la collection de missions satisfaisant $ c_i $ et $ l $ est le montant des clauses dans $ phi $, puis ramassez une affectation de $ s_i $. " Mais ensuite, on nous dit de "vérifier si cette affectation satisfait à $ phi $. C'est un non-sens, chaque affectation qui satisfait la clause $ c_i $ pour tout $ i $ doit satisfaire toute la formule?

Certes, ce cours de base sur la probabilité et les statistiques est le premier cours où je me sens comme un idiot total.

Des conseils? Je perds l'espoir de pouvoir comprendre cela par moi-même.

Enfin, je ne suis pas sûr, cette question est-elle plus appropriée sur scicomp.stackexchange.com?