Zkouška 22.1.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ů.
Uživatelský avatar
lingvik
Matfyz(ák|ačka) level I
Příspěvky: 21
Registrován: 23. 1. 2006 17:44
Typ studia: Informatika Bc.
Bydliště: Valašsko
Kontaktovat uživatele:

Zkouška 22.1.2008

Příspěvek od lingvik »

Bylo nás tam 10-15, jeden jenom přišel říct, že na zkoušku nejde :), druhý dostal téma univerzální hashování (moje minulé) a se slovy "tak to taky neumím" opustil místnost. Dostal jsem vyhledávání v uspořádáném poli. Krom toho jsem ještě zaslechl A-sort, Fibonacciho haldy a počítání se separovanými řetězci (průměr, maximum atd.).

Moje téma bylo docela v pohodě. Popsal jsem obecný princip, různé metody výpočtu funkce "next" s očekávanými časy a podrobně napsal algoritmus obecného kvadratického vyhledávání (pseudokód). Pak se mě Koubek ještě ptal, proč je očekávaný čas maximálně O(log n) a průměrně O(log log n). O(log n) jsem ukázal konkrétním případem: na posloupnosti typu 1, 2, 3, 4, ..., atd a (hafo strašně moc veliké číslo) jako poslední prvek (A[n] >> A[n-1]) algoritmus degeneruje k normálnímu binárnímu prohledávání. K O(log log n) jsem řekl základní myšlenku, čili že interval, ve kterém se hledá, se zmenšuje s odmocninou. Ukázal jsem, že trvá log log n dlouho, než se odmocňováním dostanu na konstantu (snadný důkaz na 4 řádky) a dál jsem to neuměl, nechtělo se mi to vymýšlet a chtělo se mi na záchod 8)

Takže za dva, spokojenost. Odcházel jsem jako druhý se známkou po hodině a třech čtvrtinách další hodiny, těsně přede mnou byla jednička.
Naposledy upravil(a) lingvik dne 22. 1. 2008 19:57, celkem upraveno 1 x.
gris
Matfyz(ák|ačka) level I
Příspěvky: 43
Registrován: 31. 10. 2004 20:31

Re: Zkouška 22.1.2008

Příspěvek od gris »

Já doplním, že vedle mě byl člověk, který měl externí hašování. Já jsem měla AVL-stromy. Hodinu jsem psala, napsala jsem odhad na hloubku a všechny případy pro insert a delete. Trvalo mi to asi hodinu, pak si to Koubek 15 minut četl. Vadilo mu, že jsem si v definici hloubky podstromu zapomněla dodefinovat 0 pro prázdný podstrom, jinak si nestěžoval. Můj dojem je, že člověk má tolik času, kolik potřebuje, takže je lepší toho dobře využít a napsat všechno přesně. Nevadí, když použijete jednodušší odhad třeba s horšími konstantami, ale když už něco píšete, tak je to třeba napsat dosti přesně. Jinak Koubek se mi zdál při zkoušení velmi příjemný a nápomocný.
Maca
Matfyz(ák|ačka) level I
Příspěvky: 16
Registrován: 4. 10. 2005 20:01

Re: Zkouška 22.1.2008

Příspěvek od Maca »

Já jsem měl ten A-Sort, takže vám můžu podat přesné svědectví o tom, že na 3ku stačí pár obecných vět (třídící algoritmus vhodný pro předtříděné posloupnosti...), popis algoritmu (klidně svými slovy, hlavně aby to bylo správně, můžete kreslit obrázky a on asi bude jedině rád :wink: ) a jeho složitost. Zeptal se mě jenom na to, co myslím tím "předtříděné posloupnosti" a stačila odpověď "počet inverzí ve vstupním poli", což je stejně součástí složitosti algoritmu.
bajeluk
Matfyz(ák|ačka) level I
Příspěvky: 15
Registrován: 20. 8. 2007 16:49
Typ studia: Informatika Bc.
Bydliště: Reichenberg
Kontaktovat uživatele:

Re: Zkouška 22.1.2008

Příspěvek od bajeluk »

Ja jen strucne doplnim, ze sem dostal perfektni hashovani. Fakt sem to moc neumel, takze sem 3 minuty premejslel, jestli to ma vubec cenu, a pak to se cti vzdal.

Jedna prakticka rada: uz o vikendu jsem dost tusil, ze se to nestihnu naucit, ale prosvih jsem termin na odhlaseni ze zkousky. Tak sem mu napsal mail, ale na ten neodpovedel, takze sem si rek, ze to teda zkusim, beztak nemam co ztratit. Kdyz sem se s nim ale bavil, tak jsem pochopil, ze kdybych to mel zapsany, ale vubec tam neprisel nebo mu nejlip rek dopredu, za to vzdavam, tak mi ten termin nepocital.

PS: tri dny je na uceni opravdu malo ;)
Odpovědět

Zpět na „TIN066 Datové struktury I“