Zkouška - Hric 1.2.2018

Pokračování přednášky TIN060 Algoritmy a datové struktury I
TomRiddle
Matfyz(ák|ačka) level I
Příspěvky: 4
Registrován: 5. 6. 2017 18:05
Typ studia: Informatika Bc.

Zkouška - Hric 1.2.2018

Příspěvek od TomRiddle »

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

Zpět na „TIN061 Algoritmy a datové struktury II“