Zkouskovy priklad

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.

Zkouskovy priklad

Příspěvekod joehill » 31. 12. 2007 11:10

Ahoj, koukam na zkouskove priklady z minulych let a s timhle prikladem nemuzu hnout:

Jaka je slozitost HK pro nadkubicke grafy (nadkubicky graf: Pro kazdy vrchol v plati deg(v) > 3)?
Navrhnete polynomialni algoritmus, nebo dokazte ze je NPU.

Na modrem je navrhovano reseni stylem prevodu HK na tento problem, ale to se mi zatim nedari, nevi nekdo, jak na to?
joehill
 

Re: Zkouskovy priklad

Příspěvekod beaver » 1. 1. 2008 13:54

Tak vezmeme si problem HK na obycejnem grafu G. To co bych chtel je, ze tuhle HK umim (polynomialne) prevest na HK pro nadkubicke grafy (tim ukazu, ze HK pro nadkubicke grafy je NPU problem, protoze obyc HK je taky NPU).

Rekneme, ze v G nejsou vrcholy se stupnem 1 (nebo mensim). Kdyby byly, pak tam nemuze HK existovat a umim ji vyloucit v polynomialnim case (coz pro nas neni vubec zajimave). Zaroven predpokladejme, ze zadny vrchol G neobsahuje smycku (tzn. hranu (v, v) pro nejake v). Kdyby graf smycky obsahoval, muzeme je beztrestne odstranit (HK to nijak neublizi).

Vsechny vrcholy v G maji ted stupen 2, nebo vetsi a neobsahuji smycky. Hurra - tak si tam ty smycky pridame (pro kazdy vrchol v, pridame hranu (v,v)). Pokud bereme neorientovane grafy, pak je stupen vsech vrcholu alespon 4.

Takze prevod tam uz mame a prevod zpet je taky jednoduchy - jen zahodime smycky. A to, ze jsou oba prevody polynomialni, je doufam videt. :D
Cožpak většina z nás svým způsobem nehledá svou kravičku?
T. Pratchett, z knihy "Kdepak je má kravička"
Uživatelský avatar
beaver
Matfyz(ák|ačka) level III
 
Příspěvky: 187
Registrován: 2. 2. 2007 09:33
Bydliště: Praha
Typ studia: Nestuduji ale učím na MFF

Re: Zkouskovy priklad

Příspěvekod gASK » 13. 1. 2008 11:37

Ahoj všichni.
Mám také "problém" s jedním zkouškovým příkladem - konkrétně MMNM (Monochromatická maximální nezávislá množina). Pokud si dobře pamatuji, maximální nezávislá množina je největší nezávislá množina na daném grafu co do počtu vrcholů. Potom nechápu, jak může fungovat transformace libovolné formule ze SAT - například (a) AND (a) mi udělá graf O - o - O (O=červené, o=černé), kde MNM je složena výlučně z červených, přitom ta formule je splnitelná. Co mi uniká? Pamatuji si blbě definici MNM nebo je tam nějaký fígl? :?:
When life gives you crap, make crap golems.
Uživatelský avatar
gASK
Admin(ka) level I
 
Příspěvky: 635
Registrován: 9. 6. 2005 11:33
Bydliště: Konečně Vinohrady:)
Typ studia: Informatika Mgr.
Login do SIS: BUREJ3BM

Re: Zkouskovy priklad

Příspěvekod twoflower » 13. 1. 2008 12:51

Ten tvuj priklad udela graf

Kód: Vybrat vše
o ----- o
| \     
|  \
|   \   
O    O


A otazku bych spis chapal takhle: "Lze vybrat na tom grafu takovou mnozinu (pouze) cernych vrcholu, ze je maximalni nezavisla (tj. nelze k ni pridat zadny cerveny vrchol)?" Pak je ta ekvivalence snad jasna..
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: Zkouskovy priklad

Příspěvekod gASK » 13. 1. 2008 13:34

Ok, v tom případě bych tam dal tři klauzule, pak by opět můj dotaz platil.

