# Zkouška - Hric 1.2.2018

<{ForumPost(poster="TomRiddle", timestamp=2018-02-02 11:22:43)}>
1.  Popište jednu fázi Dinitzova algoritmu, odhadněte a dokažte její časovou složitost.
1.  Popište invariant zpětné funkce f ve vyhledávacím stroji u Aho-Corrasicka a dokažte, že platí.
1.  Sestrojte síť na násobení 2 n-bitových čísel v polylogaritmickám čase (O(log^k(n), pro nějaké pevné k).
1.  
    1. Definujte poměrovou a relativní poměrovou chybu.
    1.  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.

<{/ForumPost}>