[Zk] 19.6.2014

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ů.
maky
Matfyz(ák|ačka) level I
Příspěvky: 13
Registrován: 24. 1. 2010 15:25
Typ studia: Informatika Mgr.

[Zk] 19.6.2014

Příspěvek od maky »

Dneska jsme se sešli u prof. Koubka čtyři ("termín" domluven individuálně mailem), já dostala dvojité hashování a ostatní snad Fibonacciho haldy, A-sort a c-univerzální systémy (nevím, jak přesně bylo zadáno).
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: [Zk] 19.6.2014

Příspěvek od mathemage »

Ja mel
Univerzalni hashovani
Napsal jsem uvodni definice (operace hashovani, znaceni), existenci univerzalniho systemu (s dukazem), ocekavana delka retezce (s dukazem). Precetl, poznal, ze chci na jednicku. Tak prisla otazka, dalsi otazka, dalsi otazka, tu jsem v podstate rekl, ale on myslel, ze ne, jeste mi zprdnul za vykrucovani.

Tak mi chtel dat za 2, ja si rekl o dalsi otazku, aplikace d-regularnich haldy. Rekl jsem o Dijsktrovi (nezap. ohodnoceni) a ze se na to daj pouzit haldy (jen insert, deletemin a decreasy). On po mne jeste chtel slozitost v zavislosti na manipulaci s "d". To jsem z hlavy nevyhuhlal, tak jsem pocital na papire a vyslo mi, ze pro graf na |V|^{1+\epsilon} je cas O(\frac{|E|}{\epsilon}). Pro ridsi se hodi spis Fibonacci, ale nevi se, zda-li je to jen ciste teoreticky vysledek.

Pak jeste chtel amortizovanou slozitost, proc to u Fibonacciho vychazi tak dobre (zalezi na posloupnosti operaci, to nam dava presnajsi odhad nez kazdou operaci odhadnout nejhorsim pripadem). Porad se mu nelibilo, co rikam, at tedy uz konecne reknu, co to ta amortizovana slozitost je. Napsal jsem definici amortizovane slozitosti operace...

To uz toho asi mel plny zuby (sedel jsem tam 90 min a blizil se cas na obed), tak s velikou nelibosti dal za 1 (rekl, ze to vubec nebylo ono). A jeste mi vytknul nedostatky, ze zakryvam, to co nevim, a okecavam (jako malymu klukovi mi vynadal), takze zkouska nebyla vubec prijemna :-(

Vysledek: 1. S mou rychlosti 3 str. za cca 30-40 min mi zabralo uceni 12 +- 5 dni.
Carpe Diem!
Odpovědět

Zpět na „TIN066 Datové struktury I“