Obsah cviceni

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.
Monty
Matfyz(ák|ačka) level I
Příspěvky: 12
Registrován: 19. 1. 2009 00:36
Typ studia: Informatika Bc.

Obsah cviceni

Příspěvek od Monty »

Ahojte, mohl by mne, prosim, nekdo napsat, jestli na cviceni bylo probrano to, co ma uvedeno doc. Cepek na svych webovych strankach? Dekuji.
seby
Matfyz(ák|ačka) level I
Příspěvky: 42
Registrován: 31. 1. 2008 15:40
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Obsah cviceni

Příspěvek od seby »

Ahoj,

možná to neodpovídá úplně přesně, ale podle prvních cca 5 slov v zadání to odpovídá tomu, co se probíralo na cvičení.
Odpovědět

Zpět na „TIN062 Složitost I“