Skuska 6.2.

Uživatelský avatar
rastik
Supermatfyz(ák|ačka)
Příspěvky: 661
Registrován: 19. 10. 2005 21:45
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Skuska 6.2.

Příspěvek od rastik »

1) Aho-Corasick na {strom, stroj, postroj, trojka}.

2) Dany graf ako mriezka n x n, v nom vybranych m vrcholov. Najdite polynomialny algoritmus, ktory rozhodne ci existuju vrcholovo disjunktne cesty z tychto m vrcholov do vrcholov na okraji mriezky. Pokial je vybrany vrchol na okraji, tak uz dalsi cestu nepotrebuje. Je mozne pouzit akykolvek algoritmuz z prednasky.

3) Dokazat, ze problem rozhodnotia ci existuje v grafe G indukovany podgraf izomorfny s grafom H je NP-uplny problem. Je mozne vyuzit problemy KLIKA, HK, TSP, SP, ROZ a SAT.
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Příspěvek od hippies »

Neměl by tu někdo autorské řešení na 2. a 3. příklad?
Uživatelský avatar
rastik
Supermatfyz(ák|ačka)
Příspěvky: 661
Registrován: 19. 10. 2005 21:45
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Příspěvek od rastik »

2) Cez toky v sietach. Detailnejsie neviem, pretoze viac mi z riesenia neuznal (a ja sam som v case medzi pisomkou a ustnou zistil, ze to mam zle).

3) Pomocou kliky. Zadanie problemu kliky prevedies na zadanie IP. Teda: pokial mas najst k-kliku v grafe, tak vytvoris uplny graf na k vrcholoch a hladas ho ako podgraf. Teda slozitost hladania podgrafu je aspon tak velka, ako kliky.

Dolezite u prikladov, kde sa dokazuje NP-uplnost dokazat, ze problem je z NP. Ja som urobil iba dokaz NP-tazkosti, na NP zlozitost som zabudol. Bolo za to 1/4 bodu dole.
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Příspěvek od hippies »

rastik píše: 3) Pomocou kliky. Zadanie problemu kliky prevedies na zadanie IP. Teda: pokial mas najst k-kliku v grafe, tak vytvoris uplny graf na k vrcholoch a hladas ho ako podgraf. Teda slozitost hladania podgrafu je aspon tak velka, ako kliky.

Dolezite u prikladov, kde sa dokazuje NP-uplnost dokazat, ze problem je z NP. Ja som urobil iba dokaz NP-tazkosti, na NP zlozitost som zabudol. Bolo za to 1/4 bodu dole.
Jasně sem blbej, sem to dělal na druhou stranu, taková začátečnická chyba :? ,... To nestačí udělat ten převod jako důkaz NP-úplnosti? Jak se to teda dotáhne?
Uživatelský avatar
MyS
Donátor
Donátor
Příspěvky: 178
Registrován: 22. 9. 2004 00:13
Typ studia: Informatika Bc.
Bydliště: The city of Dobříš
Kontaktovat uživatele:

Příspěvek od MyS »

Mno, problem NPC musi byt NPhard (dokaze se prevodem) a lezet v NP (dokaze se "certifikatem", tj. kdyz mi nekdo da to izomorfni zobrazeni, tak v P overim, ze je to splneno).

K tem tokum...resi se to v zasade takhle: vyznacene vrcholy se spoji se zdrojem (hrana kap 1), vrcholy na krajich se stokem (hrana kap 1). Co se tyce disjunktnosti cest, tak to se provede tak, ze se uvazi orientovany graf a vsechny vrcholy (body mrize) se rozdeli na pulky, prvni je vstupni, druha vystupni a jsou spojeny hranou kap 1.
We don't need no education!
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Příspěvek od hippies »

MyS píše:Mno, problem NPC musi byt NPhard (dokaze se prevodem) a lezet v NP (dokaze se "certifikatem", tj. kdyz mi nekdo da to izomorfni zobrazeni, tak v P overim, ze je to splneno).
Můžeš být konkrétnější u toho certifikátu? Ani nevim co to je.
Uživatelský avatar
MyS
Donátor
Donátor
Příspěvky: 178
Registrován: 22. 9. 2004 00:13
Typ studia: Informatika Bc.
Bydliště: The city of Dobříš
Kontaktovat uživatele:

Příspěvek od MyS »

Cepek to ma ve slidech. NP trida je definovana tak, ze algoritmus jede v pol. case, kdyz za nej nekdo provadi rozhodnuti (tj. pracuje nedeterministicky)...nejaka vestirna. Mno, a ty napovedy pro kladnou odpoved ANO jsou ten certifikat. Treba kdyz je NPC zda ma graf kliku vel. aspon k, tak certifikat je ta mnozina vrcholu. Overeni je snadne.
We don't need no education!
Uživatelský avatar
luk
Matfyz(ák|ačka) level II
Příspěvky: 74
Registrován: 6. 6. 2005 18:32
Typ studia: Informatika Mgr.
Bydliště: Praha

Příspěvek od luk »

hippies píše:Neměl by tu někdo autorské řešení na 2. a 3. příklad?
Ten druhý příklad jsem řešil následovně:
I. Přidal jsem ke grafu jeden vrchol, který jsem označil jako zdroj a natáhl z něj hrany s jednotkovou kapacitou ke všem černým vrcholům uvnitř mřížky (ne těm na okraji)
II. Obdobně jsem přidal stok a hrany s jednotkovými kapacitami z bílých vrcholů na okraji.
III. Pak jsem přidělil všem hranám mezi vrcholy na okraji a těm, které vycházely z černých vrcholů na okraji kapacitu 0 a zbylým 1.
IV. Pomocí Ford-Fulkersona jsem našel max. tok (Ford-Fulkerson je na sítích s jednotkovými kapacitami nejrychlejší) a díval jsem se na jeho velikost.
Výsledek: Označím-li m' počet černých vrcholů bez těch na okraji, pak pokud
- byl max. tok >= m' tyto cesty existovaly
- jinak ne

