Zkouška - Hric 1.2.2018
Napsal: 2. 2. 2018 11:22
- Popište jednu fázi Dinitzova algoritmu, odhadněte a dokažte její časovou složitost.
- Popište invariant zpětné funkce f ve vyhledávacím stroji u Aho-Corrasicka a dokažte, že platí.
- Sestrojte síť na násobení 2 n-bitových čísel v polylogaritmickám čase (O(log^k(n), pro nějaké pevné k).
-
- Definujte poměrovou a relativní poměrovou chybu.
- Popište aproximační algoritmus na hledání minimální vertex-cover grafu G s poměrovou chybou 2 a dokažte, že je poměrová chyba skutečně 2.