Zkouška - 18. 12. 2014 - Čepek

Zkouška 18. 12. 2014

1) Aho-Corasick:

Slova: {okolo, lom, luk, omyl}
Nakreslete graf znázorňující stavy a přechodovou funkci. Zpětnou a výstupní fci zapište tabulkou.

2) Minimální pokrytí grafu pomocí orientovaných cest

G = (V, E) acyklický orientovaný graf

Problém: Najděte polynomiální algoritmus, který v G nalezne minimální počet vrcholově disjunktních orientovaných cest, které pokryjí všechny vrcholy G.

3) Hamiltonovská cesta

G = (V, E) neorientovaný graf
s, k $\in$ V

Problém HC: Existuje v G cesta z s do k, která navštíví každý další vrchol G právě jednou?

Otázka: Je tato úloha NP-úplná? Dokažte pomocí nějaké úlohy, kterou jsme brali na přednášce (KLIKA, HK, TSP, ROZ, ....)

Ústní část:
Třídící sítě - hloubka mergesortu
Toky v sítích - preflow-push algoritmy

2. Nebylo ještě v zadání, že ten graf je acyklický?

Pavel Brožek wrote:2) Nebylo ještě v zadání, že ten graf je acyklický?

Nevzpomínám si, ale nejspíš to bude pravda. Algoritmus, který jsem použil (hledání maximálního toku v bipartitním grafu), by si s cykly neuměl poradit a nenašel by vždy nejmenší pokrytí, přesto mi byl uznán, takže v testu tento předpoklad nejspíš byl.
Díky za otázku, změním první zprávu.

Shodou okolností jsem u zkoušky dostal přesně tohle zadání a skutečně v zadání bylo, že je graf acyklický :)