X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=10-prevody%2F10-prevody.tex;h=d5e4de090efd2f47a836ed5474cca9472a5c098f;hb=30640a35bdff6f4f89a6846f17b5331cf0f03a2b;hp=53abdb2afc20c127c13b72bb8e8d1e8fe42be662;hpb=8fd7530a52f4c19dccc1c9a8f29f2ca987458319;p=ads2.git diff --git a/10-prevody/10-prevody.tex b/10-prevody/10-prevody.tex index 53abdb2..d5e4de0 100644 --- a/10-prevody/10-prevody.tex +++ b/10-prevody/10-prevody.tex @@ -6,63 +6,59 @@ \s{Definice:} {\I Rozhodovací problém} je takový problém, jeho¾ výstupem je v¾dy {\sc ano}, nebo {\sc ne}. -\s{Pøíklad:} Je dán bipartitní graf $G$, $k \in {\bb N}$. Existuje v $G$ párování, které obsahuje alespoò $k$ hran? +\s{Pøíklad:} Je dán bipartitní graf $G$ a $k \in {\bb N}$. Existuje v $G$ párování, které obsahuje alespoò $k$ hran? \s{Pøíklad:} Daný problém pøevedeme na jiný: Párování $\rightarrow$ hledání maximálního toku (¹ipka znamená \uv{lze pøevést}). -Tzn. existuje v síti $G$ tok velikosti alespoò $k$? +Tzn. existuje v nìjaké síti $G'$ tok velikosti alespoò $k$? -\s{Obecnì se dá øici:} Pokud daný pro problém umíme rozhodnout, zda platí $\Rightarrow$ umíme najít øe¹ení problému. +\s{Obecnì se dá øici:} Pokud daný pro rozhodovací problém umíme rozhodnout, zda platí, pak umíme také najít øe¹ení tohoto problému. Proto¾e jak jinak bychom o daném problému mohli tvrdit, ¾e zaruèenì platí, kdy¾ bychom ho neumìli vyøe¹it. \s{Pøíklad:} Mìjme èernou skøíòku (fungující v polynomiálním èase), která odpoví, zda daný graf má nebo nemá perfektní párování. Odebereme hranu a zeptáme se, jestli i tento nový graf má pefektní párovaní. Kdy¾ má, tak tato hrana nebyla potøebná pro párování, vyhodíme ji, proto¾e ji nepotøebujeme. -Kdy¾ nemá (hrana patøí do párování), tak si danou hranu poznamenáme a odebereme ji i její vrcholy a také hrany, které vedly do tìchto vrcholù. Toto je korektní krok, proto¾e v pùvodním grafu tyto vrcholy byly navzájem spárované, a tedy nemohou být spárované s~¾ádnými jinými vrcholy. -Takto iterujeme, dokud to jde. Výsledkem je mno¾ina hran, které patøí do maximálního párování. Tím jsme dané párování nalezli. +Kdy¾ nemá (hrana patøí do ka¾dého párování), tak si danou hranu poznamenáme a odebereme nejen ji a její vrcholy ale také hrany, které do tìchto vrcholù vedly. Toto je korektní krok, proto¾e v pùvodním grafu tyto vrcholy byly navzájem spárované, a tedy nemohou být spárované s~¾ádnými jinými vrcholy. +Takto iterujeme, dokud to jde. Výsledkem je mno¾ina hran, které patøí do perfektního párování. Tím jsme dané párování nalezli. Hran je polynomiálnì mnoho a skøíòka funguje v polynomiálním èase, tak¾e algoritmus je polynomiální. -\s{Definice:} Jsou-li $A$, $B$ rozhodovací problémy, pak øíkáme, ¾e $A$ lze redukovat na $B$ ($A \rightarrow B$) $\Leftrightarrow$ existuje funkce $f$ spoèitatelná v polynomiálním èase taková, ¾e pro $\forall x: A(x) = B(f(x))$. +\s{Definice:} Jsou-li $A$, $B$ rozhodovací problémy, pak øíkáme, ¾e $A$ lze {\I redukovat} (pøevést) na $B$ (pí¹eme $A \rightarrow B$) $\Leftrightarrow$ existuje funkce $f$ spoèitatelná v polynomiálním èase taková, ¾e pro $\forall x: A(x) = B(f(x))$. -\s{Pøíklad:} Bipartitní graf $\rightarrow$ Tok v síti. -Funkce $f$ je funkce, která vezme bipartitní graf a vyrobí z~nìj regulerní sí» (pøidá zdroj, stok, hrany a ohodnocení). +\s{Pøíklad:} Hledání maximálního párování v bipartitním grafu $\rightarrow$ Hledání maximálního toku v síti. +Funkce $f$ je funkce, která vezme bipartitní graf a vyrobí z~nìj sí» (jak správnì vyrobit sí» pro tento pøíklad viz 3.pøedná¹ka - Dinicùv algoritmus). \s{Nìco málo o slo¾itosti:} -Kdy¾ $A$ lze redukovat na $B$ a $B$ umíme vyøe¹it v èase $\O(\vert $vstup$ \vert^l) = \O(\vert f(x)\vert^l)$ - pro vstup $x: \vert x \vert = n$ -$ \vert f(x)\vert = \O(n^k)$ pro nìjaké $k$, -$A$ poèítá v~èase $\O(n^{kl})$, -$f$ poèítá v polynomiálním èase $\rightarrow$ mù¾e vydat maximálnì polynomiální výstup. +Kdy¾ $A$ lze redukovat na $B$ funkcí $f$ a vstup $A$ je $x$, t¾. $\vert x \vert = n$ a funkce $f$ je spoèitatelná v polynomiálním èase, t¾. $\vert f(x) \vert = \O(n^k)$ pro nìjaké $k$, pak B umíme vyøe¹it v èase $\O(\vert f(x)^l \vert) = \O(n^{kl})$, $f$ poèítá v polynomiálním èase $\rightarrow$ mù¾e vydat maximálnì polynomiální výstup. -\s{Pozorování:} Funkce $f$ je: +$A \rightarrow B$ znamená, ¾e $B$ je alespoò tak tì¾ké jako $A$. + +\s{Pozorování:} Pøevoditelnost je: \itemize\ibull \:reflexivní (úlohu mù¾eme identicky pøevést na tu stejnou), $A \rightarrow A$, \:tranzitivní, $A \rightarrow B$ funkcí $f$, $B \rightarrow C$ funkcí $g$, $A \rightarrow C$ slo¾enou funkcí $(g \circ f)$. \endlist \h{1. problém: SAT} -\>Splnitelnost logických formulí, tj. dosazení $0$ èi $1$ do logické formule tak, aby formule platila. +\>Splnitelnost logických formulí, tj. dosazení $true$ èi $false$ za promìnné v logické formuli tak, aby formule dala výsledek $true$. -\>Zamìøíme se na speciální formu zadání formulí, {\I konjunktivní normální formu} (CNF): +\>Zamìøíme se na speciální formu zadání formulí, {\I konjunktivní normální formu} (CNF). $$(\ldots\lor\ldots\lor\ldots\lor\ldots) \land (\ldots\lor\ldots\lor\ldots\lor\ldots) \land \ldots $$ -\>{\I Vstup:} Formule v konjunktivní normální formì. - -\>{\I Výstup} $\exists$ dosazení $0$ a $1$ za promìnné takové, ¾e hodnota formule $\phi(\ldots) = 1$. +\>{\I Vstup:} Formule $\phi$ v konjunktivní normální formì. -$$ \phi(x, y, \ldots) = (x \lor \lnot y \lor \ldots) \land (\ldots\lor\ldots\lor\ldots\lor\ldots) \land \ldots $$ +\>{\I Výstup} $\exists$ dosazení $true$ a $false$ za promìnné takové, ¾e hodnota formule $\phi(\ldots) = true$. \>Pro formuli platí následující podmínky: \itemize\ibull -\:formule je zadána pomocí klauzulí oddìlených $\land$, -\:ka¾dá klauzule je slo¾ená z literálù oddìlených $\lor$, -\:ka¾dý literál je buïto promìnná nebo její negace. +\:{\I formule} je zadána pomocí {\I klauzulí} oddìlených $\land$, +\:ka¾dá {\I klauzule} je slo¾ená z {\I literálù} oddìlených $\lor$, +\:ka¾dý {\I literál} je buïto promìnná nebo její negace. \endlist \>Uká¾eme, ¾e staèí vyøe¹it jednodu¹¹í problém 3-SAT. \h{2. problém: 3-SAT} -\s{Definice:} 3-SAT je takový SAT, kde ka¾dá klauzule obsahuje nejvý¹e tøi literály. +\s{Definice:} 3-SAT je takový SAT, v nìm¾ ka¾dá klauzule obsahuje nejvý¹e tøi literály. \s{Pøevod 3-SAT na SAT:} -Platí identita, 3-SAT splòuje vlastnosti SATu, proto 3-SAT = SAT (3-SAT je alespoò tak tì¾ký jako SAT) +Vstup není potøeba nijak upravovat, 3-SAT splòuje vlastnosti SATu, proto 3-SAT = SAT (3-SAT je alespoò tak tì¾ký jako SAT) \s {Pøevod SAT na 3-SAT:} Musíme formuli pøevést tak, abychom neporu¹ili splnitelnost. @@ -77,30 +73,32 @@ kde $x$ je nov \:$\alpha \Rightarrow x = 0$ (zajistí splnìní druhé poloviny nové formule), \:$\beta \Rightarrow x = 1$ (zajistí splnìní první poloviny nové formule), \:$\alpha ,\beta / \lnot\alpha ,\lnot\beta \Rightarrow x = 0/1$ (je nám to jedno, celkové øe¹ení nám to neovlivní). - -Hodnota $x$ nám pùvodní formuli nijak neovlivní, proto¾e se v ní nevyskytuje, proto ji mù¾eme nastavit, jak chceme. \endlist \>Tento trik opakujeme tak dlouho, dokud je to tøeba. +Nabízí se otázka, proè mù¾eme promìnnou $x$ nastavit, jak se nám zlíbí. Vysvìtlení je prosté, promìnná $x$ nám pùvodní formuli nijak neovlivní, proto¾e se v ní nevyskytuje, proto ji mù¾eme nastavit tak, jak chceme. + \s{Poznámka:} U~3-SAT lze vynutit právì tøi literály, pro krátké klauzule pou¾ijeme následující trik: -$$(a) \rightarrow (a \lor x) \land (a \lor \lnot x).$$ +$$(\alpha) \rightarrow (\alpha \lor x) \land (\alpha \lor \lnot x).$$ \h{3. problém: Hledání nezávislé mno¾iny v grafu} \>Existuje nezávislá mno¾ina vrcholù z~$G$ velikosti alespoò $k$? -\s{Definice:} {\I Nezávislá mno¾ina} (NzMna) je tvoøena vrcholy grafu, které spolu nemají spoleènou hranu. +\s{Definice:} {\I Nezávislá mno¾ina} (NzMna) je tvoøena vrcholy grafu, které nemají ¾ádnou spoleènou hranu. -\>{\I Vstup:} Neorientovaný graf G, $k \in N$. +\figure{nezmna.eps}{Pøíklad nezávislé mno¾iny.}{3in} -\>{\I Výstup:} $\exists A \subseteq V(G)$, $\vert A \vert \ge k$, $u,v \in A \Rightarrow (uv) \not\in E(G)$? +\>{\I Vstup:} Neorientovaný graf G, $k \in {\bb N}$. -\>Úlohu øe¹íme tak, ¾e problém 3-SAT pøevedeme tuto úlohu. +\>{\I Výstup:} $\exists A \subseteq V(G)$, $\vert A \vert \ge k$: $\forall u,v \in A \Rightarrow uv \not\in E(G)$? -\s{Poznámka:} Ka¾dý graf má minimálnì jednu nezávislou mno¾inu, a tou je prázdná mno¾ina. +\s{Poznámka:} Ka¾dý graf má minimálnì jednu nezávislou mno¾inu, a tou je prázdná mno¾ina. Proto je potøeba zadat i minimální velikost hledané mno¾iny. + +\>Uká¾eme, jak tento probém pøevést na 3-SAT. -\s{Øe¹ení úlohy:} Z ka¾dé klauzule vybereme jeden literál tak, abychom v rùzných klauzulích nevybírali konfliktnì, tj. $x$ a $\lnot x$. +\s{Pøevod:} Z ka¾dé klauzule vybereme jeden literál tak, abychom v rùzných klauzulích nevybírali konfliktnì, tj. $x$ a $\lnot x$. \s{Pøíklad:} $(x \lor y \lor z) \land (x \lor \lnot y \lor \lnot z) \land (\lnot x \lor \lnot y \lor p) $. @@ -109,24 +107,16 @@ $(x \lor y \lor z) \land (x \lor \lnot y \lor \lnot z) \land (\lnot x \lor \lnot Princip je takový, ¾e z~ka¾dé klauzule si vybereme promìnnou, která danou klauzuli splní, a to, aby promìnné, které si vybereme, nekolidovaly, vyøe¹íme hranami mezi promìnnými a jejich negacemi. +\figure{nezmna_graf.eps}{Ukázka pøevodu 3-SAT na nezávislou mno¾inu.}{3in} + Existuje nezávislá mno¾ina velikosti rovné poètu klauzulí? Pokud ano, tak dostaneme seznam promìnných, pomocí kterých splníme danou formuli. -\h{4. problém: Klika} - -\>{\I Vstup:} Graf $G, k \in N$. - -\>{\I Výstup:} $\exists$ úplný podgraf grafu $G$ na $k$ vrcholech? - -\s{Øe¹ení:} Prohodíme hrany a nehrany $\rightarrow$ hledání nezávislé mno¾iny. - -\s{Dùvod:} Pokud existuje úplný graf na $k$ vrcholech, tak v~\uv{invertovaném} grafu tyto vrcholy nejsou spojeny hranou, tj. tvoøí nezávislou mno¾inu. - -\s{Pøíklad:} (Viz obrázky.) - \s{Pøevod NzMna na SAT:} Máme promìnné $v_1, \ldots , v_n$ pro vrcholy. +\>Nyní uká¾eme, jak pøevést problém hledání nezávislé mno¾iny, na SAT. + \itemize\ibull \:Poøídíme si promìnné $v_1, \ldots, v_n$ odpovídající vrcholùm grafu. Promìnná $v_i$ bude indikovat, zda se $i$-tý vrchol vyskytuje v~nezávislé mno¾inì. @@ -144,14 +134,30 @@ M x_{i1} \lor x_{i2} \lor \ldots \lor x_{in}$. \endlist +\figure{matice.eps}{Výsledná matice.}{3in} + +\h{4. problém: Klika} + +\>{\I Vstup:} Graf $G, k \in N$. + +\>{\I Výstup:} $\exists$ úplný podgraf grafu $G$ na $k$ vrcholech? +\figure{klika.eps}{Pøíklad kliky.}{3in} + +\s{Pøevod:} Prohodíme v grafu $G$ hrany a nehrany $\Rightarrow$ hledání nezávislé mno¾iny. + +\s{Dùvod:} Pokud existuje úplný graf na $k$ vrcholech, tak v~\uv{invertovaném} grafu tyto vrcholy nejsou spojeny hranou, tj. tvoøí nezávislou mno¾inu. + +\figure{doplnek_nm.eps}{Prohození hran a nehran.}{3in} \h{5. problém: 3D párování (3D matching)} -\>{\I Vstup:} Tøi mno¾iny, napø. K (kluci), H (holky), Z (zvíøátka) a mno¾ina kompatibilních trojic (tìch, kteøí se spolu snesou). +\>{\I Vstup:} Tøi mno¾iny, napø. $K$ (kluci), $H$ (holky), $Z$ (zvíøátka) a mno¾ina kompatibilních trojic (tìch, kteøí se spolu snesou). + +\>{\I Výstup:} Perfektní podmno¾ina trojic - tj. taková podmno¾ina trojic, která obsahuje v¹echna $K$, $H$ a $Z$. -\>{\I Výstup:} Perfektní podmno¾ina trojic. +\>Uká¾eme, jak tento problém pøevést na 3,3-SAT (ov¹em to a¾ na dal¹í pøedná¹ce). -\s{Øe¹ení:} Pøes 3,3-SAT (konkrétnìji, viz dal¹í pøedná¹ku). +\figure{3d_parovani.eps}{Ukázka 3D párování.}{3in} \h{6. problém: 3,3-SAT} @@ -179,6 +185,9 @@ $$ (x_k \Rightarrow x_1). $$ -Tímto zaruèíme, ¾e v¹echny promìnné budou mít stejnou hodnotu. +Tímto zaruèíme, ¾e v¹echny promìnné budou mít stejnou hodnotu. Navíc si lze v¹imnout, ¾e ka¾dý literál se vyskytuje nejvíce $2x$. + +\s{Závìr:} Obrázek ukazuje problémy, jimi¾ jsme se dnes zabývali, a vztahy mezi tìmito problémy. +\figure{prevody.eps}{Pøevody mezi problémy.}{3in} \bye