:!: Je v tom ještě jedna drobnost a to, že takhle by ten algo nezajistil vrcholovou disjunktnost těch cest, ale to se vyřeší fíglem:
Každý vrchol se rozdělí na dva, do jednoho povedou všechny vstupní hrany z druhého půjdou všechny výstupní a mezi nimi povede jen hrana kapacity 1.
Pak to funguje (alespoň zkoušející to uznal :D )
Třetí příklad jsem zvoral, ale i tak jsem dostal z písemky 2 body a nakonec jedničku, takže hlavu vzhůru, není to tak zlé :)

Přeji všem, které to ještě čeká hodně štěstí a na viděnou v dalším semestru :D
Luk
Uživatelský avatar
Necroman
Supermatfyz(ák|ačka)
Příspěvky: 459
Registrován: 20. 1. 2005 19:46
Typ studia: Informatika Mgr.
Bydliště: Louny / kolej Jednota, Praha
Kontaktovat uživatele:

Re:

Příspěvek od Necroman »

Dnesni Algoritmy me opravdu prekvapily... za celou dobu skoro nebylo videt Cepka, jen Petra Kuceru. Pisemku bych povazoval vyhledem k tem predchozim za ponekud lehci...
Dvojku jsem resil ponekud nedeterministicky :roll: , takze za nula, ale jinak +- dobre. Na ustni me vzal opet Petr Kucera, tam jsem mu popsal "se vsema chlupama" binarni scitacku... nejak nemohl prijit na protipriklad a tak mi dal za jedna... :D
Takovy postreh, nevim jak jinde, ale u P. Kucery vysledek z testu nijak nesouvisi s ustnim, je to jen takova podminka ustni zkousky... staci dva body a umet ustni otazku a mate to! Hodne stesti vsem, kteri na to teprve jdou :wink: !
WANTED:
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
Uživatelský avatar
MyS
Donátor
Donátor
Příspěvky: 178
Registrován: 22. 9. 2004 00:13
Typ studia: Informatika Bc.
Bydliště: The city of Dobříš
Kontaktovat uživatele:

Příspěvek od MyS »

Jj, souhlas, dnesni pisemka byla jedna z tech lehcich. Hmm, s tim Fulkesonem (oproti jinym alg) je to chytry. Mno, me zkousel David Kronus a tam se vysledek ustniho (pro me nastesti) odviji od pisemky silne.
We don't need no education!
Uživatelský avatar
Oscar
Donátor
Donátor
Příspěvky: 26
Registrován: 13. 11. 2004 13:52
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Příspěvek od Oscar »

Tak ... u pana Cepka ide aj o pisomnu aj o ustnu cast.
Z pisomky som mal 2 3/4 bodu (som zabudol napisat ze ten problem v 3ke je z triedy NP) a na ustnej som trochu zjednodusil par dokazov (niezeby som ich nevedel, ale nebolo to "ono"). Vraj prehlad mam aj viem o co ide, ale ...
Tak som dostal za 2. :?

Nieze by mi to vadilo, ale ... :cry: (mal som sa viac ucit)
Ale som aj tak rad, ze si to nebudem musiet zopakovat, tie minule otazky boli drsne.
Uživatelský avatar
rastik
Supermatfyz(ák|ačka)
Příspěvky: 661
Registrován: 19. 10. 2005 21:45
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re:

Příspěvek od rastik »

Necroman píše:Dnesni Algoritmy me opravdu prekvapily... za celou dobu skoro nebylo videt Cepka, jen Petra Kuceru.
Cepek dnes cele doobedie skusal na SZZ. Ale oblek mu dlho nevydrzal a bol sa prezliect :D
Uživatelský avatar
rastik
Supermatfyz(ák|ačka)
Příspěvky: 661
Registrován: 19. 10. 2005 21:45
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Příspěvek od rastik »

MyS píše:K tem tokum...resi se to v zasade takhle: vyznacene vrcholy se spoji se zdrojem (hrana kap 1), vrcholy na krajich se stokem (hrana kap 1). Co se tyce disjunktnosti cest, tak to se provede tak, ze se uvazi orientovany graf a vsechny vrcholy (body mrize) se rozdeli na pulky, prvni je vstupni, druha vystupni a jsou spojeny hranou kap 1.
A jeje, uz som nebol daleko. Nevedel som ale vyriesit tu vrcholovu disjunktnost.
Uživatelský avatar
stviper
Matfyz(ák|ačka) level I
Příspěvky: 14
Registrován: 23. 1. 2005 18:12
Typ studia: Informatika Bc.
Bydliště: Troja
Kontaktovat uživatele:

Příspěvek od stviper »

Ja si tiez myslim ze pisomka bola najlahsia zo vsetkych co zatial boli. Teda aspon mne sa to zda. Pocul som ze na ustnu beru aj tych co maju 1,5 boda a je este sanca aby ste dostali 2.
Na ustnej ma skusal ten druhy doktorant (nie Kucera). Bolo to v pohode pytal sa na Triediace siete (vsetko co o tom viem). Mohol som si vybrat nejaku a popisat ju. Samozrejme ze som si vybral Merge sort (jedina tried. siet ktoru poznam :) ). Druha otazka bola aby som povedal co viem o verejneom a sukromnom kluci.
Chalan co tam bol so mnou dostal aproximacne algoritmy a mal si vybrat jeden priklad a dokazat ho.
Vela stastia. :wink:
Odpovědět

Zpět na „2005“