Ano, pokud to beru tak jak píšeš, tak to samozřejmě smysl dává. Jen to trochu koliduje s tím, co si představím pod pojmem "maximální nezávislá množina". Budiž tedy.
When life gives you crap, make crap golems.
Uživatelský avatar
gASK
Admin(ka) level I
 
Příspěvky: 635
Registrován: 9. 6. 2005 11:33
Bydliště: Konečně Vinohrady:)
Typ studia: Informatika Mgr.
Login do SIS: BUREJ3BM

Re: Zkouskovy priklad

Příspěvekod Wegguy » 20. 1. 2008 13:42

No, mně ta definice max. nezávislé množiny s tím řešením taky nesedí. Max. množina = nedá se vybrat větší, barva nebarva.

Ale napadlo mě, co takhle navíc spojit každé dva červené vrcholy (= formule) hranou?
Uživatelský avatar
Wegguy
Matfyz(ák|ačka) level I
 
Příspěvky: 7
Registrován: 20. 1. 2008 13:35
Typ studia: Informatika Mgr.

Re: Zkouskovy priklad

Příspěvekod gASK » 20. 1. 2008 13:54

V zadání je "maximální z hlediska inkluze" (měl jsem to u zkoušky), takže to je bráno tak, že je to taková množina, že do ní nelze přidat žádný další vrchol, aniž by přestala být nezávislá.
When life gives you crap, make crap golems.
Uživatelský avatar
gASK
Admin(ka) level I
 
Příspěvky: 635
Registrován: 9. 6. 2005 11:33
Bydliště: Konečně Vinohrady:)
Typ studia: Informatika Mgr.
Login do SIS: BUREJ3BM

Re: Zkouskovy priklad

Příspěvekod Wegguy » 20. 1. 2008 13:57

Aha...v tom případě řešení z modrého asi funguje, včetně důkazu NP.
Uživatelský avatar
Wegguy
Matfyz(ák|ačka) level I
 
Příspěvky: 7
Registrován: 20. 1. 2008 13:35
Typ studia: Informatika Mgr.

Re: Zkouskovy priklad

Příspěvekod Tuetschek » 20. 1. 2008 15:10

beaver píše:Tak vezmeme si problem HK na obycejnem grafu G. To co bych chtel je, ze tuhle HK umim (polynomialne) prevest na HK pro nadkubicke grafy (tim ukazu, ze HK pro nadkubicke grafy je NPU problem, protoze obyc HK je taky NPU).

Rekneme, ze v G nejsou vrcholy se stupnem 1 (nebo mensim). Kdyby byly, pak tam nemuze HK existovat a umim ji vyloucit v polynomialnim case (coz pro nas neni vubec zajimave). Zaroven predpokladejme, ze zadny vrchol G neobsahuje smycku (tzn. hranu (v, v) pro nejake v). Kdyby graf smycky obsahoval, muzeme je beztrestne odstranit (HK to nijak neublizi).

Vsechny vrcholy v G maji ted stupen 2, nebo vetsi a neobsahuji smycky. Hurra - tak si tam ty smycky pridame (pro kazdy vrchol v, pridame hranu (v,v)). Pokud bereme neorientovane grafy, pak je stupen vsech vrcholu alespon 4.

Takze prevod tam uz mame a prevod zpet je taky jednoduchy - jen zahodime smycky. A to, ze jsou oba prevody polynomialni, je doufam videt. :D
Tohle je fajn, ale uznaji to, kdyz jsou tam smycky? Neslo by to nejak bez nich?
Plug 'n' Pray.
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
 
Příspěvky: 656
Registrován: 15. 6. 2005 12:54
Typ studia: Informatika Mgr.

Re: Zkouskovy priklad

Příspěvekod matoman » 20. 1. 2008 15:21

tiez sa pripajam k vyssie uvedenej otazke. A navyse to v tom nevidim. Ved opacny prevod teda na HK ze odstranime slucky. Ved nadkubicky graf nemusi vobec obsahovat slucky. A je vobec co dokazovat Prevod HK -> nadkubicky HK,resp. opacne ked je to vlastne iba jeho specialny pripad.
Tento priklad mi je nejaky celkom nejasny
Uživatelský avatar
matoman
Matfyz(ák|ačka) level III
 
Příspěvky: 105
Registrován: 8. 1. 2005 20:12

