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 1: | Riadok 1: | ||
| − | Na tejto stránke je sylabus na skúšku v školskom roku | + | Na tejto stránke je sylabus na skúšku v školskom roku 2016/17 |
(neobsahuje úplný obsah všetkých prednášok) | (neobsahuje úplný obsah všetkých prednášok) | ||
| + | |||
| + | '''Ú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 | ||
'''Amortizovaná zložitosť''' | '''Amortizovaná zložitosť''' | ||
| Riadok 11: | Riadok 17: | ||
* jednoduché algoritmy | * jednoduché algoritmy | ||
* algoritmy s O(n) predspracovaním a O(1) dotazom | * algoritmy s O(n) predspracovaním a O(1) dotazom | ||
| − | * segmentové stromy | + | * segmentové/intervalové stromy |
'''Scapegoat stromy, splay stromy a link-cut stromy''' | '''Scapegoat stromy, splay stromy a link-cut stromy''' | ||
| Riadok 30: | Riadok 36: | ||
* konverzia zo sufixového poľa na sufixový strom a naopak | * 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 | * použitie sufixového stromu a lca na hľadanie približných výskytov vzorky pri Hammingovej vzdialenosti | ||
| + | |||
| + | '''Burrowsova–Wheelerova transformácia ''' | ||
| + | * vytváranie, spätná transformácia, použitie na kompresiu, FM index | ||
'''Vyhľadávanie vzorky v texte''' | '''Vyhľadávanie vzorky v texte''' | ||
| Riadok 35: | Riadok 44: | ||
* použitie konečných algoritmov, Morrisov-Prattov a Knuthov-Morrisov-Prattov algoritmus | * 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 | * dynamické programovanie na výpočet editačnej vzdialenosti a na hľadanie približných výskytov vzorky | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
'''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í | ||
| − | * | + | * Bloomov filter - algoritmus, približný odhad pravdepodobnosti chyby |
'''Štruktúry pre externú pamäť''' | '''Štruktúry pre externú pamäť''' | ||
| Riadok 56: | Riadok 56: | ||
'''Štruktúry pre celočíselné kľúče''' | '''Štruktúry pre celočíselné kľúče''' | ||
* van Emde Boas stromy, x-fast trie, y-fast trie | * van Emde Boas stromy, x-fast trie, y-fast trie | ||
| + | |||
| + | '''Streaming model''' | ||
| + | * count-min sketch vrátane odhadu chyby | ||
'''Perzistentné dátové štruktúry''' | '''Perzistentné dátové štruktúry''' | ||
Aktuálna revízia z 14:07, 16. máj 2017
Na tejto stránke je sylabus na skúšku v školskom roku 2016/17 (neobsahuje úplný obsah všetkých prednášok)
Ú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
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é/intervalové 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
Burrowsova–Wheelerova transformácia
- vytváranie, spätná transformácia, použitie na kompresiu, FM index
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
Hešovanie
- Perfektné hešovanie: algoritmus, odhad očakávanej veľkosti pamäte pri použití univerzálnej triedy hešovacích funkcií
- Bloomov filter - 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
Streaming model
- count-min sketch vrátane odhadu chyby
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
