Zkouska 21.6.2006

Takze dnes byla pisemka podle meho nazoru velmi jednoducha:

1. pro libobolny souvisly graf, ktery ma ruzne ohodnoceni hran, projizdime DFS tak, ze si vybirame hrany v rostoucim poradi.
   Dokazte nebo vyvratte: a) mnozina vsech stromovych hran tvori kostru b) mnozina vsech stromovych hran tvori minimalni kostru

2.a) mas dokazat indukci, ze pro AVL strom prati, ze strom s hloubkou n ma nejmenne F(n+2) -1 vrcholu, kde F(n) je nte fibinnaciho cislo
b) mazani prvku z B stromu

3. dokazte nebo vyvratte

a) logn! e theta (nlogn) , kde e je nalezi
b) 2^n e o(2^(n+3)), kde o je male o
c) (sqrt(2))^n e O(2^(n/2), kde o je velke O

reseni :
1 a) ano.
1b) ne - protiklad najit fakt neni tezke.

3. dokazte nebo vyvratte

a) toto plati, bylo treba to dokazat na obe strany, na jednu se udelal odhad jakej je v rozhodovacim strome a na druhou ze n! < n^n

b) 2^n e o(2^(n+3)), kde o je male o
toto neplati, protoze v definici o(n) je, ze to musi platit pro kazde c > 0 a to neplati.

c) (sqrt(2))^n e O(2^(n/2), kde o je velke O
plati, tady to je jednoduche :]

Ustni: co jsem tak slysel tak daval LUP rozklad, Mater Theorem [aji s ideou dukazu], Dokazat, ze Kruskal najde minimalni kostru...
mno a ja jsem chytl Nejkratsi cesty pomoci specialniho nasobeni matic - tak toto byla jedina vec, kterou jsem VUBEC nevedel, proste je to az v tech doplnovanych slajdech, ve zverejnenem postscriptu co tu je, tu to taky neni :) Takze bacha na to! Mno dosel jsem za panem Hricem ze k tomu mu nereknu ani slovo, jestli mi da neco jineho. Dostal jsem Floyd-Warshalla....nacez me presvedcil, ze ho opravdu nechapu a ze to neni vubec tak jednoduche a ze to mam vlastne uplne blbe....

Vzhledem k tomu ze jsem pisemku napsal na 15/15, tak jsme se domluvili, ze jsem dnes na zkousce vubec nebyl...

Tak to sem rad, ze nejsem sam, kdo napsal dobre pisemku a pak mel smulu u ustni. Mel sem teda "jen" 13/15 ale i tak. Na ustni sem nemel az tak tezke veci(Prumerna slozitost quicksortu a pak nasobeni cisel lepsi nez O(n^2)), ale jelikoz sem se ucil jen vecer predem, tak sem umel hlavne veci z prvni pulky slajdu(coz tohle bylo az v te druhe), dal to bylo slabsi a neco sem nevidel vubec. Jinak, ale muzu potvrdit, ze Hric je fakt v pohode, nijak me nestresoval a i kdyz videl, ze nevim, nechal mi jeste cas jestli si vzpomenu. Kdyz videl, ze to fakt nejde dal druhou otazku. Jelikoz sem ani k jednomu nerek nic moc smysluplnyho, tak rek, ze mi to neda, at prijdu priste :(
Je to celkem v poho zkouska, ale uplne ji nepodcenujte, pisemka se da napsat v podstate i bez dukazu, ale u ustniho se bez nich neobejdete :!:

Heheh, tak to ses ty, co tam porad chodil neco psat, mimochdem ty dlouhe cislo a quicksort jsem ti pekelne zavidel :) Mno tebe to mozna nesere, ale ja se na to ucil docela DLOUHO a to byla fakt asi JEDINA vec, ke ktere jsem mu nebyl schopen nic rict, co mi dal... no des :]

Taky jsem dostal Floyd-Warshallův algoritmus, a stejně tak mě p. Hric přesvědčil že ho úplně nechápu, naštěstí to co jsem mu řekl a napsal stačilo na 3, což je sice zklamání vzhledem k tomu kolik času jsem tomuto předmětu věnoval hlavně při přepisování přednášek, ale mám to za sebou :)

Co se týče chybějící části o speciálním násobení matic, omlouvám se, ale v průběhu semestru jsem byl několik týdnu nemocen a díky tomu jsem vynechal několik přednášek na kterých bylo přednášena i tato kapitola, nebyla ani v původní verzi slidů kterou jsem měl staženu od p. Hrice. To že tato kapitola chybí jsem zjistil až den před zkouškou díky upozornění jednoho ze spolužáků. Kapitolu jsem doplnil a najdete ji v aktualizované verzi přepisu v druhém threadu :wink: