Zk 21. 1. 2014

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ů.
MaM

Zk 21. 1. 2014

Příspěvek od MaM »

Dostal jsem fibonaciho haldy. Slovne jsem presne popsal jak probihaji operace (insert, min atd). Napsal slozitosti a rekl, jaky jsou amortizovany slozitosti. Nemel jsem to uplne tip top jako v knizce, ale vse hned proslo. Pak jsem se snazil dokazat amortizovanou slozitost (dukaz pres fibonaciho cisla). Tam jsem se trochu zasekl, tak pak jsem jen dopsal myslenku. Tzn i-ty strom ma alespon Fi+2 vrcholu a fib cisla rostou exponencialne, tzn staci log stromu (zkracene receno). Vse stacilo na 1.

Takze je dulezite znat princip a vysvetlit ho, netreba to uplne exaktne spocitat.
Na 3 by urcite v pohode stacilo jen popsani operaci.
Uživatelský avatar
emu
Matfyz(ák|ačka) level I
Příspěvky: 9
Registrován: 24. 1. 2011 16:24
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: Zk 21. 1. 2014

Příspěvek od emu »

Já jsem dostal A-sort, tak jsem se pozvolna rozpomenul na fungování ab-stromů a ve výsledku snad popsal algoritmus tak, jako byl na přednášce. Včetně složitosti, tu jsem si z části pamatoval a odvodit se dá docela snadno. Koubek se zeptal na pár podrobností, protože jsem řešení psal hodně random-access, a dal mi jedničku.

Teď mi dochází, že vlastně ani nemám ponětí, proč algoritmus čte posloupnost odzadu: popředu by podle mě fungoval taky.

Úspěšnost asi hodně záleží na otázce. Spolužák, co dneska přišel pozdě a neomluvil se, dostal perfektní hashování a radši šel rovnou zas domů.
Když mám zajímavý podpis, nepotřebuju psát zajímavé věci do těla zprávy.
Odpovědět

Zpět na „TIN066 Datové struktury I“