zkouska u Hrice 16.6.

aja
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 15. 5. 2006 09:02
Typ studia: Informatika Bc.
Kontaktovat uživatele:

zkouska u Hrice 16.6.

Příspěvek od aja »

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:
Computers are useless. They can only give you answers. - Pablo Picasso
Calm down -- it's only ones and zeros.
Bug? That's not a bug, that's a feature. -T. John Wendel
Jakobicek
Matfyz(ák|ačka) level II
Příspěvky: 53
Registrován: 26. 1. 2006 12:42
Typ studia: Informatika Bc.
Bydliště: Praha... VSE/MATFYZ

Příspěvek od Jakobicek »

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?
Minsk will lead with blade and sword Boo will sort out the details
aja
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 15. 5. 2006 09:02
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Příspěvek od aja »

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:
Computers are useless. They can only give you answers. - Pablo Picasso
Calm down -- it's only ones and zeros.
Bug? That's not a bug, that's a feature. -T. John Wendel
Uživatelský avatar
Zdeněk Vilušínský
Matfyz(ák|ačka) level III
Příspěvky: 110
Registrován: 16. 1. 2006 22:04
Typ studia: Informatika Bc.
Bydliště: Železný Brod/Troja A1923
Kontaktovat uživatele:

Příspěvek od Zdeněk Vilušínský »

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 :)
Věda je jako sex. Jistěže má nějaké praktické výsledky, ale proto ji přece neděláme. - R.P.Feynman

I krátký algoritmus může mít chování tak komplikované, že mu nerozumí ani jeho autor.
Jakobicek
Matfyz(ák|ačka) level II
Příspěvky: 53
Registrován: 26. 1. 2006 12:42
Typ studia: Informatika Bc.
Bydliště: Praha... VSE/MATFYZ

Příspěvek od Jakobicek »

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
Naposledy upravil(a) Jakobicek dne 18. 6. 2006 15:41, celkem upraveno 1 x.
Minsk will lead with blade and sword Boo will sort out the details
Uživatelský avatar
Zdeněk Vilušínský
Matfyz(ák|ačka) level III
Příspěvky: 110
Registrován: 16. 1. 2006 22:04
Typ studia: Informatika Bc.
Bydliště: Železný Brod/Troja A1923
Kontaktovat uživatele:

Příspěvek od Zdeněk Vilušínský »

Jakobicek píše: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..
Věda je jako sex. Jistěže má nějaké praktické výsledky, ale proto ji přece neděláme. - R.P.Feynman

I krátký algoritmus může mít chování tak komplikované, že mu nerozumí ani jeho autor.
Jakobicek
Matfyz(ák|ačka) level II
Příspěvky: 53
Registrován: 26. 1. 2006 12:42
Typ studia: Informatika Bc.
Bydliště: Praha... VSE/MATFYZ

Příspěvek od Jakobicek »

ale jak si jiz naznacil... ono je to vlastne jedno... princip zustava
Minsk will lead with blade and sword Boo will sort out the details
Odpovědět

Zpět na „2005“