Zkouška 23. 01. 2015 Čepek

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₁, ..., v_n velikosti předmětů
c₁, ..., c_n 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

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

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 )