Skuska 14.6.05

qwyxyo
Matfyz(ák|ačka) level II
Příspěvky: 51
Registrován: 30. 5. 2005 19:26
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Skuska 14.6.05

Příspěvek od qwyxyo »

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:

Kód: Vybrat vše

   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.

1. 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...
tuxo
Matfyz(ák|ačka) level I
Příspěvky: 4
Registrován: 7. 11. 2004 23:29
Typ studia: Informatika Bc.
Kontaktovat uživatele:

riesenie

Příspěvek od tuxo »

hm a riesenie aspon nejak 1 a 2 ?
qwyxyo
Matfyz(ák|ačka) level II
Příspěvky: 51
Registrován: 30. 5. 2005 19:26
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: riesenie

Příspěvek od qwyxyo »

tuxo píše: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:)....
Odpovědět

Zpět na „2004“