od lkj » 9. 2. 2017 10:51
Průběh zkoušky odpovídá popisu zde
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
je s velkou pravděpodobností perfektní
rozhodnout zda to samé platí i pokud má tabulka velikost
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, ...
Průběh zkoušky odpovídá popisu zde 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 [latex]\Theta (n^3)[/latex] je s velkou pravděpodobností perfektní
rozhodnout zda to samé platí i pokud má tabulka velikost [latex]\Theta (n^2)[/latex]
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, ...