# Zkouška 23. 01. 2015 Čepek

<{ForumPost(poster="lksjdl", timestamp=2015-01-23 14:31:51)}>
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.  
  
U ústní co jsem slyšel:  
definice P, NP, nějaký převod mezi problémy  
preflow-push  
RSA
<{/ForumPost}>

<{ForumPost(poster="SebastianP", timestamp=2017-01-22 22:28:45)}>
Ahoj, nevíš, jak by měla vypadat třídící síť pro 8 prvků? Přijde mi, že mergesort chápu, ale na 19 komparátorů mi má síť nevyjde.  
  
Díky, Sebastian
<{/ForumPost}>

<{ForumPost(poster="Jankus", timestamp=2017-01-24 11:58:45)}>
Popisem to ako 8 zvislych ciar a..h bez krizenia a napisem, medzi ktorymi su v ktorej vrstve komparatory (Cepek to ma radsej. na skuske som tie ciary krizil, aby porovnavene boli vedla seba - prislo mi to prehladnejsie - ale ze to strasne dlho lustil, nez zistil, ze su topologicky ekvivalentne :D )  
1) ab, cd, ef, gh (4 komparatory)  
2) ac, bd, eg, fh (4)  
3) bc, fg (2)  
4) ae, bf, cg, hd (4)  
5) ce, df (2)  
6) bc, de, fg (3)  
dohromady 6 vrstiev a 19 komparatorov  
  
zotroji sa to podla algoritmu:  
merge(x0..xn-1, y0..yn-1)  
    if (n==1) return ( min(x0,yo), max(x0,y0) )  
    a0..an-1 = merge(x0,x2..xn-2, y0,y2..yn-2)  
    b0..bn-1 = merge(x1,x3..xn-1, y1,y3..yn-1)  
    return ( a0, min(a1,b0), max(a1,b0), min(a2,b1), max(a2,b1) ... min(an-1, bn-2), max(an-1, bn-2), bn-1 )
<{/ForumPost}>