po pisemce jsem byl smutny
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...
ten muj co visi o par threadu dal stoji za houby
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
zkouska 30.6 Hric
-
- 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
Minsk will lead with blade and sword Boo will sort out the details
Mno neda mi to abych si rypnul. Nechapu jak si mohl byt smutny, kdyz si dostal 1 Takove lidi mam rad
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].
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.
-
- 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
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
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
smutny jsem byl jen po pisemce... po ustni pochopitelne uz ne
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