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...
[Zk] 4.2.2009
-
- Matfyz(ák|ačka) level II
- Příspěvky: 81
- Registrován: 19. 1. 2006 15:53
- Typ studia: Informatika Mgr.
- Login do SIS: prinf5am
- Bydliště: Jindřichův Hradec
- Kontaktovat uživatele:
-
- Supermatfyz(ák|ačka)
- Příspěvky: 403
- Registrován: 11. 11. 2006 14:10
- Typ studia: Informatika Mgr.
- Bydliště: Praha
- Kontaktovat uživatele:
Re: [Zk] 4.2.2009
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!
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
- Myshaak
- Matfyz(ák|ačka) level III
- Příspěvky: 162
- Registrován: 18. 1. 2006 22:29
- Typ studia: Informatika Mgr.
- Login do SIS: michp5am
Re: [Zk] 4.2.2009
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 )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?
...
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.
"Go for the eyes Boo, go for the eyes! Yeahh!!"
- twoflower
- Supermatfyz(ák|ačka)
- Příspěvky: 445
- Registrován: 22. 9. 2004 21:07
- Typ studia: Informatika Ph.D.
- Kontaktovat uživatele:
Re: [Zk] 4.2.2009
Známý algoritmus využívající SSK běží v O(n).Osiris píše:Celkovej čas O(n^3), nevíte někdo, zda to jde lépe?
- Che
- Donátor
- Příspěvky: 166
- Registrován: 2. 6. 2005 12:29
- Typ studia: Informatika Mgr.
- Login do SIS: przyc4am
- Bydliště: EU
- Kontaktovat uživatele:
Re: [Zk] 4.2.2009
Je to správně, alespoň podle wikipedieMyshaak píše: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 )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?
...
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.
shoot that shit