Zk [1.6.2007] Slozitost II

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
MrCooper
Matfyz(ák|ačka) level II
Příspěvky: 59
Registrován: 17. 1. 2006 17:54

Zk [1.6.2007] Slozitost II

Příspěvek od MrCooper »

Dnesni zkouska neprekvapila - nejdrive inkluze, potom ustni. Na ustnim byly typicke otazky - Borodin, Savic, Polynomialni hierarchie, ale i "lehci vety" - rozsirene o vztazich (obe dve), veta o prostorove hierarchii, veta o nedeterministicke prostorove hierarchii...

Je to ferova zkouska.
Nahoru
Odpovědět

Zpět na „TIN062 Složitost I“