[Zk] 7. 2. 2012

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ů.
peci1
Matfyz(ák|ačka) level II
Příspěvky: 86
Registrován: 21. 1. 2009 20:08
Typ studia: Informatika Bc.

[Zk] 7. 2. 2012

Příspěvek od peci1 »

Zdravim, tak k dnesni zkousce.

Temata, ktera jsem zaslechl, me neprekvapila, klasika RB-stromy, AVL, univerzalni a perfektni hashovani, neco s ostatnimi hashovanimi (zaslechl jsem pozdeji debatu od LICH/VICH apod.), leftist haldy... Proste bych rekl, ze zkousi temer cela skripta :) ( :( )

Ja dostal RB-stromy. Dal jsem dohromady definici, strukturu uzlu/listu, popsal jsem mu (slovne a z velkeho nadhledu!) vsechny algoritmy (nasel mi drobnost ve splitu a joinu), popsal, jak se to ma s vyskou stromu (zase zadne formalni dokazovani, slovne to uplne stacilo), odtud jsem jen napsal, ze plyne i slozitost vsech operaci (u splitu jsem napsal jen naznak, ze to je diky vlastnostem joinu a nejakou tu sumu jsem tam zvecnil). Co byla ale totalni tragedie, bylo vyvazovani. U insertu jsem dal dohromady tak 2 pripady z cca 4, u delete sotva dva, a to jeste nektere s chybama. Rikal, ze se mu zacatek libil, a jeste by to chtelo dodelat tohle. Ja mu rekl, ze mam vubec problem vymyslet, jake ze pripady to mam zkouset resit - tak se mnou sednul, dali jsme dohromady, jake jsou ty spatne konfigurace, a ja mu na nich pak ukazal, jak se toho rotacema ci prebarvenim zbavit. Obcas jsem neco udelal spatne (clovek se prehlidne) nebo jinak, nez ve slajdech (neefektivne - tady pozor, nektere pripady jdou resit jak prebarvenim, tak rotaci - a je nutne zvolit prebarveni, protoze mame vetu, ze insert se pri rotaci zastavi, coz ale v techhle pripadech zrovna nevychazelo).

Protoze nekdo pred zkouskou hlasil, ze se vyhazuje, kdyz clovek umi cokoli, ale na vyvazovani si nevzpomene, tak uz jsem jen premyslel, proc me trapi dal. A pak najednou prisel s tim, ze na jednicku uz to neni :-D Takze za dva a odchazel jsem stastnej jako blecha =)

Moje resume - pan profesor dokaze neco odpustit, ale neznalosti zakladnich veci nepromiji (rikal, ze vyhodil cloveka, protoze mu predvadel rotaci, ale tu rotaci delal spatne - tedy vyvazovani uz takovy zaklad neni, ale rotace, ty jo!). Kdyz tusi, ze se ve vas skryvaji nejake vedomosti, pidi se po nich (to vyvazovani ze me pacil, kdyz uz jsme tam po 3 hodinach zbyli sami, jeste dalsi pulhodinu). A rozhodne mu nejde o nejake formalnosti, zkouma, jestli chapete, co delate (pravda, ja zrovna nemel zadny vypocty, tak nevim, jak je to u nich). Na druhou stranu, pokud se neco, co nechapete, naucite nazpamet ( :-D ) a napisete to na papir dobre, tak se k tomu asi vracet nebude.

A pro uplnost - ucil jsem se cca 6 dni (celkem intenzivne).

Good luck!

PS: O dalsim zkouseni plati to, co uz tu bylo napsano v drivejsich letech. Kdyz za panem prof. prijdete v LS s tim, ze to umite, vyzkousi vas v relativne blizke dobe. Dokonce je dobre, kdyz se domluvi vic lidi. Ale je alergicky na lidi, co se s nim takhle domluvi a neprijdou! Jo, a na posledni zkousku (tusim kolem 14. 2.) nema pro neprihlasene smysl chodit, je tam tolik cekatelu, ze bude jistojiste kapacita 20 lidi vycerpana, i kdyz pulka prihlasenych neprijde. Resp. zkusit to muzete, ale s velkou pravdepodobnosti vas nevyzkousi.
Odpovědět

Zpět na „TIN066 Datové struktury I“