Zaawansowane algorytmy i struktury danych/Ćwiczenia 15

From Studia Informatyczne

Zadanie 1

Udowodnij lemat Zuppela-Schwartca podany poniżej.

Lemat [Zippela-Schwartza]

Niech p(x_1,\ldots, x_n) będzie niezerowym wielomianem n zmiennych stopnia d nad ciałem F. Niech S będzie skończonym podzbiorem F oraz niech r_1,\ldots, r_n będą losowymi elementami z S, wtedy:
\Pr[p(r_1,\ldots,r_n)=0] \le \frac{d}{|S|}.

Rozwiązanie

Dowód

Dowód lematu przeprowadzimy przez indukcję po n. Dla n=1 wielomian p może mieć co najwyżej d zer, co daje podstawę indukcji. Załóżmy teraz, że lemat ten zachodzi dla wszystkich wielomianów nad n-1 zmiennymi. Możemy wtedy zapisać p jako wielomian x_1:
p(x_1,\ldots,x_n) = \sum_{i=0}^d x_i^d p_i(x_2,\ldots,x_n).

Ponieważ p nie jest zerowy, to istnieje takie i dla którego p_i nie jest zerowy. Weźmy największe takie i. Wtedy \deg p_i \le  d-i. Wybierzmy teraz losowo elementy r_2,\ldots, r_n z S. Z hipotezy indukcyjnej mamy:

\Pr[p_i(r_2,\ldots,r_n)=0] \le \frac{d-i}{|S|}.

Jeżeli p_i(r_2,\ldots,r_n) \neq 0, to wtedy p(x_1,r_2,\ldots,r_n) ma stopień i, a więc

\Pr[p(r_1,r_2,\ldots,r_n)=0 | P_i(r_2,\ldots,r_n) \neq 0] \le \frac{i}{|S|}.

Mamy więc:

\begin{array}{r@{}c@{}l} \Pr[p(r_1,r_2,\ldots,r_n)=0] &=&\\  &=& \Pr[P_i(r_2,\ldots,r_n) = 0] \Pr[p(r_1,r_2,\ldots,r_n)=0 | P_i(r_2,\ldots,r_n) = 0] +\\&+&  \Pr[P_i(r_2,\ldots,r_n) \neq 0] \Pr[p(r_1,r_2,\ldots,r_n)=0 | P_i(r_2,\ldots,r_n) \neq 0]\le\\ &\le&  \Pr[P_i(r_2,\ldots,r_n) = 0] + \Pr[p(r_1,r_2,\ldots,r_n)=0 | P_i(r_2,\ldots,r_n) \neq 0] \le\\ &\le& \frac{d-i}{|S|} + \frac{i}{|S|} = \frac{d}{|S|}. \end{array}
image:End_of_proof.gif

Zadanie 2

Masz daną formułę logiczną w postaci DNF. Zaproponuj efektywny algorytm losowego generowania z rozkładem jednostajnym wartościowań ją spełniających?


Rozwiązanie


Zadanie 3


Rozwiązanie