Stránka 1 z 1
Kedy zapoctovy test
Napsal: 10. 1. 2010 17:37
od macbeth
Ahojte,
hovoril Cepek, kedy bude hromadny zapoctovy test? Alebo sa to este objavi v SISe..?
dik za odpoved...
Re: Kedy zapoctovy test
Napsal: 13. 1. 2010 10:53
od mat
Hromadný test je 14.1.2010 na cvičení a další, stejně jako loni, na každém zkouškovém termínu
Re: Kedy zapoctovy test
Napsal: 15. 1. 2010 20:20
od macbeth
ahojte,
mohol by niekto v strucnosti napisat, ake boli priklady? mal som totiz vo stvrtok od 12.20 skusku, takze som nemohol ist na zapocet.
vdaka
Re: Kedy zapoctovy test
Napsal: 15. 1. 2010 21:19
od space_man
Ahoj,
priklady byly nasledujici, jako obvykle ze cviceni, bylo na to 60 minut:
1.
Nechť S je konečná neprázdná množina a nechť S1, S2, ..., Sn je rozdělení množiny S na po dvou disjunktní podmnožiny. Nechť I = {A | Vi |A prunik Si| <= 1}. Dokažte, že (S,I) je matroid.
2.
Nechť je orientovaný graf G=(V,E), kde |V| = n, zadán maticí sousednosti. Navrhněte algoritmus, který zjistí zda G obsahuje stok, tj. vrchol x takový, že vstupní stupeň x je n-1 a výstupní stupeň x je 0, přičemž algoritmus smí použít (přečíst) pouze O(n) prvků matice (předpokládejme, že před zahájením algoritmu je již celá matice načtena do paměti).
3.
1.Nechť máme k dispozici „černou skřínku“, která umí řešit VP (rozhodovací verzi problému vrcholového pokrytí grafu) v polynomiálním čase. Skřínka odpovídá pouze ANO-NE. Zkonstruujte algoritmus, který pro daný neorientovaný graf najde v polynomiálním čase jeho (libovolné) minimální vrcholové pokrytí.