[Zk] 4.2.2009

Základní přednáška o teorii složitosti algoritmů. Zhruba první polovina přednášky je věnována studiu složitosti konkrétních algoritmů různých typů (grafové, rozděl a panuj, hladové na matroidech) pracujících v polynomiálním čase. Složitost je zkoumána jak "klasicky" (složitost v nejhorším případě), tak amortizovaně. Druhá polovina přednášky je pak věnována studiu třídy NP, polynomiální převoditelnosti problémů a důkazům NP-úplnosti problémů. Závěr přednášky je věnován tématům souvisejícím se studiem NP-úplnosti: pseudopolynomiálním algoritmům a silné NP-úplnosti, početním úlohám a třídě #P.

[Zk] 4.2.2009

Příspěvekod 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...
Prince_of_Persia
Matfyz(ák|ačka) level II
 
Příspěvky: 81
Registrován: 19. 1. 2006 15:53
Bydliště: Jindřichův Hradec
Typ studia: Informatika Mgr.
Login do SIS: prinf5am

Re: [Zk] 4.2.2009

Příspěvekod 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! :)
Osiris
Osiris
Supermatfyz(ák|ačka)
 
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Bydliště: Praha
Typ studia: Informatika Mgr.

Re: [Zk] 4.2.2009

Příspěvekod 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.
"Go for the eyes Boo, go for the eyes! Yeahh!!"
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
 
Příspěvky: 161
Registrován: 18. 1. 2006 22:29
Bydliště: Tanvald / Troja A820
Typ studia: Informatika Mgr.

Re: [Zk] 4.2.2009

Příspěvekod 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).
Uživatelský avatar
twoflower
Supermatfyz(ák|ačka)
 
Příspěvky: 445
Registrován: 22. 9. 2004 20:07
Typ studia: Informatika Ph.D.

Re: [Zk] 4.2.2009

Příspěvekod 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 :)
shoot that shit
Uživatelský avatar
Che
Donátor
Donátor
 
Příspěvky: 166
Registrován: 2. 6. 2005 11:29
Bydliště: EU
Typ studia: Informatika Mgr.
Login do SIS: przyc4am


Zpět na TIN062 Složitost I

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron