Zkouška 14.1.

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.
guthro
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 12. 4. 2013 10:07
Typ studia: Informatika Bc.

Zkouška 14.1.

Příspěvek od guthro »

V 9 hodin jsme byli vpuštěni do třídy, spolu s lidmi co si šli pro zápočet a lidmi jdoucími na zkoušku z Boolovských funkcí. Pan Čepek se zeptá, kdo na co jde, a v závislosti na tom dostane papír se zadáním. Na zápočet je hodina, na zkoušku hodiny dvě. První 4 lidi, kteří jsme odevzdali zkoušku nejdříve, následně dostane otázku ústní, zbytek byl pozván na nějakou hodinu po obědě, tuším že v intervalech dva lidi na půl hodiny.

K tématům: ve zkoušce byly dvě otázky, obě obsažené v úlohách do tramvaje.
První byla monochromatická maximální nezávislá množina (MMNM), druhé byl polynomiální algoritmus pro 2-SAT. Což je hlavní důvod proč sem píšu, nepochopil jsem totiž řešení z úloh do tramvaje.
Jako lepší řešení mi přijde řešení z anglické wikipedie, které se zároveň probírá na Boolovských funkcích.
V prvním kroku ohodnotíme všechny klauzule délky 1, pozor že nám při tom mohou vznikat nové klauzule délky 1, a případně může vzniknout i spor, a algoritmus pak skončí.
V druhém kroku si převedeme klauzule a uděláme si orientovaný graf, kde Vrcholy jsou za každý literál x vyskytující se v CNF vrchol X a vrchol non X, hrany jsou složeny z klauzulí ( x V y) : ( non x -> y) a (non y -> x)(dvě různá vyjádření klauzule x V y ). Na tento graf nyní spustíme algoritmus pro silně souvislé komponenty, a formule je splněna právě tehdy, pokud x a non x neleží ve stejné komponentě souvislosti.

Na ústní jsem dostal důkaz věty Cook-Lewin, existuje NP úplný problém, a protože jsem v tom měl pár děr, dostal jsem ještě za úkol říci,co jsou to úplně polynomiální aproximační schémata. Nešlo o formální definici, ale prostě o vysvětlení k čemu to je. Na všechno mi přišlo že bylo dost času.
Danstahr
Matfyz(ák|ačka) level I
Příspěvky: 12
Registrován: 26. 1. 2012 18:50
Typ studia: Informatika Bc.

Re: Zkouška 14.1.

Příspěvek od Danstahr »

Polynomiální algoritmus pro 2-SAT je mj. docela pěkně vysvětlen v letošních slajdech na logiku (konkrétně od slajdu 14), pokud by to někomu pomohlo : http://ktiml.mff.cuni.cz/~gregor/logika/VPL02.pdf
Jookyn
Matfyz(ák|ačka) level III
Příspěvky: 115
Registrován: 13. 9. 2008 21:42
Typ studia: Informatika Mgr.

Re: Zkouška 14.1.

Příspěvek od Jookyn »

Ja mel z pisemky 1.5 bodu, pulka byla za MMNM, jeden za 2-SAT. Takze jsem u ustni dostal prevod VP na Hamiltonovskou kruznici, aby pry videl, ze ty prevody umim...

Zacal jsem dobre, ale nedokazal jsem pak vymyslet, jak se to ma vsechno spojit na konci dohromady tak, aby to fungovalo, takze tak maximalne z poloviny. Druhou otazku jsem dostal jak je to s aproximaci obecneho TSP, dokazal jsem, ze pokud by existovala aproximace s konstantni pomerovou chybou, tak by se P = NP, tam nemel temer zadne vyhrady a odchazel jsem s dvojkou, je to hodnoceno pomerne mirne...
Odpovědět

Zpět na „TIN062 Složitost I“