zkouska 30.6 Hric

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

zkouska 30.6 Hric

Příspěvek od Jakobicek »

po pisemce jsem byl smutny :cry:
zadani
1a. popsat RB-tree insert
1b. definuj B-strom
2.LU-dekompozice tridiagonalni ctrvercove matice radu 4 +vyresit soustvu pomoci LU rozkladu
ted proc jsem byl smutny
3.graf s ruzne ohodnocenymi hranami
3a...spravnost boruvkova algoritmu neboli sjednoceni vsech lehkych hran pres vsechny rezy tvori v grafu s ruzne ohodnocenymi hranami min.kostru--- pokud mate nekdo pekny dukaz postnete ho sem... :cry:
ten muj co visi o par threadu dal stoji za houby :wink:
3b.jednoznacnost jarnikova algoritmu v grafu s prostou vahovou fci
toto neni tezke.. je treba vedet ze vybirame vzdy lehkou hranu pro rez mezi dosud otevrenymi a jiz zpracovanymi vrcholy...
lehka hrana je pro dany rez za predpokladu proste vahove funkce prave jedna
pisemka az na treti priklad nebyla prilis narocna
na ustni je mozna dobre jit az po obede
/*syty hric je lepsi nez hladovy hric*/
ja jsem dostal silne souvisle komponenty
hric nijak zvlaste nestoural jen se zeptal jakou slozitost ma usporadani vrcholu podle casu uzavreni... O(V)
a na neco cemu jsem prilis nerozumel... souviselo to s casy uzavreni
kamarada po me se ptal na to jak se u floyd-warshallova algoritmu zjisti jestli graf obsahuje zaporne cykly... na diagonale budou zaporna cisla
oba jsme dostali za jedna :)
Minsk will lead with blade and sword Boo will sort out the details
Veslar
Matfyz(ák|ačka) level I
Příspěvky: 19
Registrován: 20. 6. 2006 19:39

Příspěvek od Veslar »

Mno neda mi to abych si rypnul. Nechapu jak si mohl byt smutny, kdyz si dostal 1 :P Takove lidi mam rad :P

Mno k tomu 3a....jelikoz me to uznal tak jsem to mel snad dobre :] Nejdriv jsem to chtel dokazat tak, ze kdyz si ty rezy spravne usporadam tak nic nepokaizm. Nejdriv jsem si je usporadal tak, jak by je vzal Prim-Jarnikuv alg....ale pak se muselo resit strasne moc pripadu, aby si dokazal, ze ostatni rezy urcite nepridaji nejakou hranu, kterou by Prim-Jarnik nepridal.
Takze jsem to zaskrtal.
Mno a tedka k reseni ktere jsem tam nechal napsane : Nejdriv reknes, ze kazdy rez urcite respektuje nejakou podmnozinu minimalni kostry. To je zcela jiste pravda [ to jsem tam ani nedokazoval a ani to po me nechtel ].
Mno a jelikoz mela kazda hrana jine ohodnoceni, tak je minimalni kostra jednoznacne urcena [popravde receno jsem si tim nebyl AZ tak jisty, ze jich tam naaahodou nemuze byt vic, ale nechtel se po me dukaz :] Mno a pak uz to je jednoduche. Pouzije se ta veta [tam uz jsem dukaz napsal], ktera rika, ze kdyz je F podmnozina hran nejake minimalni kostry a S je rez, ktery respektuje F, tak F U {u,v} je zase podmnozina minimalni kostry [kde u,v je lehka hrana pro rez S]. [viz slajdy].
Trouble? I call it sport.
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 »

jen si rypni... si to zaslouzim... :!: chtel jsem tu cast o smutku po ustni vymazat ale neudelal jsem to prave proto abych mohl byt po zasluze flamovan
smutny jsem byl jen po pisemce... po ustni pochopitelne uz ne :wink:
3a jsem totiz dokazoval nebo se o to spise pokousel zhruba pred 14 dny a na zkousce jsem si nebyl schopen vzpomenout co ze jsem to vlastne tehdy delal... pokus o par threadu zpet... jinak tvuj dukaz vypada smysluplne
tvrzeni, ze prosta vahova fce urcuje min. kostru jednoznacne, plati
jenom si nejsem jisty jak dokazat ze ta mnozina tvori vubec nejakou kostru ... ale asi to opravdu vyplyva z te vety na prednasce
Minsk will lead with blade and sword Boo will sort out the details
Odpovědět

Zpět na „2005“