Zkouška Čtvrtek 5.6.2008 -- Kučera

V podstatě jako minule: http://forum.matfyz.info/viewtopic.php? ... 449#p21911
Bylo nás skoro třicet, měl nás seřazené podle času přihlášení (pokud si vzpomínám dobře) a cca po 4 lidech za hodinu nás bral. Pořadí řekl na začátku a kdo měl dlouho než se na něj dostane řada, mohl klidně na těch několik hodin odejít.

Pro začátek dá vždy téma na zpracování, pak případně doplňkové otázky. Dnes jsem slyšel tyhle:

• Průměrná hloubka binárního stromu (imho nejtěžší téma a docela mě překvapilo -- naštěstí jsem ho neměl já...)

• Perfektní hashování

• Dijkstrův algo

• Dolní odhad složitosti pro třídění (doplňková otázka: odhad průměrného případu)

• AVL stromy (doplňková otázka: najdi strom kde se po deletu nějakého prvku provedou 3 nebo více rotací)

• Červeno-černé stromy

• Minimální kostru jsem dnes neslyšel, ale určitě je to taky jedna z možností

Průměrná hloubka binárního stromu, super otazka...
jedina na kterou jsem se vykaslal, nic podobnyho jsme totiz minulej rok nedelali tak jsem se nemel moc ceho chytnout
...jsem mel pomalu vetsi sanci ze me ten den srazi autobus nez ze dostanu tuhle otazecku :P

nemeli byste k ni nejaky info? to co ma kucera na strankach je docela brutalni

bola aj minimalna kostra. uplne presne som ju nepovedal, tak mi dal doplnujucu otazku : mam rb strom, kde su vsetky vrcholy cierne a chcem vymazat list, ktory je uplne vlavo.

Jeste by mozna bylo dobre doplnit, ze Kucera v realtimu hashoval nove prichozi studenty pomoci uplne hashovaci funkce do tabulky velikosti 6 (nejdriv jednoho z tabulky odstranil a pak tam dalsiho vlozil) :wink:

Dal mi dolni odhad slozitosti trideni, tak jsem mu napsal asi na stranku ten dukaz s Mkama (staci to co ma na strance), pak to druhe lemma co tam je jenom tak hodne zhruba ... on se na to skoro ani nedival, jen se me zeptal na neco ze zacatku (trochu jsem nechapal, co presne chce, tak jsem jen pritakal), pak se zeptal na to, jak muze byt nejhur hluboky AVL strom s 12ti nodama a nakonec me poslal domu se slovy "no tak ja vam tu jednicku dam" :D

Myslim, ze zkousku u Kucery je tezsi nedat nez dat, je vazne skvelej :)