20.6.2006 - skuska u p.Hrica
Napsal: 20. 6. 2006 14:28
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]
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]