od TomRiddle » 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.
[list=1]
[*] 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).
[*] [list=a][*]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.[/list][/list]