Zkouska 26.1

Návštěvník

Zkouska 26.1

Příspěvek od Návštěvník »

Tak dnes nas na pisomke (teda aspon mna) Cepek nemilo prekvapil tymito prikladmi:

1. Predpokladejme, ze mame 2n (po dvou ruznych) prvku a1,a2,...,a2n, ktere chceme rozdelit na n nejmensich a nejvetsich. Dokazte, ze pote co tridici sit paralelne setridi prvky a1,...,an a prvky an+1,an+2,...,a2n postacuje jiz k dosazeni vysledku sit konstantni hloubky.

2. Problem Vrcholoveho pokryti (VP) lze sformulovat nasledovne:
Zadani: Neorientovany graf G(V,E) a prirozene cislo k.
Otazka: Existuje podmonozina vrcholov W (W je podmnozina V) velikosti nejvyse k, ktera pokryva vsetky hrany, t.j. W takova, ze kazda hrana ma aspon jeden zo svojich koncovych vrcholov na mnozine W?
Dokazte, ze je tento porblem NP-uplny. K dukazu jeho NP tezkosti pouzijte nektery z NP-uplnych problemu probiranych na prednasce, t.j. nektery problem z mnoziny(KLIKA, HK, TSP,SP,ROZ,SAT)

3. Mejme nasledujici aproximacni algoritmus pro hledani minimalneho Vrcholoveho Pokryti VP (t.j VP obsahujici nejmensi mozny pocet vrcholu). Dokud graf obsahuje nejake hrany, tak opakuj nasledujici akci: vyber vrchol nejvyssiho stupne (pokud je takych vice, tak vyber libovolny z nich), pridej ho do pokryti a z grafu odstran vsechny hrany incidentni s vybranym vrcholem. Dokazte nebo vyvratte: uvedeny aproximacny algoritmus ma (na mnozine vsech zadani VP) pomerovou chybu 0<=2 (0 mene rovno 2).


NEviem ako vam, ale mne to nepride az tak jednoduche. Ked som uz na tej skuske bol tak som si to aspon opisal, aby ste si to tu precitali. Ja som z toho nic neodovzdal. :cry:
Ak niekto viete ako vyriesit nejaky z tych to prikladov tak to tu prosim hodte.

vela stastia.
Uživatelský avatar
Eubie
Matfyz(ák|ačka) level III
Příspěvky: 295
Registrován: 8. 10. 2005 15:35
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Příspěvek od Eubie »

Tak to je maso.
Uživatelský avatar
xstyler
Matfyz(ák|ačka) level II
Příspěvky: 66
Registrován: 29. 1. 2005 12:27
Typ studia: Informatika Bc.
Bydliště: EU

Příspěvek od xstyler »

Druhá úloha sa dokazuje pomocou kliky a doplnkového grafu, kde doplnkový graf grafu G(V,E) je graf G'(V,E'), ktorý obsahuje všetky hrany, ktoré pôvodný graf neobsahuje. Potom platí, že vrcholy, ktoré v grafe G NETVORIA kliku, sú vrcholovým pokrytím grafu G'. Skúste si to nakresliť a hneď vám to bude jasné.
lukumo
Matfyz(ák|ačka) level I
Příspěvky: 13
Registrován: 10. 6. 2005 00:38
Typ studia: Informatika Mgr.

Příspěvek od lukumo »

Tak ten prvni nebyl zas tak tezky. nechate setridit ty dve posloupnosti delky n a pak staci porovnat nejmensi z prvni posloupnosti s nejvetsim v druhe posloupnosti, druhy nejmensi s druhym nejvetsim ... atd az porovnate nejvetsi z prvni s nejmensim v druhe. Ty ktere vypadnou z techto porovnani jako mensi tvori n-tici mensich, ty vetsi tvori n-tici ... vetsich. Tedy staci vam k tomu n komparatoru v jedne vrstve. K dukazu ... no ono je to skoro videt. Kdyz to porovnavate tak az do urciteho indexu vsechny ty porovnani "vyhrava" jedna posloupnost. (bude tam stejna nerovnost bud > nebo <). No a kdyz to dopadne opacne, tak zase musi uz porad vyhravat ta druha posloupnost. Jestli to neni jasny doporucuju si to nakreslit :) (take jsem to tak nejdrive udelal), treba pro 2n=8.

Po ustnim jsem se ptal na ten treti ... a ten odhad nefunguje. Ale konstrukce protiprikladu je obtizna (podle slov zkousejiciho). Zacina se nejak s (alespon)12-dvojicema vrcholu spojene hranou (dvojice mezi sebou ma hranu)... pod to se prida vrstva o 1 mensi, napojena na tu jednu radu dvojic, pod to dalsi vrstva, pod to dalsi .. az zbyde jeden vrchol. Ten algoritmus bude postupovat od spoda a postupne ubirat ty vrstvy az zase zbudou ty dvojice (tu pak nejak rozebere). Pritom optimum jsou vrcholy z dvojice, na ktere jsou napojeny vsechny ty spodni vrstvy ...
Uživatelský avatar
laliebijard
Matfyz(ák|ačka) level III
Příspěvky: 168
Registrován: 8. 6. 2005 10:26
Typ studia: Informatika Mgr.

