Pseudopolynomiální algoritmy

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

Pseudopolynomiální algoritmy

Příspěvek od jamos »

Zdravím,

ve slajdech ze složitosti 1, je těsně před kapitolou o pseudopolynomiálních algoritmech uveden algoritmus pro součet podmnožiny. Je u něj uvedená složitost O(nb). Mohl by mi prosím někdo vysvětlit proč je tato složitost exponenciální vzhledem k binárnímu kódování a polynomiální vzhledem k unárnímu?

Díky.
HonzaK
Matfyz(ák|ačka) level II
Příspěvky: 71
Registrován: 28. 9. 2007 17:36
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Pseudopolynomiální algoritmy

Příspěvek od HonzaK »

Protoze pri unarnim kodovani je pro zapis cisla potreba udelat tolik "carek", kolik je to cislo, kdyzto pri binarnim a vyssim kodovani staci O(log(b)) bitu pro zapsani cisla b. Kdyz to tedy vezmes z opacne strany, tak pri unarnim zapisu se treba velikost toho b da omezit nejakym polynomem v promenne kod(X) (jak je to definovano ve slajdech dale), tedy plati b <= p(kod(X)) (p je ten polynom). Pri binarnim kodovani ale roste max. hodnota b exponencialne vzhledem k poctu bitu, ktere pouzijes na jeho zapis, nemuzes tedy velikost b omezit nejakym polynomem.
Odpovědět

Zpět na „TIN062 Složitost I“