zkouška 30. 5. Čepek

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.**

jaky bylo ustni? (bylo vubec ustni?)

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

peterblack wrote: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ě.