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 bude postupne vznikať sylabus na skúšku, zatiaľ však nie je kompletný. | Na tejto stránke bude postupne vznikať sylabus na skúšku, zatiaľ však nie je kompletný. | ||
| − | Amortizovaná zložitosť a splay stromy | + | '''Amortizovaná zložitosť a splay stromy''' |
* definícia amortizovanej zložitosti, potenciálová funkcia | * definícia amortizovanej zložitosti, potenciálová funkcia | ||
* 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) | ||
| − | RMQ a LCA | + | '''RMQ a LCA''' |
* algoritmy s O(n) predspracovaním a O(1) dotazom | * algoritmy s O(n) predspracovaním a O(1) dotazom | ||
| − | Vyhľadávanie kľúčových slov | + | '''Vyhľadávanie kľúčových slov''' |
* invertovaný index | * invertovaný index | ||
* lexikografický strom | * lexikografický strom | ||
* prienik triedených zoznamov (doubling search/galloping search) | * prienik triedených zoznamov (doubling search/galloping search) | ||
| − | Sufixové stromy a polia | + | '''Sufixové stromy a polia''' |
* sufixový strom | * sufixový strom | ||
* sufixové pole | * sufixové pole | ||
| Riadok 22: | Riadok 22: | ||
* použitie sufixového stromu a lca na hľadanie približných výskyty vzorky pri Hammingovej vzdialenosti | * použitie sufixového stromu a lca na hľadanie približných výskyty vzorky pri Hammingovej vzdialenosti | ||
| − | 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 hľadanie približných výskytov vzorky | ||
| − | Burrowsova–Wheelerova transformácia | + | '''Burrowsova–Wheelerova transformácia ''' |
* vytváranie, spätná transformácia, použitie na kompresiu, FM index | * vytváranie, spätná transformácia, použitie na kompresiu, FM index | ||
| − | Úsporné dátové štruktúry | + | '''Úsporné dátové štruktúry''' |
* štruktúra pre rank a select | * štruktúra pre rank a select | ||
* wavelet tree (rank nad väčšou abecedou) | * wavelet tree (rank nad väčšou abecedou) | ||
| Riadok 36: | Riadok 36: | ||
* úsporné stromy, počet binárnych stromov | * úsporné stromy, počet binárnych stromov | ||
| − | Prioritné rady | + | '''Prioritné rady''' |
* Fibonacciho halda a jej amortizovaná analýza | * Fibonacciho halda a jej amortizovaná analýza | ||
* Tri verzie meldable háld: random, leftist a skew, v každej algoritmus pre zjednotenie a jeho analýza | * Tri verzie meldable háld: random, leftist a skew, v každej algoritmus pre zjednotenie a jeho analýza | ||
| − | 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í | ||
| − | Štruktúry pre celočíselné kľúče | + | '''Štruktúry pre celočíselné kľúče''' |
| + | * van Emde Boas stromy, x-fast trees | ||
| − | Štruktúry pre externú pamäť | + | '''Štruktúry pre externú pamäť''' |
* výpočtový model externej pamäti, cache oblivious model | * výpočtový model externej pamäti, cache oblivious model | ||
* B-stromy | * B-stromy | ||
* statické cache-oblivious stromy s vEB rozložením | * statické cache-oblivious stromy s vEB rozložením | ||
| − | 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ácia dátovej štruktúry na čiastočne perzistentnú (za určitých predpokladov) | * všeobecná transformácia dátovej štruktúry na čiastočne perzistentnú (za určitých predpokladov) | ||
* ú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 | ||
| − | Geometrické dátové štruktúry | + | '''Geometrické dátové štruktúry''' |
* 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) | ||
Verzia zo dňa a času 10:25, 13. máj 2014
Na tejto stránke bude postupne vznikať sylabus na skúšku, zatiaľ však nie je kompletný.
Amortizovaná zložitosť a splay stromy
- definícia amortizovanej zložitosti, potenciálová funkcia
- splay stromy (algoritmus, zložitosť a potenciálová funkcia, netreba celý dôkaz)
RMQ a LCA
- algoritmy s O(n) predspracovaním a O(1) dotazom
Vyhľadávanie kľúčových slov
- invertovaný index
- lexikografický strom
- prienik triedených zoznamov (doubling search/galloping search)
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
- hľadanie maximálnych opakovaní
- použitie sufixového stromu a lca na hľadanie približných výskyty 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 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 (rank nad väčšou abecedou)
- štruktúra RRR a jej súvis s entropiou
- úsporné stromy, počet binárnych stromov
Prioritné rady
- Fibonacciho halda a jej amortizovaná analýza
- Tri verzie meldable háld: random, leftist a skew, v každej algoritmus pre zjednotenie a jeho analýza
Hešovanie
- Perfektné hešovanie: algoritmus, odhad očakávanej veľkosti pamäte pri použití univerzálnej triedy hešovacích funkcií
Štruktúry pre celočíselné kľúče
- van Emde Boas stromy, x-fast trees
Š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
Perzistentné dátové štruktúry
- definícia (čiastočne a úplne) perzistentných a retroaktívnych dátových štruktúr
- všeobecná transformácia dátovej štruktúry na čiastočne perzistentnú (za určitých predpokladov)
- ú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)
