[NTIN067] - Datové struktury II (Mareš, 25. 6. 2016)

Erim
Matfyz(ák|ačka) level I
Příspěvky: 11
Registrován: 18. 12. 2014 12:28
Typ studia: Informatika Bc.

[NTIN067] - Datové struktury II (Mareš, 25. 6. 2016)

Příspěvek od Erim »

Na termínu jsme byli tři a každý dostal teoretickou a praktickou otázku.

Teoretické otázky:
  • Statické slovníky - ukázat FKS a HMP, přičemž stačilo popsat kvadratické univerzum á la trie a jak funguje redukce do lineárního s randomizovanou konstrukci (důkaz lemma nemusel být vůbec podrobný, stačilo bez derandomizace).
  • Dynamizace - nadefinovat rozložitelný problém a obecnou dynamizaci.
  • Reprezentace řetězců nad obecnou abecedou s redundancí O(log n) - mixérové lemma + stromovitá struktura mixérů.
Praktické otázky:
  • Dynamizovat intervalové stromy - buď použít BB-alpha stromy a ukázat, že amortizovaně vyjdou o log n hůř nebo (to jsem dělal) šlo použít konstrukci řadou exponenciálně rostoucích statických struktur se sléváním (pozor, není třeba třídit) a škrtat mazané prvky. Na jedničku stačilo ukázat jak se řeší fractional cascading (verze pro 2D), a že to funguje i pro vylepšené intervalové stromy s efektivní 3D konstrukcí - protože se buňková reprezentace na dně nedá snadno upravovat, find může vycházet špatně v závislosti na počtu vyškrtaných prvků, ale průměrně vyjde dobře, protože se řada průběžně přebudovává když se prvků vyškrtá hodně.
  • Datová struktura pro udržování inkrementální kostry - udržuje kostru a přidává hrany (pomocí Link-Cut stromů).
  • Pro X podmnožinu U odpovídat na rank(x) a unrank(i) (i-tý prvek X) v o(log n) - stačilo staticky přes van Emde Boasovi stromy nebo Fusion Trees.
Odpovědět

Zpět na „I1 Ostatní Teoretická informatika“