Zaawansowane algorytmy i struktury danych/Ćwiczenia 15

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zadanie 1

Udowodnij lemat Zuppela-Schwartca podany poniżej.

Lemat [Zippela-Schwartza]

Niech będzie niezerowym wielomianem zmiennych stopnia nad ciałem . Niech będzie skończonym podzbiorem oraz niech będą losowymi elementami z , wtedy:
Rozwiązanie

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