Zkouška 14.1.

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: Zkouška 14.1.

Re: Zkouška 14.1.

od Jookyn » 14. 1. 2014 22:28

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

Re: Zkouška 14.1.

od Danstahr » 14. 1. 2014 20:41

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

Zkouška 14.1.

od guthro » 14. 1. 2014 14:12

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.

Nahoru