Zaawansowane algorytmy i struktury danych/Ćwiczenia 15

Zadanie 1

Udowodnij lemat Zuppela-Schwartca podany poniżej.

Lemat [Zippela-Schwartza]

Niech $p(x_1,\dots ,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,\dots ,r_n$ będą losowymi elementami z $S$, wtedy:

$\mathrm{Pr}[p(r_1,\dots ,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,\dots ,x_n)=\sum _{i=0}^d{x}_i^d{p}_i(x_2,\dots ,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 $\mathrm{deg}{p}_i\le d-i$. Wybierzmy teraz losowo elementy $r_2,\dots ,r_n$ z $S$. Z hipotezy indukcyjnej mamy:

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

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

$\mathrm{Pr}[p(r_1,r_2,\dots ,r_n)=0|P_i(r_2,\dots ,r_n)\ne 0]\le \frac{i}{|S|}.$

Mamy więc:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \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} }

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