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 (neobsahuje úplný obsah všetkých prednášok) | Na tejto stránke je sylabus na skúšku (neobsahuje úplný obsah všetkých prednášok) | ||
| − | '''Amortizovaná zložitosť | + | '''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 | ||
| + | * Tri verzie meldable háld: random, leftist a skew, v každej algoritmus pre zjednotenie a jeho 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é stromy | ||
| + | |||
| + | '''Splay stromy a link-cut stromy''' | ||
| + | * 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''' | ||
| Riadok 19: | Riadok 29: | ||
* 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 | + | |
'''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 |
'''Burrowsova–Wheelerova transformácia ''' | '''Burrowsova–Wheelerova transformácia ''' | ||
| Riadok 35: | Riadok 44: | ||
* š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 | ||
| − | |||
| − | |||
| − | |||
| − | |||
'''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, priblizny odhad pravdepodobnosti chyby | ||
'''Štruktúry pre celočíselné kľúče''' | '''Štruktúry pre celočíselné kľúče''' | ||
| Riadok 53: | Riadok 59: | ||
'''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 | ||
Verzia zo dňa a času 13:35, 21. máj 2015
Na tejto stránke je sylabus na skúšku (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
- Tri verzie meldable háld: random, leftist a skew, v každej algoritmus pre zjednotenie a jeho analýza
RMQ a LCA
- jednoduché algoritmy
- algoritmy s O(n) predspracovaním a O(1) dotazom
- segmentové stromy
Splay stromy a link-cut stromy
- 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
- 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
- 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 (rank nad väčšou abecedou)
- š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, priblizny odhad pravdepodobnosti chyby
Š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á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)
