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.
Uživatelský avatar
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

Příspěvek od macbeth »

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...
mat

Re: Kedy zapoctovy test

Příspěvek 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
Uživatelský avatar
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

Příspěvek 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
Nieco, co by nejavilo ziadne znamky bytia, teda by sa nijak neprejavovalo ako sucno, by nebolo niecim, ale prave nicim...
space_man
Matfyz(ák|ačka) level I
Příspěvky: 9
Registrován: 7. 6. 2006 18:43

Re: Kedy zapoctovy test

Příspěvek 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í.
Odpovědět

Zpět na „TIN062 Složitost I“