Fórum studentů MFF UK

Pisemna cast:

1) Vymyslet algoritmus na hledani mostu v neorientovanem grafu.
2) 2-SAT - vymyslet polynomialni algoritmus
3) Dokazat ze MMNM je NPU

Na vysledky se ceka...

Snad jen načrtnu svoje řešení (měl jsem vše dobře)

1) Pouze aplikace algoritmu na hledání 2-souvislých komponent. Jednoduše otestujeme, zda 2-souvislá komponenta se sestává pouze z 1 hrany (pak je ta most).
2) Uděláme si hezký rekurzivní algoritmus. Vezmeme první formuli a ohodnotíme první literál na 1. Pak smažeme ty formule, kde je literál ohodnocen na 1 a ohodnotíme ty formule, kde je negovaný - vyjdou 1 formule, které musí být ohodnoceny vždy na 1. Po smazání se zavoláme rekurzivně na zbytek neohodnocených formulí. Pokud to nejde splnit, vrátíme se a ohodnotíme druhý literál na 1. Pokud i to je nesplnitelné, pak je formule celá nesplnitelná. Celkovej čas O(n^3), nevíte někdo, zda to jde lépe?
3) Dělá se převodem SATu, červené jsou klauzule, černé proměnné a jejich negace, hrany vedou mezi proměnnými a jejich negacemi a mezi literály a formulemi, které je obsahují. Pokud existuje maximální nezávislá černá množina, dostaneme splňující ohodnocení a pokud neexistuje, formule nejde splnit.

Pak na ústním jsem dostal takovou směsku okolo #P, silná NP-úplnost, aproximační algoritmy apod. po 40 minutách jsem odcházel s 1 v indexu. Hodně štěstí ostatním!

Osiris píše:Snad jen načrtnu svoje řešení (měl jsem vše dobře)
...
2) Uděláme si hezký rekurzivní algoritmus. Vezmeme první formuli a ohodnotíme první literál na 1. Pak smažeme ty formule, kde je literál ohodnocen na 1 a ohodnotíme ty formule, kde je negovaný - vyjdou 1 formule, které musí být ohodnoceny vždy na 1. Po smazání se zavoláme rekurzivně na zbytek neohodnocených formulí. Pokud to nejde splnit, vrátíme se a ohodnotíme druhý literál na 1. Pokud i to je nesplnitelné, pak je formule celá nesplnitelná. Celkovej čas O(n^3), nevíte někdo, zda to jde lépe?
...

Na to jsem nekdy na necem videl pekny algoritmus, nevim, jestli si uplne spravne vzpomenu, tak me kdyztak nekdo opravte, kdybych placal nesmysly (slozitost jsem se jeste neucil )
Klauzule (x || y) se prevedou na ekvivalentni tvar ( neg(x) => y ) [EDIT: zrejme se musi doplnit i ( neg(y) => x ) ] ... no a tohle interpretuji jako orientovany graf (na 2n vrcholech). A myslim plati, ze formule je splnitelna <-> pro kazde x plati, ze x a neg(x) nejsou ve stejne SSK. (potom by platilo x <=> neg(x)). No a to uz se da docela pekne otestovat.

Osiris píše:Celkovej čas O(n^3), nevíte někdo, zda to jde lépe?

Známý algoritmus využívající SSK běží v O(n).

Myshaak píše:

Osiris píše:Snad jen načrtnu svoje řešení (měl jsem vše dobře)
...
2) Uděláme si hezký rekurzivní algoritmus. Vezmeme první formuli a ohodnotíme první literál na 1. Pak smažeme ty formule, kde je literál ohodnocen na 1 a ohodnotíme ty formule, kde je negovaný - vyjdou 1 formule, které musí být ohodnoceny vždy na 1. Po smazání se zavoláme rekurzivně na zbytek neohodnocených formulí. Pokud to nejde splnit, vrátíme se a ohodnotíme druhý literál na 1. Pokud i to je nesplnitelné, pak je formule celá nesplnitelná. Celkovej čas O(n^3), nevíte někdo, zda to jde lépe?
...

Na to jsem nekdy na necem videl pekny algoritmus, nevim, jestli si uplne spravne vzpomenu, tak me kdyztak nekdo opravte, kdybych placal nesmysly (slozitost jsem se jeste neucil )
Klauzule (x || y) se prevedou na ekvivalentni tvar ( neg(x) => y ) [EDIT: zrejme se musi doplnit i ( neg(y) => x ) ] ... no a tohle interpretuji jako orientovany graf (na 2n vrcholech). A myslim plati, ze formule je splnitelna <-> pro kazde x plati, ze x a neg(x) nejsou ve stejne SSK. (potom by platilo x <=> neg(x)). No a to uz se da docela pekne otestovat.

Je to správně, alespoň podle wikipedie