[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.

[zk] 25/1/2010

Příspěvekod macbeth » 25. 1. 2010 20:01

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

Re: [zk] 25/1/2010

Příspěvekod Magon » 25. 1. 2010 23:13

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.
Magon
Matfyz(ák|ačka) level I
 
Příspěvky: 4
Registrován: 2. 1. 2007 14:16
Bydliště: Opava


Zpět na TIN062 Složitost I

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník