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

[Zk] 4.2.2009

Příspěvek od Prince_of_Persia »

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

Příspěvek od Osiris »

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
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
Příspěvky: 162
Registrován: 18. 1. 2006 22:29
Typ studia: Informatika Mgr.

Re: [Zk] 4.2.2009

Příspěvek od Myshaak »

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

Příspěvek od twoflower »

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
Che
Donátor
Donátor
Příspěvky: 166
Registrován: 2. 6. 2005 12:29
Typ studia: Informatika Mgr.
Bydliště: EU
Kontaktovat uživatele:

Re: [Zk] 4.2.2009

Příspěvek od Che »

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
Odpovědět

Zpět na „TIN062 Složitost I“