Zk 22.2.2010

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ů.
pasky
Matfyz(ák|ačka) level II
Příspěvky: 89
Registrován: 4. 1. 2005 22:57
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Zk 22.2.2010

Příspěvek od pasky »

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. ;-)
Next lecture on time travel will be held on previous Monday.
Betlista
Matfyz(ák|ačka) level I
Příspěvky: 24
Registrován: 21. 11. 2007 14:59
Typ studia: Informatika Mgr.

Re: Zk 22.2.2010

Příspěvek od Betlista »

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.
jkt
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 17. 5. 2007 14:02
Typ studia: Informatika Mgr.

Re: Zk 22.2.2010

Příspěvek od jkt »

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 :).
Odpovědět

Zpět na „TIN066 Datové struktury I“