Vybrané partie z dátových štruktúr
2-INF-237, LS 2016/17
Sylabus na skúšku: Rozdiel medzi revíziami
Z VPDS
| Riadok 7: | Riadok 7: | ||
'''Prioritné rady''' | '''Prioritné rady''' | ||
* Fibonacciho halda a jej amortizovaná analýza | * Fibonacciho halda a jej amortizovaná analýza | ||
| − | |||
'''RMQ a LCA''' | '''RMQ a LCA''' | ||
| Riadok 14: | Riadok 13: | ||
* segmentové stromy | * segmentové stromy | ||
| − | ''' | + | '''Scapegoat stromy, splay stromy a link-cut stromy''' |
| + | * scapegoat stromy, vrátane analýzy | ||
* splay stromy (algoritmus, zložitosť a potenciálová funkcia, netreba celý dôkaz) | * splay stromy (algoritmus, zložitosť a potenciálová funkcia, netreba celý dôkaz) | ||
* použitie splay stromov na join a split | * použitie splay stromov na join a split | ||
| Riadok 22: | Riadok 22: | ||
* invertovaný index | * invertovaný index | ||
* lexikografický strom | * lexikografický strom | ||
| − | |||
'''Sufixové stromy a polia''' | '''Sufixové stromy a polia''' | ||
| Riadok 42: | Riadok 41: | ||
'''Úsporné dátové štruktúry''' | '''Úsporné dátové štruktúry''' | ||
* štruktúra pre rank a select | * štruktúra pre rank a select | ||
| − | * wavelet tree | + | * wavelet tree |
* štruktúra RRR a jej súvis s entropiou | * štruktúra RRR a jej súvis s entropiou | ||
* úsporné stromy, počet binárnych stromov | * úsporné stromy, počet binárnych stromov | ||
| Riadok 48: | Riadok 47: | ||
'''Hešovanie''' | '''Hešovanie''' | ||
* Perfektné hešovanie: algoritmus, odhad očakávanej veľkosti pamäte pri použití univerzálnej triedy hešovacích funkcií | * Perfektné hešovanie: algoritmus, odhad očakávanej veľkosti pamäte pri použití univerzálnej triedy hešovacích funkcií | ||
| − | * Bloom filters - algoritmus, | + | * Bloom filters - algoritmus, približný odhad pravdepodobnosti chyby |
| − | + | ||
| − | + | ||
| − | + | ||
'''Štruktúry pre externú pamäť''' | '''Štruktúry pre externú pamäť''' | ||
| Riadok 57: | Riadok 53: | ||
* B-stromy | * B-stromy | ||
* statické cache-oblivious stromy s vEB rozložením | * statické cache-oblivious stromy s vEB rozložením | ||
| + | |||
| + | '''Štruktúry pre celočíselné kľúče''' | ||
| + | * van Emde Boas stromy, x-fast trie, y-fast trie | ||
'''Perzistentné dátové štruktúry''' | '''Perzistentné dátové štruktúry''' | ||
| Riadok 66: | Riadok 65: | ||
* lokalizácia bodu v rovine (planar point location) pomocou perzistentných a retroaktívnych štruktúr | * lokalizácia bodu v rovine (planar point location) pomocou perzistentných a retroaktívnych štruktúr | ||
* rozsahové stromy (range trees) a ich zrýchlenie (layered range trees) | * rozsahové stromy (range trees) a ich zrýchlenie (layered range trees) | ||
| + | * využitie wavelet trees namiesto statických rozsahových stromov | ||
Verzia zo dňa a času 09:04, 17. máj 2016
Na tejto stránke je sylabus na skúšku v školskom roku 2014/15 (neobsahuje úplný obsah všetkých prednášok)
Amortizovaná zložitosť
- definícia amortizovanej zložitosti, potenciálová funkcia
Prioritné rady
- Fibonacciho halda a jej amortizovaná analýza
RMQ a LCA
- jednoduché algoritmy
- algoritmy s O(n) predspracovaním a O(1) dotazom
- segmentové stromy
Scapegoat stromy, splay stromy a link-cut stromy
- scapegoat stromy, vrátane analýzy
- splay stromy (algoritmus, zložitosť a potenciálová funkcia, netreba celý dôkaz)
- použitie splay stromov na join a split
- link-cut stromy (štruktúra, expose, netreba analýzu zložitosti)
Vyhľadávanie kľúčových slov
- invertovaný index
- lexikografický strom
Sufixové stromy a polia
- sufixový strom
- sufixové pole
- vyhľadávanie vzorky v sufixovom strome a poli
- lineárny algoritmus na konštrukciu sufixového poľa
- konverzia zo sufixového poľa na sufixový strom a naopak
- použitie sufixového stromu a lca na hľadanie približných výskytov vzorky pri Hammingovej vzdialenosti
Vyhľadávanie vzorky v texte
- triviálny algoritmus na presné výskyty
- použitie konečných algoritmov, Morrisov-Prattov a Knuthov-Morrisov-Prattov algoritmus
- dynamické programovanie na výpočet editačnej vzdialenosti a na hľadanie približných výskytov vzorky
Burrowsova–Wheelerova transformácia
- vytváranie, spätná transformácia, použitie na kompresiu, FM index
Úsporné dátové štruktúry
- štruktúra pre rank a select
- wavelet tree
- štruktúra RRR a jej súvis s entropiou
- úsporné stromy, počet binárnych stromov
Hešovanie
- Perfektné hešovanie: algoritmus, odhad očakávanej veľkosti pamäte pri použití univerzálnej triedy hešovacích funkcií
- Bloom filters - algoritmus, približný odhad pravdepodobnosti chyby
Štruktúry pre externú pamäť
- výpočtový model externej pamäti, cache oblivious model
- B-stromy
- statické cache-oblivious stromy s vEB rozložením
Štruktúry pre celočíselné kľúče
- van Emde Boas stromy, x-fast trie, y-fast trie
Perzistentné dátové štruktúry
- definícia (čiastočne a úplne) perzistentných a retroaktívnych dátových štruktúr
- všeobecné transformácie dátovej štruktúry na čiastočne perzistentnú (fat nodes, node copying)
- úplná retroaktivita pre problém nasledovníka (successor) a podobné rozložiteľné vyhľadávacie problémy
Geometrické dátové štruktúry
- lokalizácia bodu v rovine (planar point location) pomocou perzistentných a retroaktívnych štruktúr
- rozsahové stromy (range trees) a ich zrýchlenie (layered range trees)
- využitie wavelet trees namiesto statických rozsahových stromov
