Zaawansowane algorytmy i struktury danych/Ćwiczenia 15

Z Studia Informatyczne
< Zaawansowane algorytmy i struktury danych
Wersja z dnia 13:31, 29 wrz 2006 autorstwa Sank (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
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