Zápočtová písemka - zadání

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.

Zápočtová písemka - zadání

Příspěvekod JT » 12. 1. 2012 17:50

Zadání zápočtovky (ne že by to bylo něco nového - opravdu úlohy z cvičení):
1) Ukažte, že TAUT je co-NP; jaká je složitost TAUT DNF?
2) Složitost hledání cesty v grafu se zápornými hranami.
3) Polynomiální algoritmus pro nalezení opt vrcholového pokrytí acyklického grafu.
JT
 

Re: Zápočtová písemka - zadání

Příspěvekod makak » 12. 1. 2012 18:59

wtf? pisomka ma byt az patek...
makak
 

Re: Zápočtová písemka - zadání

Příspěvekod JT » 13. 1. 2012 15:23

Ajta, můj trik se strojem času byl prozrazen :(

Realita je taková, že jsem v normálním termínu cvičil, ale chci příští týden na zkoušku, takže jsem to psal mimo.
JT
 


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