# zkouska u Hrice 16.6.

<{ForumPost(poster="aja", timestamp=2006-06-16 16:22:35)}>
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...  
2. b) Zjistit sloyitost nake rekurentni formule podle Master theoremu...easy pokud jste schopni si Master theorem zapamatovat :oops: neni to tak tezke, fakt  :oops:   
3. 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:   
3. 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:
<{/ForumPost}>

<{ForumPost(poster="Jakobicek", timestamp=2006-06-17 10:00:28)}>
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?
<{/ForumPost}>

<{ForumPost(poster="aja", timestamp=2006-06-17 13:03:07)}>
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:
<{/ForumPost}>

<{ForumPost(poster="Zdeněk Vilušínský", timestamp=2006-06-17 15:56:51)}>
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 :)
<{/ForumPost}>

<{ForumPost(poster="Jakobicek", timestamp=2006-06-18 09:13:44)}>
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
<{/ForumPost}>

<{ForumPost(poster="Zdeněk Vilušínský", timestamp=2006-06-18 12:03:40)}>

 > 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..
<{/ForumPost}>

<{ForumPost(poster="Jakobicek", timestamp=2006-06-18 15:45:17)}>
ale jak si jiz naznacil... ono je to vlastne jedno... princip zustava
<{/ForumPost}>