# Zkouška - Čepek - 11.1.2011

<{ForumPost(poster="istien", timestamp=2011-01-11 18:32:47)}>
Písemka, 3 příklady, 2 hodiny:  
  
1) Aho-Corasickova, slova {auto, automobil, automat, tomato}, grafem znazornit mnozitu stavu a prechodovou funkci, tabulkou zpetnou a vystupni funkci (takze vlastne presne tak, jak ukazoval na prednasce)  
  
2) Dokazat ze problem batohu je NP-uplny. K dukazu NP-tezkosti vyuzit nejaky problem z prednasky  
  
3) Zjistit hranovou souvislost grafu pomoci toku v sitich (algoritmus na tok v sitich nebylo potreba popisovat, stacilo rict, tady zavolam podprogram, ktery najde max tok), ukazat spravnost a casovou slozitost (tj. kolikrat potrebujeme hledat max tok)  
  
Ustni zkouska: typicky jedna otazka, ptal se na Four. trasformaci, NP-uplnost, aproximacni algoritmy, toky v sitich..  
_______________________________________________________  
  
Poznamky k pisemce:  
ad 2) Problem batohu je, ze mame n predmetu s velikosti v_i a cenami c_i, kapacitu batohu b a minimalni cenu k a ptame se, zda muzeme vybrat takovou mnozinu predmetu M, aby soucet velikosti byl max b a soucet cen min k.  
  
NP-uplnost znamena, ze je v NP a NP-tezky  
a) BAT je v NP: zrejme, mame certifikat (kdyz nam da nekdo M, lehce zjistime, zda jsou splneny podminky pro vyslednou velikost a cenu)  
b) BAT je NP-tezky: ukazeme tak, ze na nej prevedeme nejaky NP-tezky problem z prednasky (ne naopak), zde se uplne nabizi soucet podmnoziny, ukazujeme tedy SP -> BAT.  
SP: mame cisla x_1 az x_n a ptame se, zda z nich lze vybrat podmnozinu o souctu s  
prevod: polozime v_i = c_i = x_i, b = k = s  
  
ad 3) hranova souvislost je minimalni pocet hran, ktere musime z grafu odebrat, aby se stal nesouvislym  
Da se rozmyslet, ze kazdou neorientovanou hranu nahradime dveme orientovanymi (tam a zpet) a priradime jim vahu 1. Jeden vrchol zvolime pevne jako zdroj a vsechny zbyvajici postupne volime jako stok (max tok tedy hledame (n-1)krat). Minimum ze vsech maximalnich toku se rovna hranove souvislosti (protoze je to vlastne nejmensi mozny rez v grafu).
<{/ForumPost}>

<{ForumPost(poster="DocX", timestamp=2011-01-11 18:59:52)}>
Hm :) Nějak jsem si nevšiml kategorie ZS a bylo mi divné, že by zde nebyla kategorie pro ADS2.. Takže tady je moje, ale je to to samé :D  
  
**Zkouška 11.1.2011**  
  
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**  
  
*v<sub>1</sub>, ..., v<sub>n</sub>* velikosti předmětů  
*c<sub>1</sub>, ..., c<sub>n</sub>* 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.  
  
**Poznámky**  
- Aho-Corasick je celkem jednoduché, ale pozor na výstupní a zpětnou funkci :)  
- U batohu pozor na to, že je třeba převádět z něčeho na batoh, opačně to jde dost špatně ;)
<{/ForumPost}>