16.1.2009 [Zk]

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.
Manicka
Matfyz(ák|ačka) level I
Příspěvky: 26
Registrován: 28. 6. 2006 18:20

16.1.2009 [Zk]

Příspěvek od Manicka »

Tak dnes bylo prvni zadani z toho seznamu, tj.: porovnavani u algoritmu A, polynom. alg. pro JRPS pro t=2 a JRPS pro t>=3 je NPC.
Ustni jsem dostala lin. alg. pro testovani 2-souvislosti, ostatni nevim, sla jsem prvni.
Statistiku neposkytnu, jen vim ze jeden clovek odesel prede mnou a myslim, ze mel taky za 1.
Odpovědět

Zpět na „TIN062 Složitost I“