zkouska u Hrice 16.6.

Pisemka:

1. Predvest Floyd Warshalluv algoritmus na grafu a dokazat jeho spravnost.

2. a)Substitucni metodou dokazat ze F(n)=T(n/3)+T(2n/3)+bn je O(n log n) ...nebo tak nak, nejsem si jista...

3. b) Zjistit sloyitost nake rekurentni formule podle Master theoremu...easy pokud jste schopni si Master theorem zapamatovat :oops: neni to tak tezke, fakt :oops:

4. a) dva prvky v AVL, dopadne strom stejne, pokud smazete napred x a pak y, jako kdyz smazete nejprv y a pak x...nejak odborne formulovane :lol:

5. b)cerna delka CC stromu je 4...pro vsechny mozne vysky napiste minimalni pocet vrcholu...(jo a list jakoze nil se pocita do te cerne hloubky :oops: )

...no nic moc...na ustnim tez nic moc...rekla jsem ze v listech rozhodovaciho stromu jsou ty utridene posloupnosti...ono mu slo o to, at reknu, ze tam jsou srovnane indexy...jako mela jsem to tak napsane na papiru, ale celkem me pri te ustni matl...
no...pisemky nedopadly moc slavne, myslim, ze jsem tam videla jednu 2 a jinak trojky a ctyrky...no tak nevim... :roll:

hm.. chapu to dobre? myslim to s tim minimalnim poctem vrcholu v dane hloubce... protoze pokud je to jak si myslim tak v kazde hloubce az do hloubky 4 musi byt RB tree uplny a ptali se na minimalni pocty vrcholu tak ve vsech dalsich hloubkach uz zadne dalsi vrcholy byt nemusi... nebyla ta otazka na maximalni pocet vrcholu?

nooooo :lol: .....ee :wink:
rozhodne sme meli urcit minimalni pocet.
tak jsem to asi nejak nesrozumitelne vysvetlila, ale melo to byt takto:
cerna vyska stromu je 4, takze pak celkova vyska muze byt:
4...takovy ten pekny pravidelny stromecek...7 vrcholu
5...bude mit 8 vrcholu, k jednomu uzlu na 3. hladine pridam 1 cerveny vrchol
6...pridam za ten cerveny jeste jeden, nak to poopravim, no a budu muset ten uzel na 3. hladine prebarvit na rudo :wink: a tudiz doleva mu pridat tez 1 cerneho syna...celkem teda 10 vrcholu
atd...az nekam...hmmm...do 8mi :wink:

doufam, ze to je jasnejsi...no ja bych to po sobe kazdopadne nepochopila :wink:

Nevim teda, jak dopadly písemky ostatních, ale já měl z nějakého důvodu 12 z 15 a to stačilo na 1.

Ad FW - dávejte si poyor na chyby v maticích, doporučuji kontrolovat několikrát. Důkaz mi stačilo, když jsem se rozepsal o tom, že se používají stále nejkratší cesty a pak prohlásil, že pro každou dvojici vyzkouším všechny možnosti.

Ad 2) Zdá se, že mu stačilo odhadnout substitucí z jedné strany a napsat, že druhou obdobně, ale za tohle neručím.

Ad 3) Ten delete byl jednoduchy, protipříklad existuje už na 4 vrcholech a Č-C byly skutečné hloubky od úplného stromu výšky 3 po strom, kde se na jedné straně střídala černá s červenou.

Na ústní pak LU rozklad což jsem haluzil večer před zkouškou takže výsledek za 1.

Jinak je Hric poměrně v pohodě, o ústní si s Vámi popovídá a tomu co jste tam napsali rozumí - víc než vy. Rozhodně je otevřen diskusi. Ale pak si hlídejte znalosti :)

uz jsem to pochopil... s tou RB potvorou... hm no pokud jde o substituce tak jestli tam bylo O a ne theta tak to urcite staci jen odhadnout zeshora

Jakobicek wrote:uz jsem to pochopil... s tou RB potvorou... hm no pokud jde o substituce tak jestli tam bylo O a ne theta tak to urcite saci jen odhadnout zeshora

U substituce byla Theta..

ale jak si jiz naznacil... ono je to vlastne jedno... princip zustava