Zkouška 16.12. 2020 - Hubička

Pokračování přednášky TIN060 Algoritmy a datové struktury I
lukascaha
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 24. 1. 2019 20:06
Typ studia: Informatika Bc.

Zkouška 16.12. 2020 - Hubička

Příspěvek od lukascaha »

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
Odpovědět

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