Fórum studentů MFF UK

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 )

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

1) [b]Aho-Corasick:[/b]

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) [b]Problém batohu[/b]

[i]v[sub]1[/sub], ..., v[sub]n[/sub][/i] velikosti předmětů
[i]c[sub]1[/sub], ..., c[sub]n[/sub][/i] ceny předmětů
[i]k[/i] kapacita batohu
[i]r[/i] požadovaná cena

[i]Problém BAT[/i]: 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) [b]Hranová souvislost[/b]

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