Fink 8. 2. 2017

Přednáška navazuje na přednášky Algoritmy a datové struktury I a II a Programování I a II bakalářského studia. Bude věnována dvěma základním datovým strukturám, hašování a $(a,b)$-stromům (tato struktura se také nazývá $B$-stromy). Popisují se zde základní vlastnosti těchto struktur a jejich složitost. Na závěr přednášky se provede stručné zhodnocení třídicích algoritmů.

Fink 8. 2. 2017

Příspěvekod lkj » 9. 2. 2017 10:51

Průběh zkoušky odpovídá popisu zde viewtopic.php?f=206&t=11164

Otázky dostal každý jiné. Já jsem měl:
1) Fibonacciho halda - chtěl slyšet i důkazy amortizovaných složitostí operací DecreaseKey a DeleteMin + velikosti stromů, takže vpodstatě všechno co o ní bylo na přednášce.
2) definice c-universálního hashovacího systému,
definice perfektního hashování,
definice jevu vyskytujícího se s velkou pravděpodobností,
dokázat, že náhodně vybraná funkce z c-univerzálního systému, která hashuje n prvků do tabulky velikosti \Theta (n^3) je s velkou pravděpodobností perfektní
rozhodnout zda to samé platí i pokud má tabulka velikost \Theta (n^2)

Další věci co jsem zaslechl: a-b stromy, důkaz, že tabulkové hashování není 4-nezávislé (asi jako 2. příklad), cache-oblivious algoritmy, ...
lkj
 

Re: Fink 8. 2. 2017

Příspěvekod CiTrus » 14. 2. 2017 11:19

Já byl na stejném termínu a dostal jsem:
  1. Intervalové stromy (range trees)
    Chtěl prakticky všechno ze slajdů (dokonce v jednu chvíli slajdy vytáhnul a porovnával s nimi, co jsem napsal).
    Pozor: u vícedimenzionálního zobecnění Fink rád zabředne do indexů a dlouhou dobu s vámi stráví dokazováním složitostí z definice rekurzí (log^d vs. log^{d-1})
    Nakonec chtěl i odvodit složitost dynamizace pomocí BB[alpha] a zrychlení v poslední dimenzi pomocí kaskády.
  2. Splay stromy
    Chtěl jen definice struktury, rotací a jak se provádějí základní operace.
    Potom tam byl příklad na dokázání algoritmu, kterým se ze splay stromu odeberou všechny klíče v daném intervalu [a,b]. Chtěl explicitně algoritmus s logaritmickou složitostí.

    Hint: SPLAY(b), SPLAY(a) a pak se jen musí dokázat, že všechny klíče z [a,b] skončí v jednom podstromu, který jde odpojit v O(1).
Uživatelský avatar
CiTrus
Matfyz(ák|ačka) level I
 
Příspěvky: 18
Registrován: 22. 6. 2014 13:05
Bydliště: Praha
Typ studia: Informatika Mgr.
Login do SIS: manekp

Re: Fink 8. 2. 2017

Příspěvekod Katami » 14. 2. 2017 12:48

CiTrus píše:Hint: SPLAY(b), SPLAY(a) a pak se jen musí dokázat, že všechny klíče z [a,b] skončí v jednom podstromu, který jde odpojit v O(1).

U Feldmanna na anglické paralelce jsem měl stejný příklad, řešený stejně, ale přišlo mi lepší tvrdit, že odpojení stromu je O(1), ale že je vhodné do toho počítat ještě O(počet prvků [a,b]), protože je vhodné destruovat i ty konkrétní prvky.
Katami
Matfyz(ák|ačka) level I
 
Příspěvky: 20
Registrován: 3. 2. 2014 13:40
Typ studia: Informatika Bc.


Zpět na TIN066 Datové struktury I

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron