Sylabus na skúšku

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)