Kedy zapoctovy test

Základní přednáška o teorii složitosti algoritmů. Zhruba první polovina přednášky je věnována studiu složitosti konkrétních algoritmů různých typů (grafové, rozděl a panuj, hladové na matroidech) pracujících v polynomiálním čase. Složitost je zkoumána jak "klasicky" (složitost v nejhorším případě), tak amortizovaně. Druhá polovina přednášky je pak věnována studiu třídy NP, polynomiální převoditelnosti problémů a důkazům NP-úplnosti problémů. Závěr přednášky je věnován tématům souvisejícím se studiem NP-úplnosti: pseudopolynomiálním algoritmům a silné NP-úplnosti, početním úlohám a třídě #P.

Kedy zapoctovy test

Příspěvekod macbeth » 10. 1. 2010 17:37

Ahojte,

hovoril Cepek, kedy bude hromadny zapoctovy test? Alebo sa to este objavi v SISe..?

dik za odpoved...
Nieco, co by nejavilo ziadne znamky bytia, teda by sa nijak neprejavovalo ako sucno, by nebolo niecim, ale prave nicim...
Uživatelský avatar
macbeth
Matfyz(ák|ačka) level III
 
Příspěvky: 201
Registrován: 11. 2. 2005 14:48
Bydliště: PPraha
Typ studia: Informatika Mgr.

Re: Kedy zapoctovy test

Příspěvekod mat » 13. 1. 2010 10:53

Hromadný test je 14.1.2010 na cvičení a další, stejně jako loni, na každém zkouškovém termínu
mat
 

Re: Kedy zapoctovy test

Příspěvekod macbeth » 15. 1. 2010 20:20

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
Nieco, co by nejavilo ziadne znamky bytia, teda by sa nijak neprejavovalo ako sucno, by nebolo niecim, ale prave nicim...
Uživatelský avatar
macbeth
Matfyz(ák|ačka) level III
 
Příspěvky: 201
Registrován: 11. 2. 2005 14:48
Bydliště: PPraha
Typ studia: Informatika Mgr.

Re: Kedy zapoctovy test

Příspěvekod space_man » 15. 1. 2010 21:19

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í.
space_man
Matfyz(ák|ačka) level I
 
Příspěvky: 9
Registrován: 7. 6. 2006 17:43


Zpět na TIN062 Složitost I

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník