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...
Zkouska 21.6.2006
Zkouska 21.6.2006
Trouble? I call it sport.
- Andreas
- Matfyz(ák|ačka) level I
- Příspěvky: 26
- Registrován: 18. 1. 2006 16:47
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
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
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
New systems generate new problems:)
- Petr-H
- Matfyz(ák|ačka) level II
- Příspěvky: 81
- Registrován: 30. 1. 2006 14:18
- Typ studia: Informatika Mgr.
- Login do SIS: hosep5am
- Bydliště: VŠK 17. listopadu
- Kontaktovat uživatele:
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
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