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

<{ForumPost(poster="Erim", timestamp=2014-12-18 12:44:42)}>
**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
<{/ForumPost}>

<{ForumPost(poster="Pavel Brožek", timestamp=2015-01-11 21:33:54)}>
2) Nebylo ještě v zadání, že ten graf je acyklický?
<{/ForumPost}>

<{ForumPost(poster="Erim", timestamp=2015-01-12 20:54:05)}>

 > 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.
<{/ForumPost}>

<{ForumPost(poster="Pavel Brožek", timestamp=2015-01-14 00:58:49)}>
Shodou okolností jsem u zkoušky dostal přesně tohle zadání a skutečně v zadání bylo, že je graf acyklický :)
<{/ForumPost}>