Fink 8. 2. 2017
Napsal: 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, ...
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, ...