Skuska 14.6.05

No tak dnes bola pisomka z ineho sudka ako zvycajne. Pamatam si prvu ulohu (kedze som si ju opisal), ale 2. a 3. bude vymykat originalu:)

1. V pseudo kode sme mali zadane:

   MFF_SORT(A,i,j)
   BEGIN
    if A[i] >= A[j] then PREHOD(A[i],A[j])
    if i+1 >= j then EXIT
    k:= |_(j-i+1)/3_|               ..................(pozn. |_dolna cela cast_|)
    MFF_SORT(A,i,j-k)
    MFF_SORT(A,i+k,j)
    MFF_SORT(A,i,j-k)
   END
   

Rozhodnite ci dany algoritmus utriedi lubovolne vstupne n-prvkove pole A a svoje rozhodnutie zdovodnite resp. dokazte...

2. Urcte asymptoticku zlozitost algoritmu v zavislosti od funkcie F, ktoru nejakym sposobom vyciciate z ULOHY C. 1 ...
   (T.z. odvodit rekurentny vztah; horny a dolny odhad; dokazat)

3. (Toto si fakt pamatam len matne, takze ak tam niekto bol a zadanie si pamata presnejsie, nech ma opravi)
   Mate nejaku stvorcovu tabulku PxP (mozno to bolo nieco ine ale v principe to bolo jedno). Na vstupe dostanete nahodne vygenerovane dvojice (x,y), pricom 0<x,y<=p. Dve dvojice su susediace, ak sa |x1-x2|<=1 a |y1-y2|<=1. Vymyslite algoritmus, ktory vrati TRUE ak sa v zozname nachadza aspon jedna susediaca dvojica, inak vrati FALSE. Ocakavana casova zlozitost algoritmu je LINEARNA. Mozete predpokladat ze kazda dvojica sa vyskytne najviac raz.

4. a 2. som zmakol... Tu trojku nemal nikto dobre, kedze to malo byt riesene hashovanim. Takze max. za tuto ulohu bol 1/2b, co sa mi podarilo aj pri nie tak korektnom rieseni...

hm a riesenie aspon nejak 1 a 2 ?

tuxo wrote:hm a riesenie aspon nejak 1 a 2 ?

1. indukcia: ukazes ze 1,2,3prvkove pole to zotriedi. Predpokladas, ze plati pre 1,2,3...(n-1) a ukazes, ze plati aj pre n. Ked sa na to pozries poriadne tak si uvedomis (teda aspon by si si mal:)), ze tie 3 rekurzivne volania su vlastne volania na n prvkove pole take (nezalezi, aky interval sa vola), ze sa zoradi najprv pole o velkosti 2n/3 od zaciatku, potom rovnako velke pole, ale od n/3 po koniec a do tretice opat to od zaciatku... V predpoklade mas, ze tieto polia sa zotriedia. Takze jedine, co musis ukazat je, ze ked vezmes prve dve tretiny a zotriedis, a potom posledne dve tretiny a zotriedis a opat prve dve tretiny, tak ze cele pole bude zotriedene. To urobis velmi lahko sporom. To uz je fakt trivialne. Ale malo by sa to ukazat. Ved dokaz je dokaz:)

2. Toto sa da vidiet priamo z algoritmu. Takze riesenie 1 nemalo vplyv na riesenie 2.

Ako som spominal v 1, tak triedis polia o velkosti 2n/3 a toto zavolas 3x, pricom v tej procedure iba porovnavas, priradujes, a scitavas, co sa ti podari v konstantom case....

Takze z toho ti moze vyjst uz len: T(n) = 3T(2n/3) + theta(1)

Ak to hodis do master theorem, tak ti z toho vyjde, ze to bezi pri casovej zlozitosti theta( n^(log pri zaklade 3/2 z 3) ~ 2.7-8 )

Dufam, ze to ti bude stacit:)....