od macbeth » 31. 1. 2010 13:57
1.)suma x
i <= t, black box nam povie ano, ak existuje S
i: suma x
i cez prvky S
i = t
ide tam o pridavanie y
0 = 2
0, y
1 = 2
1, ... y
log_2 t = 2
log_2 t (tie log s dolnou celou castou), potom nasu instanciu tvoria x
j, y
i a t a pytame sa, ci sa da t poskladat z y
i... presne som to nepochopil, doplnte ma niekto...
2.) hviezda -- jeden vrchol v strede spojeny so vsetkymi vrcholmi usporiadanymi do kruhu okolo stredu... algoritmus vyberie nahodnu hranu a odstrani jej 2 vrcholy... pritom optimalne VP je tvorene len tym stredom... alebo nejaka modifikacia grafu tvoreneho dvojicami vrcholov spojenymi hranou, cosi ako
Kód: Vybrat vše
o o o o
| | | |
| | | | ...
o o o o
len tam treba vymysliet co s neparnym poctom...
3.) ideme od listov, tie neofarbime, ale ofarbime ich rodicov, potom odstranim hrany veduce medzi listami a ich rodicmi aj s danymi vrcholmi a iterujem... ofarbene vrcholy by mali byt potom VP... spravnost sa da dokazat podobne ako spravnost algoritmu B na prednaske, hrany su po 2 disjunktne, vybrana nemoze byt incidentna s inou potom...
hadam ma ostatni doplnia...
1.)suma x[sub]i[/sub] <= t, black box nam povie ano, ak existuje S[sub]i[/sub]: suma x[sub]i[/sub] cez prvky S[sub]i[/sub] = t
ide tam o pridavanie y[sub]0[/sub] = 2[sup]0[/sup], y[sub]1[/sub] = 2[sup]1[/sup], ... y[sub]log_2 t[/sub] = 2[sup]log_2 t[/sup] (tie log s dolnou celou castou), potom nasu instanciu tvoria x[sub]j[/sub], y[sub]i[/sub] a t a pytame sa, ci sa da t poskladat z y[sub]i[/sub]... presne som to nepochopil, doplnte ma niekto...
2.) hviezda -- jeden vrchol v strede spojeny so vsetkymi vrcholmi usporiadanymi do kruhu okolo stredu... algoritmus vyberie nahodnu hranu a odstrani jej 2 vrcholy... pritom optimalne VP je tvorene len tym stredom... alebo nejaka modifikacia grafu tvoreneho dvojicami vrcholov spojenymi hranou, cosi ako
[code]
o o o o
| | | |
| | | | ...
o o o o
[/code]
len tam treba vymysliet co s neparnym poctom...
3.) ideme od listov, tie neofarbime, ale ofarbime ich rodicov, potom odstranim hrany veduce medzi listami a ich rodicmi aj s danymi vrcholmi a iterujem... ofarbene vrcholy by mali byt potom VP... spravnost sa da dokazat podobne ako spravnost algoritmu B na prednaske, hrany su po 2 disjunktne, vybrana nemoze byt incidentna s inou potom...
hadam ma ostatni doplnia...