Zkouška 29.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ů.

Zkouška 29.1.2014

Příspěvekod deusex » 29. 1. 2014 17:25

Klasická sada otázek, žádné pekla z Dodatků jsem neslyšel.

Já měl univerzální hasovani.

Napsal jsem definici, alt. definici s pravdepodobnosti s minidukazem. Dolni odhad c bez dukazu. Existenci c - univ. systemu s dukazem. Ocekavanou slozitost (µ = Σ δ) coz vede na 1 + c α s dukazem (to prohozeni sum) a markovovu nerovnost bez dukazu.

Cetl, cetl, kyval souhlasne hlavou. Nakonec se me zeptal na to jak volit i pro hi. Ja, ze generatorem pseudonahodnych cisel. On proc chceme cmalé? Já, že pseudonahodne generatory jsou zavisle na drive vygenerovanych hodnotach. Oceneno bez dalsiho komentare zapisem do indexu za jedna.
deusex
 

Re: Zkouška 29.1.2014

Příspěvekod pcech » 30. 1. 2014 10:54

Já bych jen dodal, že skutečně dodatek zkouší, kolega vedle mě dostal kukaččí hašování a myslím, že to hned vzdal, protože to nevěděl (asi na dodatek vůbec nekoukal). Přitom si myslím, že když si to člověk jednou přečte, tak to není těžké a zbytečně takto můžete přijít o jeden pokus.

Jinak já jsem měl červeno-černé stromy a celkem jsem se u toho zapotil. Popsal jsem asi 6x A4, všechny operace a rotace a vyvažování až na jednu u DELETE jsem měl dobře, měl jsem tam důkaz, že výška stromu je O(log|S|), definice 2-parc, 3-parc atd. a stejně mě tam pan Koubek hodně trápil. Hlavní je dát si pozor na definici bin. vyhledávacích stromů, kterou jsem samozřejmě zkazil. :-) Není to jen levý(v) < v < pravý(v) pro všechna v, ale (všechny levý(v)) < v < (všechny pravý(v)) pro všechna v. Tímto jsem ho myslím docela dost naštval (ještě mi vyčítal, jak několikrát zdůrazňoval na přednášce, že na tohle si máme dát pozor a stejně mu to tam všichni píšeme špatně :-)) a i když jsem měl pak všechno dobře (až na to jedno vyvažování), tak mi řekl, že se mu to nelíbí, ale že mi dá za 3. Byl jsem nakonec rád, že mám datovky za sebou...
pcech
Matfyz(ák|ačka) level I
 
Příspěvky: 3
Registrován: 4. 2. 2010 09:31
Typ studia: Informatika Mgr.

Re: Zkouška 29.1.2014

Příspěvekod tomtom » 30. 1. 2014 19:48

Dnešní termín (30.1.):

Huffmanův kód (napsal jsem prakticky všechno, co bylo ve skriptech, ale něco jsem pokazil v závěru toho důkazu, takže za 2)

Co jsem tak zaslechl okolo: Červeno-černé stromy, binomiální haldy, Fibonacciho haldy, ale taky třeba souvislost Quicksortu s operacemi na obecném BVS...

Tip 1: Nepodceňte látku z Dodatku, zkouší se a celkem houfně (a rozhodně to není peklo, dá se naučit zhruba za den).

Tip 2: Pokud chcete ČČ-stromy, sedněte si do první řady úplně vpravo (založeno na dvou pozorováních) :D
tomtom
 

Re: Zkouška 29.1.2014

Příspěvekod ved » 31. 1. 2014 09:09

Jo, 30. byl slyšet z druhé strany místnosti zase normální (A-sort, dvojité hashování, leftist haldy...) a relaxované stromy dostal nějaký chudák.
Přišlo mi, že možná není zas tak složité dostat tu trojku, jen se asi člověk fakt zapotí, když chce cokoliv lepšího...
ved
 


Zpět na TIN066 Datové struktury I

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník