Sylabus na skúšku: Rozdiel medzi revíziami

Verzia zo dňa a času 09:28, 13. máj 2014

Na tejto stránke je sylabus na skúšku (neobsahuje úplný obsah všetkých prednášok)

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)