Dolni odhad slozitosti medianu

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
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:
Kontaktovat uživatele Tuetschek

Dolni odhad slozitosti medianu

Příspěvek od Tuetschek »

Nemate nekdo nejaky (urcite je trivialni) dukaz odhadu slozitosti medianu? Nejak se mi nechce ho dneska vymyslet, kdyz jdu zitra :P.
Plug 'n' Pray.
Nahoru
Uživatelský avatar
Wegguy
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 20. 1. 2008 13:35
Typ studia: Informatika Mgr.

Re: Dolni odhad slozitosti medianu

Příspěvek od Wegguy »

Co si pamatuju, tak myslenka je, ze musis udelat aspon n-1 porovnani (graf: cisla vrcholy, hrany porovnani) - pokud bys udelal min, graf nebude souvisly a tedy budes mit vrchol, ktery jsi nikdy neporovnal s nicim, takze o nem nic nevis - tudiz nemuzes o zadnym tvrdit, ze je to median.
Nahoru
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:
Kontaktovat uživatele Tuetschek

Re: Dolni odhad slozitosti medianu

Příspěvek od Tuetschek »

Jaj diky ... ono to je vlastne v tom jednom zkouskovem prikladu, ale ja si to nejak nespojil :oops:
Plug 'n' Pray.
Nahoru
Odpovědět

Zpět na „TIN062 Složitost I“