Ahojte,
hovoril Cepek, kedy bude hromadny zapoctovy test? Alebo sa to este objavi v SISe..?
dik za odpoved...
Kedy zapoctovy test
- macbeth
- Matfyz(ák|ačka) level III
- Příspěvky: 201
- Registrován: 11. 2. 2005 14:48
- Typ studia: Informatika Mgr.
- Bydliště: PPraha
- Kontaktovat uživatele:
Kedy zapoctovy test
Nieco, co by nejavilo ziadne znamky bytia, teda by sa nijak neprejavovalo ako sucno, by nebolo niecim, ale prave nicim...
Re: Kedy zapoctovy test
Hromadný test je 14.1.2010 na cvičení a další, stejně jako loni, na každém zkouškovém termínu
- macbeth
- Matfyz(ák|ačka) level III
- Příspěvky: 201
- Registrován: 11. 2. 2005 14:48
- Typ studia: Informatika Mgr.
- Bydliště: PPraha
- Kontaktovat uživatele:
Re: Kedy zapoctovy test
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
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
Nieco, co by nejavilo ziadne znamky bytia, teda by sa nijak neprejavovalo ako sucno, by nebolo niecim, ale prave nicim...
Re: Kedy zapoctovy test
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í.
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í.