Re: Zkouskovy priklad

Příspěvekod Tuetschek » 20. 1. 2008 15:24

Tuetschek píše:Tohle je fajn, ale uznaji to, kdyz jsou tam smycky? Neslo by to nejak bez nich?

Ted mi napadlo vrchol rozdvojit, pridat dalsi dva vrcholy a udelat si tam maly K4:
Kód: Vybrat vše
    o
   /|\
  / | \
->o-+--o->
  \ | /
   \|/
    o

A pro tohle pak dokazu, ze mam-li HK v tomhle, mam i HK v puvodnim grafu a naopak (HK v K4 se da dodelat jednoduse). Je tahle uvaha ale korektni?

Jako obecne ... ukazat ze nejaky podproblem je stejne tezky jako puvodni problem je v poradku, koukni se treba na 3-SAT a SAT.
Plug 'n' Pray.
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
 
Příspěvky: 656
Registrován: 15. 6. 2005 12:54
Typ studia: Informatika Mgr.

Re: Zkouskovy priklad

Příspěvekod gASK » 20. 1. 2008 15:30

Dejme tomu, že umím najít HK pro nadkubický graf. Výše popsaným převodem jsem schopen si libovolný graf převést na nadkubický graf a ten mu předhodit, takže pokud v původním grafu byla HK, on ji najde a naopak. Tedy jsem schopen zjistit existenci HK pro libovolný graf, což je jak víme NPÚ, takže původní problém musí být také NP-úplný. Nevidím na tom nic složitého ani problematického. Stejně tak nevím, v čem by měl být problém se smyčkama - jsou to normální hrany jako každé jiné (v zadání není nic o tom, že by neobsahoval smyčky či tak něco, jediná omezující podmínka je stupeň vrcholů).

EDIT: Tuetschekova verze bude taky fungovat a krom toho je to originální řešení :twisted:
When life gives you crap, make crap golems.
Uživatelský avatar
gASK
Admin(ka) level I
 
Příspěvky: 635
Registrován: 9. 6. 2005 11:33
Bydliště: Konečně Vinohrady:)
Typ studia: Informatika Mgr.
Login do SIS: BUREJ3BM

Re: Zkouskovy priklad

Příspěvekod Wegguy » 20. 1. 2008 16:22

Akorat bys tam asi musel dat tri vrcholy a udelat z toho K5, aby byl skutecne nadkubicky.
Uživatelský avatar
Wegguy
Matfyz(ák|ačka) level I
 
Příspěvky: 7
Registrován: 20. 1. 2008 13:35
Typ studia: Informatika Mgr.

Re: Zkouskovy priklad

Příspěvekod peci1 » 20. 1. 2012 01:03

Wegguy píše:Akorat bys tam asi musel dat tri vrcholy a udelat z toho K5, aby byl skutecne nadkubicky.

Spravna pripominka. A jeste potrebuje podobne osetrit i vrcholy se stupnem 3.
peci1
Matfyz(ák|ačka) level II
 
Příspěvky: 86
Registrován: 21. 1. 2009 20:08
Typ studia: Informatika Bc.

Re: Zkouskovy priklad

Příspěvekod peci1 » 21. 1. 2012 01:06

peci1 píše:
Wegguy píše:Akorat bys tam asi musel dat tri vrcholy a udelat z toho K5, aby byl skutecne nadkubicky.

Spravna pripominka. A jeste potrebuje podobne osetrit i vrcholy se stupnem 3.


A hned jsem si tenhle pristup overil na zkousce :) Funguje perfektne, bez jedine vyhrady.

Takze vrchol s deg(v) = 2 nahradim za: (tady ASCII art uz moc nestaci... proste si tam predstavte K5 :) )
Kód: Vybrat vše
      o---o
     /  x  \
----o------o---
     \  v  /
        o


A vrchol s deg(v) = 3 za
Kód: Vybrat vše
      o---o
     /  x  \
----o------o---
     \  v  /
        o
        |
        |
peci1
Matfyz(ák|ačka) level II
 
Příspěvky: 86
Registrován: 21. 1. 2009 20:08
Typ studia: Informatika Bc.


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