2R-SAT

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.
Odpovědět
jonny
Matfyz(ák|ačka) level II
Příspěvky: 53
Registrován: 14. 12. 2006 17:14

2R-SAT

Příspěvek od jonny »

Zdravicko

zacinam mit silne pochybnosti o tom, ze ten algoritmus z textaku funguje. Vite nekdo jak to bude vypadat pro vstup (a v non-b) & (non-a v b)? Ja mam pocit ze to vybuduje mutligraf o = o (dva uzly spojeny dvojitou hranou), rekne ze v komponente souvislosti je #vrcholu <= #hran takze OK?
Nahoru
Návštěvník

Re: 2R-SAT

Příspěvek od Návštěvník »

jonny píše:Zdravicko

zacinam mit silne pochybnosti o tom, ze ten algoritmus z textaku funguje. Vite nekdo jak to bude vypadat pro vstup (a v non-b) & (non-a v b)? Ja mam pocit ze to vybuduje mutligraf o = o (dva uzly spojeny dvojitou hranou), rekne ze v komponente souvislosti je #vrcholu <= #hran takze OK?
Ta formule je splnitelna. Zkus a=1, b=1. Takze je v poradku, ze algoritmus vrati OK.
Nahoru
Odpovědět

Zpět na „TIN062 Složitost I“