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

Zkouskovy priklad

Příspěvek od joehill »

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?
Uživatelský avatar
beaver
Matfyz(ák|ačka) level III
Příspěvky: 189
Registrován: 2. 2. 2007 09:33
Typ studia: Nestuduji ale učím na MFF
Bydliště: Praha

Re: Zkouskovy priklad

Příspěvek od beaver »

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"
gASK
Admin(ka) level I
Příspěvky: 635
Registrován: 9. 6. 2005 12:33
Typ studia: Informatika Mgr.
Bydliště: Konečně Vinohrady:)
Kontaktovat uživatele:

Re: Zkouskovy priklad

Příspěvek od gASK »

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
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: Zkouskovy priklad

Příspěvek od twoflower »

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..
gASK
Admin(ka) level I
Příspěvky: 635
Registrován: 9. 6. 2005 12:33
Typ studia: Informatika Mgr.
Bydliště: Konečně Vinohrady:)
Kontaktovat uživatele:

Re: Zkouskovy priklad

Příspěvek od gASK »

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
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ěvek od Wegguy »

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?
gASK
Admin(ka) level I
Příspěvky: 635
Registrován: 9. 6. 2005 12:33
Typ studia: Informatika Mgr.
Bydliště: Konečně Vinohrady:)
Kontaktovat uživatele:

Re: Zkouskovy priklad

Příspěvek od gASK »

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
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ěvek od Wegguy »

Aha...v tom případě řešení z modrého asi funguje, včetně důkazu NP.
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:

Re: Zkouskovy priklad

Příspěvek od Tuetschek »

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
matoman
Matfyz(ák|ačka) level III
Příspěvky: 105
Registrován: 8. 1. 2005 20:12
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: Zkouskovy priklad

Příspěvek od matoman »

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
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:

Re: Zkouskovy priklad

Příspěvek od Tuetschek »

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.
gASK
Admin(ka) level I
Příspěvky: 635
Registrován: 9. 6. 2005 12:33
Typ studia: Informatika Mgr.
Bydliště: Konečně Vinohrady:)
Kontaktovat uživatele:

Re: Zkouskovy priklad

Příspěvek od gASK »

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
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ěvek od Wegguy »

Akorat bys tam asi musel dat tri vrcholy a udelat z toho K5, aby byl skutecne nadkubicky.
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ěvek od peci1 »

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ěvek od peci1 »

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

Zpět na „TIN062 Složitost I“