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

Každý neuvedený předmět
Katterrina
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 23. 6. 2020 16:25
Typ studia: Informatika Bc.

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

Příspěvek od 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|.
Odpovědět

Zpět na „Ostatní“