Aproximovatelnost NM

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.

Aproximovatelnost NM

Příspěvekod HonzaK » 11. 1. 2012 10:11

Ahoj,
v poznamkach ze cviceni mam u otazky, zda je mozne aproximacni alg. z prednasky pro vrcholove pokryti (s r=2) pouzit i jako aproximacni
algoritmus pro nezavislou mnozinu (protoze NM = V \ VP). Mam k tomu jen poznamenano, ze "aproximovatlenost je ruzna"...
Nemate k tomu nekdo neco vic?

Diky
HonzaK
Matfyz(ák|ačka) level II
 
Příspěvky: 71
Registrován: 28. 9. 2007 16:36
Typ studia: Informatika Mgr.
Login do SIS: kohoj7am

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

cron