[Zk] 4.2.2009

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: [Zk] 4.2.2009

Re: [Zk] 4.2.2009

od Che » 8. 2. 2009 15:13

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 :)

Re: [Zk] 4.2.2009

od twoflower » 7. 2. 2009 09:34

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

Re: [Zk] 4.2.2009

od Myshaak » 4. 2. 2009 17:50

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.

Re: [Zk] 4.2.2009

od Osiris » 4. 2. 2009 15:42

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! :)

[Zk] 4.2.2009

od Prince_of_Persia » 4. 2. 2009 11:06

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

Nahoru