[Zk] 14.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ů.
martins
Matfyz(ák|ačka) level I
Příspěvky: 15
Registrován: 16. 1. 2010 15:59
Typ studia: Informatika Bc.

[Zk] 14.2.2012

Příspěvek od martins »

Klasicka skuska z datovych struktur. Koubek kazdemu dal jedno zadanie a kto mu to chcel ukazat tak sa prihlasil.

V ruskej rulete som obstal - Fibonacciho haldy. Napisal som vlastne vsetko co je v skriptach (ale dost chaoticky) - definiciu, operacie, ich zlozitosti, amortizovane zlozitosti (zlozitosti som okomentoval ked som si myslel ze to nie je zjavne) a lemmu a vety s dokazmi (o pocte synov vrcholu). Finalny dokaz kde sa odhaduje prave pocet synov v som si nepamatal, takze som ho odhadol jednoduchsie ako je v skriptach (takze viac nahrubo).

Koubek si tie moje papiere precital a nebol uplne spokojny s definiciou haldy - nenapisal som ze korene stromov nemozu byt oznacene. Nechal ma si to rozmysliet ale neprisiel som na to. Potom mi ukazal moj vyvazovaci algoritmus a uz to zo mna vytiahol. S ostatnym viac menej suhlasil a dal mi za 2 so slovami ze by mi chcel dat za 1 alebo ze mi ju neda.
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: [Zk] 14.2.2012

Příspěvek od Him »

Otazka: wordsort (ovsem pozor, ja nad tim pred zkouskou premyslel a rikal jsem si, jak muze poznat, ze mi dal zrovna tema XY, kdyz si to nepise, to bych skoro mohl psat XX a on by to nepoznal. Ovsem Koubek me prekvapil, kdyz vedel, ktere tema mi daval :-)))

Popsal jsem Bucketsort s casovymi slozitostmi. Zadefinoval jsem lexikograficke usporadani. Wordsort jsem popsal jednak slovy a po strane jeste takovym metakodem. Ten algoritmus je velmi jednoduchy (spis jsem se jistil, aby to p. Koubek nepochopil spatne).

Cetl to velmi peclive snad pet minut (pro mne takova mala vecnost) a nakonec mi dal 1.

Aspon mi nepokazil prumer :o)
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
Kubees
Matfyz(ák|ačka) level II
Příspěvky: 65
Registrován: 12. 1. 2007 22:22
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: [Zk] 14.2.2012

Příspěvek od Kubees »

Pro 20 lidi na zkousce Koubek vysypal z hlavy 20 ruznych otazek. Takze moje teorie, ze naucit se 5 nejcastejsich otazek zajisti slusnou sanci na uspech byla trochu fail. :( Dostal jsem "univerzalni system" jestli se dobre pamatuju. Sel jsem hned po zadani.
Odpovědět

Zpět na „TIN066 Datové struktury I“