[Zk] 21.1.2009

[qwertie]

Tak jsem se vratil z hradu, plny emoci.. Otazky co jsem zaslechl - nektera hashovani, stromy, hlady.. Otazka kterou jsem si myslel ze jsem dostal: Vyvazovaci operace na (a,b) stromech.. vypracovano, podminky, aklgoritmy.. Otazka kterou jsem skutecne dostal: Pocet vyvazovacich operaci na (a,b) stromech... UFF! To jsem skutecne spocitat nedokazal... Pane kolego, to se budeme muset videt priste.. Priznejte se, kdo si to pamatuje.. Pocit: Grrr, kdyby mne vyhodil na hashovani, tak nereknu, ale tohle jsem uspesne zapomel po 10 strankach jeho skript.. A vubec, jdu snidat!

[Ziman]

Dostal som Quicksort, popisal som teda A4-ku nejakymi zakladnymi vecami, ako je definicia, nejaky jednoduchy pseudokod (tak, ze "usporiadaj prvky pola tak, ze ∀i < pivot : pole <= pole[pivot], ∀i > pivot : pole > pivot" bola jedna instrukcia, tj. ziadne porno s cyklami, if-mi a iteracnymi premennymi), O(N) pamatovu zlozitost, O(N²) v najhorsom pripade, O(N log N) v priemernom.

Koubek mal vyhrady voci tomu, ze som quicksort nazval in-place sortovacim algoritmom. Po kratkej dispute som pochopil, ze O(N) zasobnik (ktory som explicitne spomenul v papieri) nepovazuje za in-place, aj ked sa nevytvaraju ziadne pridavne polia s prvkami.

Dokaz O(N log N) zlozitosti v priemernom pripade som nevedel (co Koubek zamyslal ohodnotit trojkou), ale nejak som ukazal, ze beh quicksortu je analogicky stavaniu nahodneho binarneho stromu a pre ten som potom dokazoval, ze bude mat logaritmicku hlbku. Dokaz z prednasky som nevedel, ale vyplodil som nejake cosi, co dokazovalo, ze hlbka nahodneho binarneho stromu je v priemere O(log n), zrejme to nebolo spravne, pretoze to bolo dost kratke, ale Koubek to nevedel vyvratit a po dlhsom spekulovani nad roznymi castami dokazu nakoniec prehlasil "tak jste vyhral, dam vam dvojku, ale chci si nechat tenhle papir" a dvojku mi skutocne dal.

Celkovo mam z Koubka pocit, ze
* zalezi mu na konstantach (medianovy pivot u quicksortu mu z nejakeho dovodu nevyhovoval)
* posobil na mna dost ferovo -- vetou "ja vas nechci podcenovat, ale mnozi lide na ten dukaz koukali a nepodarilo se jim ho zkratit" mi celkom slusne naznacil, ze moj dokaz nemoze byt spravne, ozaj mu absolutne neveril, ale nedokazal najst konkretnu chybu, tak mi ho uznal
* je celkom prisny, ale nie je dovod sa ho bat, obcas nieco nevazne poznamenal, usmial sa

Na skusku som sa ucil dva dni a nakoniec som dostal nieco, co som sa neucil (pretoze to nebolo v materialoch, z ktorych som sa drvil ). Kazdopadne ale ak by som bol dostal nejake neprijemne hashovanie alebo trebars dynamizaciu, neviem-neviem, ako by som to dal; chcelo by to asi este o cosi viac pripravy.

[doser]

Já sem dostal otázku jednoduchou, hešování se separovanými řetězci a důkaz očekávané délky maximálního řetězce. Popsal jsem hešování jako takové a operace, důkaz sem si nevzpomněl, tak mi řekl ať dokážu alespoň očekávanou délku řetězce. Což jsem vymyslel. Výsledek nakonec za 2. Koubek je opravdu v pohodě.