20.6.2006 - skuska u p.Hrica

mk
Matfyz(ák|ačka) level I
Příspěvky: 22
Registrován: 15. 6. 2006 10:20

20.6.2006 - skuska u p.Hrica

Příspěvek od mk »

Dnes sa konalo dalsie kolo skusky z algoritmov. Tu su otazky:

1a) def. bezpecnej hrany
1b) nech g je suvisly graf s nezapornym ohodnotenim hran. dokazte alebo vyvratte, ze minimalna kostra grafu je tvorena mnozinou vsetkych lahkych hran voci vsetkym rezom grafu

2a) najdite ssk zadaneho grafu. napiste stromove hrany, ktore ste pouzili. urcte typy hran incidentne s jednym zadanym vrcholom.
2b) ako vyzeraju ssk grafu, ktore je topologicky usporiadany?

3a)dokazte subst. metodou, ze T(n) = T(n/2) + T(n/3) + bn je "velke theta n".
3b)najdite najvacise celociselne a take, aby riesenie T(n) = aT(n/3) + O(n^1.5) bolo o(n^2).

poznamky:
- tvrdenie 1b neplati, takze je nacim ho vyvratit. zial, neviem ako.
- 2a je jasne, pomocou DFS
- 2b - graf je DAG, ziadne cykly => ssk su len jednotlive vrcholy
- 3b - vysledok mal byt 8. Ja som priklad riesil tak, ze som pomocou Master Theoremu nasiel najvacsie a take, ze T(n) = O(n^2). A napokon som ho zaokruhlil smerom nadol.

Ustna cast:
Mal som pocit, ze p. Hric skusa latku dost podrobne. Ja som dostal binomialnu haldu a operacie na nej a ked ma skusal, popytal sa ma hadam na vsetko, co sme mali.

Kazdopadne drzim palce na dalsich terminoch![/list]
Uživatelský avatar
tommy
Matfyz(ák|ačka) level I
Příspěvky: 24
Registrován: 1. 6. 2006 13:55

Otazky na ustnej

Příspěvek od tommy »

Mozem len suhlasit. Mal som Bellman Fordov algoritmus a pytal sa ma na kazdu vec ohladom skoro kazdeho riadku, ze preco je to tak.

Na ustnej vam pan doktor da otazku. Vybera ju zo zoznamu poziadaviek, ktory ma vytlaceny zo svojho webu, takze sa oplati si ho cely prejst. Co som mal moznost pocut, tak to boli tieto : priemerny pripad quicksortu, LU rozklad(nie LUP - lebo ten je vraj "tazsi" :wink: ), najkratsia cesta v grafe pomocou "nasobenia matic", dolny odhad pomocou triedenia pomocou porovnavania dvoch prvkov.

Nakoniec som bol siedmy v poradi a spolu so mnou bolo skore taketo : 1x1, 5x2, 1x4. Tak vela zdaru v priprave. :wink:
There's nothing left to lose.
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 »

no je to osklive trvzeni ktere asi plati pokud se prida ze vahova funkce je prosta... /mam pocit ze to byl predpoklad boruvkova algoritmu..tak jestli to nevychazi z tohoto/ uvazujme tedy graf jehoz ohodnoceni je treba jedna pro kazdou hranu obsazenou v grafu a bud toto uplny graf K5... zvolme nyni S(i) = rez mnoziny vrcholu obsahujici vzdy jen vrchol i ... pak je kazda hrana tvaru e(i,j) j={1..5} j<>i lehka pro rez S(i) a tedy sjednoceni vsech lehkych hran rezu tvaru S(i) je opet uplny graf K5 ktery zjevne obsahuje cyklus... pokud na toto dokazal nekdo prijit pri pisemce smekam klobouk az k zemi... me to doslo jen proto ze jsem vedel ze to nema fungovat...
hm no jestli to funguje pro prostou vahovou funkci asi ano..
pro kazdy rez pak totiz existuje prave jedna lehka hrana hm a ta je i bezpecna pro nejakou minimalni kostru......
dukaz indukci pres lehke hrany a rezy:
1.prazdna mnozina je podmnozinou nejake minimalni kostry
2a)bud A podmnozinou nejake min kostry.necht A respektuje rez S. Pak A U e, kde e je ta jedina lehka hrana pro rez respektujici A a A je podmnozinou nejake minimalni kostry, je take podmnozinou nejake minimalni kostry.../*viz prednaska*/
2b)necht A nerespektuje rez R pak ovsem v A existuje musi existovat hrana ktera je pro dany rez R lehka nebot A je podmnozinou minimalni kostry a tedy pro kazde dve mnoziny vrcholu S,P (S prunik P) =0 grafu obsahuje hranu e:min w(e[i,j]) kde i je elemenem S a j je elementem P
/*pri kazdem editu velikost dukazu roste :lol: asi to moc nebude konvegrovat k nake konecne limite*/
se moh nekdo ozvat arict mi ze ta druha cast je blbe :cry: nez napisu neco takoveho do pisemky...
Naposledy upravil(a) Jakobicek dne 30. 6. 2006 11:25, celkem upraveno 1 x.
Minsk will lead with blade and sword Boo will sort out the details
Inv
Matfyz(ák|ačka) level I
Příspěvky: 13
Registrován: 20. 1. 2006 23:48
Typ studia: Informatika Bc.
Bydliště: 17. listopad A1602
Kontaktovat uživatele:

Odhad slozitosti trideni

Příspěvek od Inv »

Pisu to sice trochu pozde.. Ja jsem mel na ustni ten dolni odhad slozitosti trideni zalozeneho na porovnavani 2 prvku. Docela hodne se vyptaval:

nakreslil jsem mu binarni rozhodovaci strom a rekl ze ma prave n! listu, coz jsou vsechny permutace vstupni posloupnosti. to mu ale nestacilo. ptal se me, proc je tam potrebuju vsehny permutace. Odpoved je, ze kdyby nektera chybela, predhodime algoritmu inverzni permutaci a on ji nedokaze setridit. Ok, takze urcite ne min nez n!. Ale taky ne prave n!.. tady jsme si trochu nerozumeli. Ptal se me: je tam tech listu n! nebo muze byt i vic ? Odpoved: muze byt i vic. Nejdrive nam nepritel da algoritmus, k nemu pak mame az strom. Tedy napr. selectSort ma taky rozhodovaci strom, ktery ma hloubku radove n^2, listu je tam vic nez n!, jenomze nektere listy jsou stejne. selectSort proste dela nejake porovnavani zbytecne.. Takze listu je >= n! a hloubka je >= nlogn (protoze log n! se da odhadnout jako >= nlogn, protoze n! >= npul na npul, to vi kazdy)
Proto je dolni odhad nlogn.

Snad to jeste nekomu pomuze, zdar
Odpovědět

Zpět na „2005“