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