Zkouška 23. 01. 2015 Čepek
Napsal: 23. 1. 2015 14:31
1) Aho-Corasick:
Slova: {auto, automobil, automat, tomato}
Nakreslete graf znázorňující stavy a přechodovou funkci. Zpětnou a výstupní fci zapište tabulkou.
2) Problém batohu
v1, ..., vn velikosti předmětů
c1, ..., cn ceny předmětů
k kapacita batohu
r požadovaná cena
Problém BAT: Existuje podmnožina předmětů, jejíž celková cena je alespoň r a vejdou se do batohu?
Otázka: Je tato úloha NP-úplná? Dokažte pomocí nějaké úlohy, kterou jsme brali na přednášce (KLIKA, SP, ROZ, ....)
3) Hranová souvislost
Označme HS(G) hranovou souvislost grafu G. HS(G) je minimální počet hran, po jejichž odebrání bude graf G nesouvislý.
Napište algoritmus hledající HS(G) v polynomiálním čase vzhledem k velikosti dat takový, že jako podprogram bude využívat nějaký algoritmus hledání maximálního toku v síti (nezajímá nás jaký konkrétní). Zdůvodněte korektnost.
Napište časovou složitost vlastních operací algoritmu a počet, kolikrát se spustí podprogram hledání maximálního toku.
U ústní co jsem slyšel:
definice P, NP, nějaký převod mezi problémy
preflow-push
RSA
Slova: {auto, automobil, automat, tomato}
Nakreslete graf znázorňující stavy a přechodovou funkci. Zpětnou a výstupní fci zapište tabulkou.
2) Problém batohu
v1, ..., vn velikosti předmětů
c1, ..., cn ceny předmětů
k kapacita batohu
r požadovaná cena
Problém BAT: Existuje podmnožina předmětů, jejíž celková cena je alespoň r a vejdou se do batohu?
Otázka: Je tato úloha NP-úplná? Dokažte pomocí nějaké úlohy, kterou jsme brali na přednášce (KLIKA, SP, ROZ, ....)
3) Hranová souvislost
Označme HS(G) hranovou souvislost grafu G. HS(G) je minimální počet hran, po jejichž odebrání bude graf G nesouvislý.
Napište algoritmus hledající HS(G) v polynomiálním čase vzhledem k velikosti dat takový, že jako podprogram bude využívat nějaký algoritmus hledání maximálního toku v síti (nezajímá nás jaký konkrétní). Zdůvodněte korektnost.
Napište časovou složitost vlastních operací algoritmu a počet, kolikrát se spustí podprogram hledání maximálního toku.
U ústní co jsem slyšel:
definice P, NP, nějaký převod mezi problémy
preflow-push
RSA