Zk 22.2.2010

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 22.2.2010

Re: Zk 22.2.2010

od jkt » 23. 2. 2010 00:42

Ke quicksortu (jsem nyni po 8+ viteznych Plznich, proto prosim omluvte souvislost projevu) -- popsal jsem algoritmus slovne, uvedl problemy s volbou pivota (konstatoval jsem, ze "pro libovolneho pivota existuje posloupnost, kde alg. pobezi v $$O(n^2)$$", coz se doc. Koubkovi nezamlouvalo -- pokud jsem to v tuto hodinu schopen dat dohromady, jde cca. o to, ze pro kazdy pevne zadratovany algoritmus volby pivota existuje nejaky vstup, pro ktery alg. bezi v $$O(n^2)$$, zatimco pri nahodne volbe pivota je takovy cas nejhorsi pro vsechny vstupy), uvedl, ze nahodna volba chce cas, a ze se typicky bere median ze tri ci peti pevne danych prvku, konstatoval, ze pri zohledneni multiplikativni konstanty jde o nejrychlejsi znamy alg. pro trideni zalozeny na vzajemnem porovnavani prvku, uvedl aplikaci pri hledani k-teho nejmensiho prvku, konstatoval, ze casova slozitost je v nejhorsim pripade $$O(n^2)$$ a v ocekavanem O(n lon g ), aplikoval to na odhad potrebneho prostoru, popsal algoritmus tez formalne, zduvodnil slozitost v nejhorsim pripade ("pivot je nejvetsi/nejmensi prvek, tedy v kazdem kroku rekurze ubyde prave jeden clen posloupnosti"), lehce naznacil dukaz slozitosti v ocekvanem pripade, kde jsem pohnojil znaceni prvku -- dle Koubkovo skript se v prvnim, "peknem" dukaze hovori v pripade prvku $$ x_i $$ o i-tem prvku ve vystupni posloupnosti, a vubec jsem nemel rozhodovaci strom o prubehu algoritmu,... -- popsal jsem ale sumaci $$\sum_{i,j} X_{i j}$$...

-> zkratka nakonec se urodila krasna a zdrava dvojka, ktera mne coby tatovi udelala velikou radost :).

Re: Zk 22.2.2010

od Betlista » 23. 2. 2010 00:08

Ja len upravím, že nás bolo 11, po tom ako traja odišli po zadaní sme zostali ôsmi a dvaja boli "navyše", prišli bez toho, aby boli zapísaní v SISe.

Ja som dostal univerzálne hashovanie s príkladom (teda 3.25-univerzálne hashovanie), inak boli AVL stromy, hľadanie n-tého prvku (dotyčný nevedel, tak mu vyslovene povedal, že chce FIND a SELECT, on to asi skúšal nejak vymyslieť), bol aj quicksort, A-sort.

Pri tom hashovaní ho zaujímalo ako to funguje, prečo hľadáme niečo ako 3.25-univerzálne hashovanie od toho sme sa dostali k tomu ako fungujú pseudonáhodné generátory tj. generujú ďalšie číslo podľa predchádzajúcich vygenerovaných a preto nie sú dobré pre veľa vygenerovaných čísel.

Zk 22.2.2010

od pasky » 22. 2. 2010 20:20

Ja byl ten, kdo prisel a nebyl prihlaseny - vzhledem k tomu, ze mista byla dost (neprislo zdaleka vsech 20 lidi), to nebyl problem; pokud se na nejaky z poslednich terminu v SISu uz nevejdete, doporucuji prijit stejne, pravdepodobne Vas vezme.

Celkem bylo tak 15 lidi, cca 3 lidi to vzdali po kratke chvili, mezi ostatnimi iteroval. Ja jsem dostal jednu z nejlepsich moznych veci ;), vyhledavani v setridene posloupnosti. Sepsal jsem snad celkem presne obecny algoritmus i vsechny zakladni modifikace vcetne "trislovnych dukazu" slozitosti (to je fakt trivialni, az na ocekavane O(loglogN) u interpolacniho, a to se zase zrejme nedokazovalo a nezkousi vubec). U zobecneneho kvadratickeho jsem chvili musel vzpominat, jak je to s temi odmocninami, ale s matnymi vzpominkami se dal algoritmus uhadnout, jen jsem zapomnel, ze unarni kroky jdou tim smerem, kterym je prvek (ne vzdy dopredu) - ale to jsem rychle opravil, kdyz se mne na to zeptal. Nejvetsi problem byl se slozitosti, u ocekavane jsem si jen pamatoval, ze se da ukazat, ze v ramci jednoho interpolacniho kroku je ocekavany pocet tech ostatnich konstantni, ale neumel jsem to dokazat; tak mi nabidl, ze mne "jeste necha se s tim morit", nebo mi da rovnou trojku, kterouz jsem s povdekem prijal. Dokonce mi pak pri zapisovani znamky i docela srozumitelne vysvetlil, jak se to vlastne dokazuje, jdu to pripsat na wiki. ;-)

Nahoru