[zk] 25/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.
Uživatelský avatar
macbeth
Matfyz(ák|ačka) level III
Příspěvky: 201
Registrován: 11. 2. 2005 14:48
Typ studia: Informatika Mgr.
Bydliště: PPraha
Kontaktovat uživatele:

[zk] 25/1/2010

Příspěvek od macbeth »

Tak co, ako ste dopadli? Ake boli priklady na pisomke? Co ste dostali na ustnej...?
Nieco, co by nejavilo ziadne znamky bytia, teda by sa nijak neprejavovalo ako sucno, by nebolo niecim, ale prave nicim...
Magon
Matfyz(ák|ačka) level I
Příspěvky: 4
Registrován: 2. 1. 2007 14:16
Typ studia: Informatika Bc.
Bydliště: Opava
Kontaktovat uživatele:

Re: [zk] 25/1/2010

Příspěvek od Magon »

Dnes byl priklad na Nalezeni HK pomoci krabicky na TSP. A Prevod SAT -> 3R-SAT. Vsechno zname a dohledatelne priklady.

Z ustni bylo: Savicova veta, Cook-Levinova veta, ukazat ze TSP bez trojuhelnikove nerovnosti neni aproximovatelny, TSP s trojuhelnikem je aproximovatelny, #P definovat/popsat, Pseudo-polynomialni alogoritmy.

A nevim jestli to byla jen vyjimka, anebo z toho bude pravidlo, ale zadal pouze 2 priklady na pisemnou, je treba alespon jeden vyresit. A velmi prijemne bylo, ze se odevzdavani pisemky dalo iterovat - kdyz bylo neco spatne, tak to donesl zpet a ukazal a rekl at to napravim.
Odpovědět

Zpět na „TIN062 Složitost I“