2. priklad

Příspěvek od laliebijard »

K tomu 2. pr. este, ze mi sme to na cvikach robili aj pomocou 3 - SAT (t. j. v kazdej klauzuli, ci co to je su prave tri literaly).
A to tak, ze pre kazdu klauzulu sa nakresli trojuholnik, pre kazdy literal hrana (u, non(u)), ktora sa potom pripoji k trojuholniku danej klauzule a to tak, ze ak je v klauzuli u, tak sa pripoji k trojuholniku, u, inac non(u).
A potom, kladne ohodnotenie jednotlivych premennych dava k-vrcholove pokrytie daneho grafu a k=<pocet premennych> + 2*<pocet klauzuli>.
Plus este v kazdom trojuholniku treba oznacit dva dalsie vrcholy (preto ta dvojka v tom vztahu).

A tak.
qk
Matfyz(ák|ačka) level III
Příspěvky: 181
Registrován: 24. 2. 2005 10:03
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Příspěvek od qk »

nomohla by se ta trojka resit tak, ze bych si vzal graf, kde by byly 2 hvezdy (stred + dejmetomu 12 vrcholu spojenych se stredem) a ty by byli spojene useckou. Tenhle algoritmus by potom vybral jeden ze stredu ty hvezdy a vzal ho a i jeho sousedy, takze by zustalo 12 rozpojenych vrcholu...takze 13 vrchlolu je k, zatimco idealni reseni ma k jen dva....nebo je to blbost?
Don't worry, be dead
Návštěvník

Příspěvek od Návštěvník »

qk píše:nomohla by se ta trojka resit tak, ze bych si vzal graf, kde by byly 2 hvezdy (stred + dejmetomu 12 vrcholu spojenych se stredem) a ty by byli spojene useckou. Tenhle algoritmus by potom vybral jeden ze stredu ty hvezdy a vzal ho a i jeho sousedy, takze by zustalo 12 rozpojenych vrcholu...takze 13 vrchlolu je k, zatimco idealni reseni ma k jen dva....nebo je to blbost?
Pokud jsem to dobre pochopil, tak algoritmus bere vrcholy od tech s nejvetsim stupnem, takze by vzal jeden stred, dal ho do pokryti, vsechny hrany s nim spojene odstranil a pak sel na druhy stred. Ten by taky hodil do pokryti a uz by mu nezustala zadna hrana. Takze idealni pripad.
qk_

Příspěvek od qk_ »

jo mas pravdu, sem se prekoukl, sem myslel ze odstrnuje sousedici vrcholy
Uživatelský avatar
SaNuel
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 11. 10. 2018 14:52
Typ studia: Informatika Bc.

Re: Zkouska 26.1

Příspěvek od SaNuel »

3. Najbližšie k odpovedi je asi toto: http://cgi.csc.liv.ac.uk/~michele/TEACH ... 10.4.4.pdf - "Clever Greedy Algorithm"

Keby sa niekomu nechcelo čítať a lúštiť, (čo sa mne určite nechcelo):
Buď graf
G = (L \cup R_1 \cup R_2 \cup ... \cup R_n, E),
kde L je n vrcholov. R_i následne množina n/i vrcholov, ktoré sú spojené postupne s i-ticou vrcholov z L. Teda v R_1 každý spojený s 1 vrcholom z L, v R_2 každý spojený s dvojicou vrcholov z L ... a R_n jediný vrchol spojený so všetkými vrcholmi z L. (pre referenciu kukni na obrázčok vyššie v pdf).

Aproximačný algoritmus vezme vždy vrchol z R_i pre max i. Tak teda použije k \le \frac{n^2+n}{2} vrcholov (v prípade násobku (n,n-1,...,1) práve toľko vrcholov), pričom optimálny vezme vrcholy z L, teda n vrcholov. Odtiaľ asi jasne vidno, že APPROX > 2OPT.

Nuž, i je tu háčik, a síce, že v počiatočnom bode chodu aproximačného algoritmu majú vrcholy z L rovnaký stupeň ako v maximálnom R. Ale ako sa aj v pdf vyššie píše, náhoda je blbec, teda ak sa podarí, podarí sa aj riadna pomerová chyba.
Ono dalo by sa aj vypočítať priemerná odchýlka nejakou strašidelnou sumou všetkých možných chodov approximačného algoritmu (čo by vyšlo n/2... žeby? Možno?), no to už asi zabŕdam do iného predmetu. Berte teda na vlastné uváženie.

Kód: Vybrat vše

if ( exam.date > critical_date ) {
    this.procrastination.enable();
    Steam.launch("Skyrim");
}
else {
    this.panic.start();
    // TODO: This isn't working...
}
[/size]
Odpovědět

Zpět na „2005“