From 3a6b0f5f17f36619d5e74e266ef4d72c7a12a303 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 16 Jan 2012 00:18:08 +0100 Subject: [PATCH] APX: Cviceni --- 9-apx/9-apx.tex | 67 +++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 60 insertions(+), 7 deletions(-) diff --git a/9-apx/9-apx.tex b/9-apx/9-apx.tex index c382f01..f4e1d34 100644 --- a/9-apx/9-apx.tex +++ b/9-apx/9-apx.tex @@ -17,7 +17,7 @@ Ale co naplat, sv Na¹tìstí situace není zase tak beznadìjná. Nabízejí se tyto mo¾nosti, co si poèít: -\algo +\numlist\ndotted \:{\I Spokojit se s~málem.} Nejsou vstupy, pro které problém potøebujeme øe¹it, dostateènì malé, abychom si mohli dovolit pou¾ít algoritmus s~exponenciální slo¾itostí? Zvlá¹» kdy¾ takový algoritmus vylep¹íme @@ -38,7 +38,7 @@ po napøíklad pou¾ít aproximaèní algoritmus a poté jeho výsledek je¹tì heuristicky vylep¹ovat. Tak získáme øe¹ení, které zaruèenì není moc daleko od optima, a~pokud budeme mít ¹tìstí, bude k~nìmu velmi blízko. -\endalgo +\endlist \>Nyní si nìkteré z~tìchto technik pøedvedeme na konkrétních pøíkladech. @@ -70,7 +70,7 @@ list Bude pracovat s~polem znaèek~$M$, v~nìm¾ na poèátku bude v¹ude \ a postupnì obdr¾í \ v¹echny prvky hledané nezávislé mno¾iny. -\algo +\algo{NzMnaVeStromu} \algin Strom~$T$ s~koøenem~$v$, pole znaèek~$M$. \:$M[v] \= \$. \:Pokud je~$v$ list, skonèíme. @@ -99,7 +99,7 @@ Kdykoliv interval za ¾e je momentálnì volná, a~dal¹ím intervalùm budeme pøednostnì pøidìlovat volné barvy. Øeèeno v~pseudokódu: -\algo +\algo{BarveníIntervalù} \algin Intervaly $\left[ x_1, y_1 \right], \ldots, \left[ x_n, y_n \right]$. \:$b \= 0$ \cmt{poèet zatím pou¾itých barev} \:$B \= \emptyset$ \cmt{které barvy jsou momentálnì volné} @@ -270,7 +270,7 @@ Kdy nìjak zaokrouhlit. Optimální øe¹ení nové úlohy pak sice nemusí odpovídat optimálnímu øe¹ení té pùvodní, ale kdy¾ nastavíme parametry správnì, bude alespoò jeho dobrou aproximací. -\s{Základní my¹lenka:} +\ss{Základní my¹lenka:} \def\cmax{c_{\rm max}} @@ -288,8 +288,7 @@ $\varepsilon\cdot c^*$, mus Na~této my¹lence \uv{kvantování cen} je zalo¾en následující algoritmus. -\s{Algoritmus:} -\algo +\algo{AproximaceBatohu} \:Odstraníme ze~vstupu v¹echny pøedmìty tì¾¹í ne¾~$H$. \:Spoèítáme $\cmax=\max_i c_i$ a zvolíme $M=\lceil n/\varepsilon\rceil$. \:Kvantujeme ceny: Pro $i=1,\ldots,n$ polo¾íme $\hat{c}_i \= \lfloor c_i \cdot M/\cmax \rfloor$. @@ -358,4 +357,58 @@ v~polynomi V~na¹em pøípadì je dokonce slo¾itost polynomiální i v~závislosti na~$1/\varepsilon$, tak¾e schéma je {\I plnì polynomiální} (FPTAS -- Fully Polynomial-Time Approximation Scheme). +\exercises + +\ex{Popi¹te polynomiální algoritmus pro hledání nejmen¹ího vrcholového pokrytí stromu +(vrcholové pokrytí je mno¾ina vrcholù, která z~ka¾dé hrany obsahuje alespoò jeden vrchol.} + +\exx{Naleznìte polynomiální algoritmus pro hledání nejmen¹ího vrcholového pokrytí +bipartitního grafu.} + +\hint{Toky a øezy.} + +\ex{Uka¾te, jak v~polynomiálnì najít nejvìt¹í nezávislou mno¾inu v~intervalovém grafu.} + +\exx{Vyøe¹te v~polynomiálním èase 2-SAT, tedy splnitelnost formulí zadaných v~CNF, +jejich¾ klauzule obsahují nejvý¹e 2 literály.} + +\hint{Na ka¾dou klauzuli se mù¾eme podívat jako na implikaci.} + +\ex{Problém E3,E3-SAT je zesílením 3,3-SATu. Chceme zjistit splnitelnost formule v~CNF, její¾ ka¾dá +klauzule obsahuje právì tøi rùzné promìnné a ka¾dá promìnná se nachází v~právì tøech klauzulích. +Uka¾te, ¾e tento problém lze øe¹it efektivnì z~toho prostého dùvodu, ¾e ka¾dá taková formule je +splnitelná.} + +\hint{Pou¾ijte Hallovu vìtu.} + +\ex{Problém tøí loupe¾níkù: Je dána mno¾ina pøedmìtù s~cenami, chceme ji rozdìlit na 3 +èásti o~stejné cenì. Navrhnìte pseudopolynomiální algoritmus.} + +\ex{Problém \alg{MaxCut}: vrcholy zadaného grafu chceme rozdìlit do dvou mno¾in tak, +aby mezi mno¾inami vedlo co nejvíce hran. Jinými slovy chceme nalézt bipartitní podgraf +s~co nejvíce hranami. Rozhodovací verze tohoto problému je \NP-úplná, zkuste jej +v~polynomiálním èase 2-aproximovat.} + +\exx{V~problému \alg{MaxE3-SAT} dostaneme formuli v~CNF, její¾ ka¾dá klauzule obsahuje +právì~3 rùzné promìnné, a~chceme nalézt ohodnocení promìnných, pøi nìm¾ je splnìno co nejvíce +klauzulí. Rozhodovací verze je \NP-úplná. Uka¾te, ¾e pøi náhodném ohodnocení promìnných +je splnìno v~prùmìru $7/8$ klauzulí. Z~toho odvoïte deterministickou $7/8$-aproximaci +v~polynomiálním èase. +} + +\exx{Uva¾ujme následující algoritmus pro nejmen¹í vrcholové pokrytí grafu. Graf projdeme +do hloubky, do výstupu vlo¾íme v¹echny vrcholy vzniklého DFS stromu kromì listù. Doka¾te, +¾e vznikne vrcholové pokrytí a ¾e 2-aproximuje to nejmen¹í.} + +\hint{Najdìte v~$G$ párování obsahující alespoò tolik hran, kolik je polovina poètu +vrcholù vráceného pokrytí. Jak velikost párování souvisí s~velikostí nejmen¹ího vrcholového +pokrytí?} + +\exx{V~daném orientovaném grafu hledáme acyklický podgraf s~co nejvíce hranami. +Navrhnìte polynomiální 2-aproximaèní algoritmus.} + +\hint{Libovolné oèíslování vrcholù rozdìlí hrany na \uv{dopøedné} a \uv{zpìtné}.} + +\endexercises + \bye -- 2.39.2