[Zk] 19.6.2014

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: [Zk] 19.6.2014

Re: [Zk] 19.6.2014

od mathemage » 21. 6. 2014 22:54

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.

[Zk] 19.6.2014

od maky » 19. 6. 2014 12:21

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).

Nahoru