Vybrané partie z dátových štruktúr
2-INF-237, LS 2016/17

Úvod · Pravidlá · Prednášky · Prezentácia · Ako poznámkovať · Moodle
Táto stránka sa týka školského roku 2016/17. V školskom roku 2017/18 predmet vyučuje Jakub Kováč, stránku predmetu je https://people.ksp.sk/~kuko/ds


Sylabus na skúšku

Z VPDS
Prejsť na: navigácia, hľadanie

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)