# Fink 8. 2. 2017

<{ForumPost(poster="lkj", timestamp=2017-02-09 10:51:06)}>
Průběh zkoušky odpovídá popisu zde [http://forum.matfyz.info/viewtopic.php?f=206&t=11164](http://forum.matfyz.info/viewtopic.php?f=206&t=11164)  
  
Otázky dostal každý jiné. Já jsem měl:  
1) Fibonacciho halda - chtěl slyšet i důkazy amortizovaných složitostí operací DecreaseKey a DeleteMin + velikosti stromů, takže vpodstatě všechno co o ní bylo na přednášce.  
2) definice c-universálního hashovacího systému,  
definice perfektního hashování,   
definice jevu vyskytujícího se s velkou pravděpodobností,  
dokázat, že náhodně vybraná funkce z c-univerzálního systému, která hashuje n prvků do tabulky velikosti $\Theta (n^3)$ je s velkou pravděpodobností perfektní  
rozhodnout zda to samé platí i pokud má tabulka velikost  $\Theta (n^2)$  
  
Další věci co jsem zaslechl: a-b stromy, důkaz, že tabulkové hashování není 4-nezávislé (asi jako 2. příklad), cache-oblivious algoritmy, ...
<{/ForumPost}>

<{ForumPost(poster="CiTrus", timestamp=2017-02-14 11:19:14)}>
Já byl na stejném termínu a dostal jsem:

1. **Intervalové stromy (range trees)**  
Chtěl prakticky všechno ze slajdů (dokonce v jednu chvíli slajdy vytáhnul a porovnával s nimi, co jsem napsal).  
Pozor: u vícedimenzionálního zobecnění Fink rád zabředne do indexů a dlouhou dobu s vámi stráví dokazováním složitostí z definice rekurzí (log^d vs. log^{d-1})  
Nakonec chtěl i odvodit složitost dynamizace pomocí BB\[alpha] a zrychlení v poslední dimenzi pomocí kaskády.
1. **Splay stromy**  
Chtěl jen definice struktury, rotací a jak se provádějí základní operace.  
Potom tam byl příklad na dokázání algoritmu, kterým se ze splay stromu odeberou všechny klíče v daném intervalu \[a,b]. Chtěl explicitně algoritmus s logaritmickou složitostí.  
  
*Hint: SPLAY(b), SPLAY(a) a pak se jen musí dokázat, že všechny klíče z \[a,b] skončí v jednom podstromu, který jde odpojit v O(1).*

<{/ForumPost}>

<{ForumPost(poster="Katami", timestamp=2017-02-14 12:48:25)}>

 > CiTrus wrote:*Hint: SPLAY(b), SPLAY(a) a pak se jen musí dokázat, že všechny klíče z \[a,b] skončí v jednom podstromu, který jde odpojit v O(1).*

U Feldmanna na anglické paralelce jsem měl stejný příklad, řešený stejně, ale přišlo mi lepší tvrdit, že odpojení stromu je O(1), ale že je vhodné do toho počítat ještě O(počet prvků \[a,b]), protože je vhodné destruovat i ty konkrétní prvky.
<{/ForumPost}>