|
|
|
||
Poslední úprava: Mgr. Petr Jedelský (01.03.2021)
|
|
||
Poslední úprava: Mgr. Petr Jedelský (01.03.2021)
Naučit pokročilejší datové struktury včetně teoretické analýzy a experimentů s chováním na reálných počítačích. |
|
||
Poslední úprava: Mgr. Petr Jedelský (01.03.2021)
Ke splnění předmětu je nutné získat zápočet a složit zkoušku.
Zápočet se udílí za získání požadovaného počtu bodů za domácí úkoly řešené během semestru. Vzhledem k povaze domácích úkolů nejsou náhradní termíny zápočtu přípustné. |
|
||
Poslední úprava: Mgr. Petr Jedelský (01.03.2021)
D. P. Mehta, S. Sahni eds.: Handbook of Data Structures and Applications. Chapman & Hall/CRC, Computer and Information Series, 2005
A. Koubková, V. Koubek: Datové struktury I. MATFYZPRESS, Praha 2011
K. Mehlhorn: Data Structures and Algorithms I: Sorting and Searching. Springer-Verlag, Berlin, 1984
|
|
||
Poslední úprava: Mgr. Petr Jedelský (01.03.2021)
Zkouška je ústní s písemnou přípravou. Zkouší se porozumění teorii prezentované na přednášce. |
|
||
Poslední úprava: Mgr. Petr Jedelský (01.03.2021)
Haldy
• regulární halda • binomiální halda • Fibonacciho halda
Stromy
• (a,b)-stromy a jejich varianty • strategie Move-to-Front pro seznamy, Splay stromy • přehled ostatních řešení: AVL stromy, červeno-černé stromy, BB-α stromy
Techniky pro paměťovou hierarchii
• I/O model, cache-oblivious analýza, strategie LRU pro on-line stránkování • příklady: transpozice a násobení matic, van Emde-Boasovo rozložení vyhledávacích stromů • cache-aware techniky
Hašování
• řešení kolizí, analýza pro uniformně rozdělená data • výběr hešovací funkce: univerzální hešování a dobré hešovací funkce • kukačkové hešování
Vícerozměrné datové struktury
• KD stromy • range trees (intervalové stromy)
Upozornění: Předmět se bude vyučovat od 2018/19 v českém jazyce pouze v zimním semestru a v anglickém jazyce pouze v letním semestru. |
|
||
Poslední úprava: Mgr. Petr Jedelský (01.03.2021)
Predpoklady: Znalosti na úrovni bakalářské přednášky Algoritmy a datové struktury. |