[Zk] 14. 2. 2008

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ů.
Graham Realyze

[Zk] 14. 2. 2008

Příspěvek od Graham Realyze »

Dnesni zkouska byla nejspis stejna jako vsechny ostatni.
Dr. Koubek sice septal, ale temata, co jsem zaslechl, byla perfektni hasovani (to dostal kolega a dostal povesti, ze tahle otazka je killer (ie. zabalil to behem 5 minut)), pak RB stromy, ja mel A-Sort.
Zkouska to byla v pohode, dostal jsem dvojku, protoze jsem neumel dokazat, ze horni hranici poctu stepeni pri A-Insertu lze odhadnout poctem vnitrnich vrcholu ve strome (a tzn. je to O(n)). Slo to rychle, az na tu rozpacitou petiminutovku, kdy jsme s Dr. K. synchronne mlceli a ja predstiral, ze to zkousim vymyslet. ;-) Nakonec me (potazmo sebe) netrapil a dal mi se slovy, ze lidem, kteri to umeji, dava dvojky nerad, dvojku. :-)
Prokop
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 28. 8. 2005 20:22

Re: [Zk] 14. 2. 2008

Příspěvek od Prokop »

Dostal jsem ocekavana delka a ocekavana nejhorsi delka retezcu u Hasovani se separovanymi retezci. Jelikoz jsem to druhe netusil, ni nevymyslil po 15minutach jsem se rozloucil. Jeste jsem se ptal na dalsi terminy a ty pry budou pripadne se da dohodnout osobne.
Uživatelský avatar
Tajro
Matfyz(ák|ačka) level I
Příspěvky: 28
Registrován: 14. 2. 2006 08:23
Typ studia: Informatika Bc.
Bydliště: Praha, Morava
Kontaktovat uživatele:

Re: [Zk] 14. 2. 2008

Příspěvek od Tajro »

Tak ten, co dostal RB stromy, jsem byl ja. Za tema jsem dekoval panubohu, protoze jsem ho poprve a naposledy cetl vecer pred zkouskou a tak jsem si ho jeste pomerne dobre pamatoval.. Je to paradoxni, protoze snad vsechna ostatni temata jsem cetl aspon ctyrikrat ;) Jinak tohle byl muj druhy termin, nakonec jsem to dal za tri, i kdyz sam bych si dal dvojku.. :D No a co jsem k tomu napsal?

- blablabla o tom, ze jsou RB stromy nejefektivnejsi a proc jako + drobne srovnani s AVL..
- hlavni definici, jak vypada RB strom...
- odvodil jsem maximalni vysku, tj. 4 + 2*log n...
- pak jsem se vrhnul na popis algoritmu KONTROLA-INSERT a KONTROLA-DELETE... kreslil jsem jen obrazky, fakt nema smysl se u tech stromu patlat s kodem.. Pri techto popisech jsem taky uvedl, co je to 2-parcialni RB strom a 3-parcialni RB strom... Jenze skoro vubec jsem nevedel KONTROLA-DELETE... jsem vul, nejak jsem to proste vecer pred zkouskou nedocetl...
- na zaver jsem napsal, ze to ma slozitosti radove log n a ze je u RB stromu fajn, ze se rotace u DELETE nevolaji tak casto jako v pripade AVL stromu

Pan Koubek na to vsechno koukal.. pomalu procital a prikyvoval.. no ale pak dosel k tomu mazani ze stromu a byl pruser.. snazil se to ze me vytahat.. a tak rikal: "Tak si rozeberme pripady: co kdyz barva tohohle vrcholu bude cervena..? premyslejte!" a ja jsem mlcel a premyslel hlavne o tom, kdy konecne rekne, ze to je teda jedno a ze mam dejmetomu za dva nebo za tri :) ale nakonec jsme vlastne spolu rozebrali vsechny pripady toho mazani a teprve pak mne pustil se slovy: "Ale musím vám to dát asi jen za tři" nebo tak nějak, což jsem až podezřele radostně odsouhlasil :)

HODNE ZDARU, LIDI!
Odpovědět

Zpět na „TIN066 Datové struktury I“