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

[Katterrina]

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/). 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|.