Zkouška 23. 01. 2015 Čepek

Pokračování přednášky TIN060 Algoritmy a datové struktury I
lksjdl

Zkouška 23. 01. 2015 Čepek

Příspěvek od lksjdl »

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
SebastianP

Re: Zkouška 23. 01. 2015 Čepek

Příspěvek od SebastianP »

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
Jankus

Re: Zkouška 23. 01. 2015 Čepek

Příspěvek od Jankus »

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 )
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“