# Nové příklady na cvičení

<{ForumPost(poster="tutchek", timestamp=2010-01-31 12:57:05)}>
Oproti loňským letům díky lehké reorganizaci zmizelo pár příkladů řešených na cvičení a oproti tomu přibyla hromada jiných. Nemáte hinty jak na ně?  
  
5. cvičení  
1.Nechť máme k dispozici „černou skřínku“, která umí řešit rozhodovací verzi problému součtu podmnožiny v polynomiálním čase. Skřínka odpovídá pouze ANO-NE. Zkonstruujte algoritmus, který pro daný vstup optimalizační verze problému součtu podmnožiny najde v polynomiálním čase (vzhledem k délce binárního zápisu vstupních dat) optimální řešení.  
2.Popište jak lze pro libovolné dané n zkonstruovat graf na n vrcholech takový, že aproximační algoritmus pro vrcholové pokrytí s poměrovou chybou r=2 (prezentovaný na přednášce) na tomto grafu vrací pokrytí právě dvakrát větší než je velikost optimálního vrcholového pokrytí (tj. ukažte, že dokázaný odhad poměrové chyby je těsný).  
3.Navrhněte algoritmus, který v polynomiálním čase nalezne optimální vrcholové pokrytí pro neorientovaný graf bez cyklů (les, strom).  
4.Bottleneck TSP: vstupem je úplný ohodnocený neorientovaný graf s nezápornými váhami na hranách (stejně jako u obyčejného TSP), o kterých navíc předpokládáme, že splňují trojúhelníkovou nerovnost. Úkolem je opět najít nejkratší Hamiltonovskou kružnici ve vstupním grafu, ovšem délka kružnice není v tomto případě rovna součtu délek hran na kružnici, ale maximu z délek hran na kružnici. Nejdříve dokažte, že Bottleneck TSP je NP-těžký a poté navrhněte polynomiální aproximační algoritmus s poměrovou chybou r=3.
<{/ForumPost}>

<{ForumPost(poster="macbeth", timestamp=2010-01-31 13:57:37)}>
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 

    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...
<{/ForumPost}>

<{ForumPost(poster="Blaf", timestamp=2010-02-02 23:19:55)}>
4) BottleneckTSP  
prevod HK $\propto$ BTSP skoro stejnej, jako u normalniho TSP: nehrany ohodnotim 2, hrany 1 a ptam se, jestli existuje kruznice vahy 1. Aproximacni algoritmus se zase dela pres min. kostru, vyuziju fakt, ze "G je souvisly $\Rightarrow$ G<sup>3</sup> je hamiltonovsky" a z trojuhelnikovy nerovnosti pak plyne, ze kruznice nebude delsi, nez trojnasobek minimalni kostry.
<{/ForumPost}>