# Zkouska 21.6.2006 <{ForumPost(poster="Veslar", timestamp=2006-06-21 14:09:18)}> 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... <{/ForumPost}> <{ForumPost(poster="Andreas", timestamp=2006-06-21 22:05:30)}> 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 :!: <{/ForumPost}> <{ForumPost(poster="Veslar", timestamp=2006-06-21 23:32:14)}> 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 :] <{/ForumPost}> <{ForumPost(poster="Petr-H", timestamp=2006-06-22 16:46:42)}> 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: <{/ForumPost}>