[zk] 29. 6.

Uživatelský avatar
tutchek
Site Admin
Příspěvky: 795
Registrován: 21. 9. 2004 00:40
Typ studia: Informatika Mgr.
Bydliště: Praha, Bohnice
Kontaktovat uživatele:

[zk] 29. 6.

Příspěvek od tutchek »

1) Dokazte nebo vyvratte ze operace delete naBVS je komutativni
(neni)

2) Mejme posloupnost ruznych klicu x1,x2,x3,...,xn a vahy klicu w1,w2,w3,...wn

Napiste algoritmus, ktery i v nejhorsim pripade v O(n) najde vazeny median. Vazeny median je definovan takto:
xk je vazeny median <=> xk splnuje:
1) soucet vsech vah klicu mensich nez xk je mensi nebo roven polovine souctu vsech vah
2) soucet vsech vah klicu vetsich nez xk je mensi nebo roven polovine souctu vsech vah
(upravene hledani medianu... ja a pak jeste nekdo pouzil neco jako counting sort, cimz si sice zjednodusili vber medianu, ale CS ma O(m+n), vzhledem k rozptylu klicu.. a kdyby |min(x) - max(x)| bylo O(n^2) tak to nebude co chteli... za to davali 1/4 bodu)


3) Napiste algoritmus co v nejlepsim case odhali nejkratsi (pocet hran) zaporny cyklus a pokud zadny takovy neni, tak vrati 0
(DFS neni idealni zpusob)

ja udelal neco na bazi DFS takze mi to skrtli, ale pak mi to uznal a dal pulku, protoze jsem tam mel vselijake ficuy co nasly vsechny cykly, opravdu to vyhodilo nejkratsi zaporny cyklus... jen to melo brutalni slozitost...


a na ustni jsem se patlal s medianem... Blum et al... nevedel jsem nic moc, ale byl jsem dokopan k vysledku a nakonec dostal trojku.... diky bohu za to, ze me nebavi dokazovat veci ale radsi vymyslet protipriklady (priklad jedna v pisemce)
exAdmin. Magistr přes umělou inteligenci. Právník přes daně.
Odpovědět

Zpět na „2004“