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

Verzia zo dňa a času 09:07, 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

Š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

• planar point location pomocou perzistentných a retroaktívnych štruktúr
• range trees a ich zrýchlenie layered range trees