[zk] 27/1/2010

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.
kaktus64
Matfyz(ák|ačka) level I
Příspěvky: 22
Registrován: 3. 6. 2008 10:42
Typ studia: Informatika Mgr.

[zk] 27/1/2010

Příspěvek od kaktus64 »

Oneskorene, ale predsa...

Písomná časť:
trvanie hodina a pol, dva príklady
1) daný počet strojov, čas t a množina úloh s jednotkovým trvaním zadaná grafom, kde hrana je medzi úlohami, ktoré sa nesmú prekrývať v čase. Navrhnúť polyn.alg. ktorý pre t=2 rozhodne, či je možné rozvrhnúť úlohy na m strojov, tak aby boli dokončené v čase 2 a dodržali závyslosti dané grafom.
2) ukázať, že pre t väčšie ako 2 je NPúplné

Známe príklady, riešenia dohľadateľné.

Ústna časť:
Počuť bolo všetky klasické otázky. Ja som mal ukázať NPúplnosť SP pomocou VP a vysvetliť, čo je to pseudopolyn.alg.

písomná 1,5 bodu + ústna komplet ok = velmi dobře

GL
Odpovědět

Zpět na „TIN062 Složitost I“