zkouška 30. 5. Čepek

[hroh]

1. Dokažte nebo vyvraťte, zda MFF-SORT(A,1,n) správně setřídí pole n čísel.
MFF-SORT (A,i,j)
begin
if A > A[j] then PROHOĎ (A,A[j]); //pouze prohodí čísla
if i+1<j then
begin
k := dolnimez((j-i+1)/3);
MFF-SORT(A,i,j-k);
MFF-SORT(A,i+k,j);
MFF-SORT(A,i,j-k)
end
end;

2. Asymptoticky určetě těsně složitost algoritmu MFF-SORT (jako funkci pro počet tříděných čísel, tj. funkci pro n).

3. Máme mřížku p x p a zadány buňky pomocí souřadnic [xi,yi]. Určete algoritmus, který jako vstup dostane pole n náhodně vybraných buněk (1<=i<=n a 1<=xi,yi<=p) a v očekávaném lineárním čase O(n), zjistí, zda se v poli nachází dvojice sousedních buněk. Sousední buňky jsou takové, jejichž xi se liší max o 1 a yi také max o 1. N je dostatečně malé, tak, že lze vygenerovat pole velikosti O(n). Váš algortimus však nesmí být závislý na p.

[peterblack]

jaky bylo ustni? (bylo vubec ustni?)

[hippies]

koukam, ze zadani se opakuji, .. presne totez jsem mel kdysi ja:)

[Chjoodge]

jaky bylo ustni? (bylo vubec ustni?)

Jj, ústní je pár hodin po písemce. Dostaneš nějaké téma zhruba v rozsahu jednoho Čepkova slajdu, chvíli volně mluvíš, pak třeba něco ukážeš / dokážeš / vypočítáš - probíhá to příjemně.