Nové příklady na cvičení

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.
Uživatelský avatar
tutchek
Site Admin
Příspěvky: 795
Registrován: 21. 9. 2004 00:40
Typ studia: Informatika Mgr.
Bydliště: Praha, Bohnice
Kontaktovat uživatele:

Nové příklady na cvičení

Příspěvek od tutchek »

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.
exAdmin. Magistr přes umělou inteligenci. Právník přes daně.
Uživatelský avatar
macbeth
Matfyz(ák|ačka) level III
Příspěvky: 201
Registrován: 11. 2. 2005 14:48
Typ studia: Informatika Mgr.
Bydliště: PPraha
Kontaktovat uživatele:

Re: Nové příklady na cvičení

Příspěvek od macbeth »

1.)suma xi <= t, black box nam povie ano, ak existuje Si: suma xi cez prvky Si = t
ide tam o pridavanie y0 = 20, y1 = 21, ... ylog_2 t = 2log_2 t (tie log s dolnou celou castou), potom nasu instanciu tvoria xj, yi a t a pytame sa, ci sa da t poskladat z yi... 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...
Nieco, co by nejavilo ziadne znamky bytia, teda by sa nijak neprejavovalo ako sucno, by nebolo niecim, ale prave nicim...
Uživatelský avatar
Blaf
Matfyz(ák|ačka) level I
Příspěvky: 12
Registrován: 28. 1. 2008 12:13
Typ studia: Informatika Bc.

Re: Nové příklady na cvičení

Příspěvek od Blaf »

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 G3 je hamiltonovsky" a z trojuhelnikovy nerovnosti pak plyne, ze kruznice nebude delsi, nez trojnasobek minimalni kostry.
Odpovědět

Zpět na „TIN062 Složitost I“