od Krakonoš » 10. 1. 2013 21:33
Ahoj,
tak dnes to bylo lehoučké, že už to lehčí být nemohlo. Čepek prohlásil, že seznam na webu není asi aktuální a tak zvolil něco, co tam určitě je a dělalo se to na cvičení
a) Mějme množiny
po dvou disjunktní,
a množinu
. Dokažte, že (S,I) je matroid. (Takový ten středně těžký matroidový jako má na webu.
b) Najděte stok v grafu zadaném maticí sousednosti na
)
přístupů do paměti.
c) Zkonstruujte optimální VP pomocí blackoboxu řešícího rozhodovací verzi.
Ahoj,
tak dnes to bylo lehoučké, že už to lehčí být nemohlo. Čepek prohlásil, že seznam na webu není asi aktuální a tak zvolil něco, co tam určitě je a dělalo se to na cvičení :-)
a) Mějme množiny [latex]S_i, i = 1..n[/latex] po dvou disjunktní, [latex]S[/latex] a množinu [latex]I=\{A \subseteq S : \forall i |A\cup S_i|\leq 1\}[/latex]. Dokažte, že (S,I) je matroid. (Takový ten středně těžký matroidový jako má na webu.
b) Najděte stok v grafu zadaném maticí sousednosti na [latex]\matcal{O}(n)[/latex] přístupů do paměti.
c) Zkonstruujte optimální VP pomocí blackoboxu řešícího rozhodovací verzi.