# Zkouška 16.12. 2020 - Hubička

<{ForumPost(poster="lukascaha", timestamp=2020-12-16 12:26:25)}>
1. Popište algoritmus Aho-Corasickové, dokažte jeho správnost a rozeberte časovou  
složitost. \[10]  
  
2. Je dán orientovaný graf a jeho vrcholy u, v. Chceme nalézt co nejvíce hranově  
disjunktních cest z u do v. \[5]  
  
3. Navrhněte hradlovou síť, která zjistí, zda je zadané n-bitové dvojkové číslo  
dělitelné třemi. \[5]  
  
4. (Bonusový úkol) EXACTLY-3,3-SAT je SAT, kde každá klauzule obsahuje  
právě 3 různé proměnné a každá proměnná se nachází v právě 3 klauzulích.  
Dokažte, že EXACTLY-3,3-SAT není NP-úplný. \[]  
  
  
Řešení:  
1. Viz. průvodce, složitost je O(H+sum J_i+V), H ... délka sena, J_i ... velikost i-té jehly, V ... počet výskytů  
2. Ford-Fulkerson na grafu kde u = zdroj, v = stok, každá hrana má kapacitu 1, složitost O(|E|*f), f ... velikost max toku  
3. Sečteme cifry na lichých pozicích = L a na sudých pozicích = S, |S-L| musí být dělitelný třemi, použijeme strom sčítaček na liché resp. sudé bity a výsledné dvě čísla odečteme sčítačkou, složitost O(log(n))  
4. Převedu na bipartitní graf, jedna partita jsou literály, druhá partita jsou klauzule, hrana značí zda je literál v klauzuli pozitivní nebo negativní, poté hledám perfektní párování v bipartitním grafu, což je P algoritmus, někde jsem dokonce viděl že EXACTLY-3,3-SAT je vždycky splnitelný a že to lze dokázat pomocí Hallovy věty
<{/ForumPost}>