Vybrané partie z dátových štruktúr
2-INF-237, LS 2016/17
Sylabus na skúšku: Rozdiel medzi revíziami
Z VPDS
| 5 medziľahlých revízií od jedného používateľa nie je zobrazených. | |||
| Riadok 1: | Riadok 1: | ||
| − | Na tejto stránke je sylabus na skúšku (neobsahuje úplný obsah všetkých prednášok) | + | 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 | * definícia amortizovanej zložitosti, potenciálová funkcia | ||
| − | * | + | |
| + | '''Prioritné rady''' | ||
| + | * Fibonacciho halda a jej amortizovaná analýza | ||
'''RMQ a LCA''' | '''RMQ a LCA''' | ||
| + | * jednoduché algoritmy | ||
* algoritmy s O(n) predspracovaním a O(1) dotazom | * 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''' | '''Vyhľadávanie kľúčových slov''' | ||
* invertovaný index | * invertovaný index | ||
* lexikografický strom | * lexikografický strom | ||
| − | |||
'''Sufixové stromy a polia''' | '''Sufixové stromy a polia''' | ||
| Riadok 19: | Riadok 35: | ||
* lineárny algoritmus na konštrukciu sufixového poľa | * lineárny algoritmus na konštrukciu sufixového poľa | ||
* 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 | + | |
| + | '''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''' | ||
* triviálny algoritmus na presné výskyty | * triviálny algoritmus na presné výskyty | ||
* 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 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 50: | 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 | ||
| + | |||
| + | '''Streaming model''' | ||
| + | * count-min sketch vrátane odhadu chyby | ||
'''Perzistentné dátové štruktúry''' | '''Perzistentné dátové štruktúry''' | ||
* definícia (čiastočne a úplne) perzistentných a retroaktívnych dátových štruktúr | * 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 | * úplná retroaktivita pre problém nasledovníka (successor) a podobné rozložiteľné vyhľadávacie problémy | ||
| Riadok 59: | Riadok 68: | ||
* 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 | ||
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
