# zkouška 30. 5. Čepek

<{ForumPost(poster="hroh", timestamp=2007-05-30 13:43:32)}>
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.**
<{/ForumPost}>

<{ForumPost(poster="peterblack", timestamp=2007-05-30 16:51:37)}>
jaky bylo ustni? (bylo vubec ustni?)
<{/ForumPost}>

<{ForumPost(poster="hippies", timestamp=2007-06-03 13:28:16)}>
koukam, ze zadani se opakuji, .. presne totez jsem mel kdysi ja:)
<{/ForumPost}>

<{ForumPost(poster="Chjoodge", timestamp=2007-06-03 14:43:51)}>

 > 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ě.
<{/ForumPost}>