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

Úvod · Pravidlá · Prednášky · Prezentácia · Ako poznámkovať · Moodle
Termíny skúšky sú v AIS, sylabus na skúšku je zverejnený, viď tiež popis v pravidlách predmetu
Body za aktivitu môžete dostať aj za nepovinnú domácu úlohu (pribudli nové zadania)
Od stredy 10.5. začínajú prezentácie podľa dohodnutého rozvrhu


Sylabus na skúšku

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

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

Úsporné dátové štruktúry

  • štruktúra pre rank a select
  • wavelet tree
  • štruktúra RRR a jej súvis s entropiou
  • úsporné stromy, počet binárnych stromov

Amortizovaná zložitosť

  • definícia amortizovanej zložitosti, potenciálová funkcia

Prioritné rady

  • Fibonacciho halda a jej amortizovaná analýza

RMQ a LCA

  • jednoduché algoritmy
  • algoritmy s O(n) predspracovaním a O(1) dotazom
  • segmentové/intervalové stromy

Scapegoat stromy, splay stromy a link-cut stromy

  • scapegoat stromy, vrátane analýzy
  • 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

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

Burrowsova–Wheelerova transformácia

  • vytváranie, spätná transformácia, použitie na kompresiu, FM index

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

Hešovanie

  • Perfektné hešovanie: algoritmus, odhad očakávanej veľkosti pamäte pri použití univerzálnej triedy hešovacích funkcií
  • Bloomov filter - algoritmus, približný odhad pravdepodobnosti chyby

Š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

Štruktúry pre celočíselné kľúče

  • van Emde Boas stromy, x-fast trie, y-fast trie

Streaming model

  • count-min sketch vrátane odhadu chyby

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)
  • využitie wavelet trees namiesto statických rozsahových stromov