Popište algoritmus Aho-Corasickové, dokažte jeho správnost a rozeberte časovou
složitost. [10]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]Navrhněte hradlovou síť, která zjistí, zda je zadané n-bitové dvojkové číslo
dělitelné třemi. [5](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í:
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ů
Ford-Fulkerson na grafu kde u = zdroj, v = stok, každá hrana má kapacitu 1, složitost O(|E|*f), f ... velikost max toku
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))
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