# Úvod do aprox. a pravděp. alg. - Sgall - 30.12.2020

<{ForumPost(poster="Katterrina", timestamp=2021-01-10 11:22:01)}>
Zkouška byla ústní. Dostala jsem dvě otázky s tím, že mám 15 minut na přípravu, myslím ale, že jsem se nakonec připravovala déle.  
  
První otázka byla na SAT, popsat a dokázat algoritmus LP-SAT, později se pan Sgall doptával na BEST-SAT a další algoritmy, které byly na přednášce.  
Druhá otázka byla na jakési lemma, které se mělo probírat na poslední přednášce (v té době ještě neproběhla). U něj jsem musela přiznat, že vůbec netuším, protože ta přenáška ještě nebyla a v poznámkách k přednášce také není (a hledat dopředu v nějaké jiné literatuře mě nenapadlo, prý by to bylo v knize [http://www.designofapproxalgs.com/](http://www.designofapproxalgs.com/)). Pan Sgall byl ale milý a dal mi jako náhradní otázku zformulovat a dokázat takové to lemma o polynomech Pr\[P(r1,...,rn) = 0]≤d/|S|.
<{/ForumPost}>