From 5ec7d028e66034719a7b6fcc8b3541d998c525e4 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 14 Dec 2011 20:50:35 +0100 Subject: [PATCH] Prevody: Ozivena historie --- {old/11-np => 8-prevody}/3d.eps | 0 {old/11-np => 8-prevody}/3d.svg | 0 {old/10-prevody => 8-prevody}/3d_parovani.eps | 0 {old/10-prevody => 8-prevody}/3d_parovani.svg | 0 .../11-np.tex => 8-prevody/8-prevody.tex | 292 +++++++++++++++++- {old/11-np => 8-prevody}/Makefile | 2 +- {old/11-np => 8-prevody}/and.eps | 0 {old/11-np => 8-prevody}/and.svg | 0 {old/10-prevody => 8-prevody}/doplnek_nm.eps | 0 {old/10-prevody => 8-prevody}/doplnek_nm.svg | 0 {old/11-np => 8-prevody}/klauzule.eps | 0 {old/11-np => 8-prevody}/klauzule.svg | 0 {old/10-prevody => 8-prevody}/klika.eps | 0 {old/10-prevody => 8-prevody}/klika.svg | 0 {old/11-np => 8-prevody}/kobvod.eps | 0 {old/11-np => 8-prevody}/kobvod.svg | 0 {old/10-prevody => 8-prevody}/nezmna.eps | 0 {old/10-prevody => 8-prevody}/nezmna.svg | 0 {old/10-prevody => 8-prevody}/nezmna_graf.eps | 0 {old/10-prevody => 8-prevody}/nezmna_graf.svg | 0 {old/11-np => 8-prevody}/not.eps | 0 {old/11-np => 8-prevody}/not.svg | 0 {old/11-np => 8-prevody}/p-np.eps | 0 {old/11-np => 8-prevody}/p-np.svg | 0 {old/10-prevody => 8-prevody}/prevody.eps | 0 {old/10-prevody => 8-prevody}/prevody.svg | 0 old/10-prevody/10-prevody.tex | 282 ----------------- old/10-prevody/Makefile | 3 - 28 files changed, 287 insertions(+), 292 deletions(-) rename {old/11-np => 8-prevody}/3d.eps (100%) rename {old/11-np => 8-prevody}/3d.svg (100%) rename {old/10-prevody => 8-prevody}/3d_parovani.eps (100%) rename {old/10-prevody => 8-prevody}/3d_parovani.svg (100%) rename old/11-np/11-np.tex => 8-prevody/8-prevody.tex (51%) rename {old/11-np => 8-prevody}/Makefile (64%) rename {old/11-np => 8-prevody}/and.eps (100%) rename {old/11-np => 8-prevody}/and.svg (100%) rename {old/10-prevody => 8-prevody}/doplnek_nm.eps (100%) rename {old/10-prevody => 8-prevody}/doplnek_nm.svg (100%) rename {old/11-np => 8-prevody}/klauzule.eps (100%) rename {old/11-np => 8-prevody}/klauzule.svg (100%) rename {old/10-prevody => 8-prevody}/klika.eps (100%) rename {old/10-prevody => 8-prevody}/klika.svg (100%) rename {old/11-np => 8-prevody}/kobvod.eps (100%) rename {old/11-np => 8-prevody}/kobvod.svg (100%) rename {old/10-prevody => 8-prevody}/nezmna.eps (100%) rename {old/10-prevody => 8-prevody}/nezmna.svg (100%) rename {old/10-prevody => 8-prevody}/nezmna_graf.eps (100%) rename {old/10-prevody => 8-prevody}/nezmna_graf.svg (100%) rename {old/11-np => 8-prevody}/not.eps (100%) rename {old/11-np => 8-prevody}/not.svg (100%) rename {old/11-np => 8-prevody}/p-np.eps (100%) rename {old/11-np => 8-prevody}/p-np.svg (100%) rename {old/10-prevody => 8-prevody}/prevody.eps (100%) rename {old/10-prevody => 8-prevody}/prevody.svg (100%) delete mode 100644 old/10-prevody/10-prevody.tex delete mode 100644 old/10-prevody/Makefile diff --git a/old/11-np/3d.eps b/8-prevody/3d.eps similarity index 100% rename from old/11-np/3d.eps rename to 8-prevody/3d.eps diff --git a/old/11-np/3d.svg b/8-prevody/3d.svg similarity index 100% rename from old/11-np/3d.svg rename to 8-prevody/3d.svg diff --git a/old/10-prevody/3d_parovani.eps b/8-prevody/3d_parovani.eps similarity index 100% rename from old/10-prevody/3d_parovani.eps rename to 8-prevody/3d_parovani.eps diff --git a/old/10-prevody/3d_parovani.svg b/8-prevody/3d_parovani.svg similarity index 100% rename from old/10-prevody/3d_parovani.svg rename to 8-prevody/3d_parovani.svg diff --git a/old/11-np/11-np.tex b/8-prevody/8-prevody.tex similarity index 51% rename from old/11-np/11-np.tex rename to 8-prevody/8-prevody.tex index c81d913..7cb1fcc 100644 --- a/old/11-np/11-np.tex +++ b/8-prevody/8-prevody.tex @@ -1,7 +1,285 @@ \input lecnotes.tex -\prednaska{11}{NP-úplné problémy}{\vbox{\hbox{(zapsali F. Kaèmarik, R. Krivák, D. Remi¹} - \hbox{ Michal Kozák, Vojta Tùma)}}} +\prednaska{8}{Pøevody problémù a NP-úplnost}{} + +\>Na této pøedná¹ce se budeme zabývat rozhodovacími problémy a jejich obtí¾ností. +Za jednoduché budeme trochu zjednodu¹enì pova¾ovat ty problémy, na~nì¾ známe algoritmus +pracující v~polynomiálním èase. + +\s{Definice:} {\I Rozhodovací problém} je takový problém, jeho¾ výstupem je v¾dy {\csc ano}, nebo {\csc ne}. +[Formálnì bychom se na~nìj mohli dívat jako na~mno¾inu $L$ vstupù, na~které je odpovìï {\csc ano}, +a místo $L(x)=\hbox{\csc ano}$ psát prostì $x\in L$.] + +Vstupy mìjme zakódované jen pomocí nul a jednièek (obecnì je jedno, jaký základ pro soustavu +kódování zvolíme, pøevody mezi soustavami o nìjakém základu $\neq$ 1 jsou co do velikosti +zápisu polynomiální). Rozhodovací problém je tedy +$f:\ \{0,1\}^{\ast} \to \{0,1\}$, to jest funkce z mno¾iny v¹ech øetìzcù jednièek a nul +do mno¾iny $\{1,0\}$, kde 1 na výstupu znamená {\csc ano}, 0 {\csc ne}. + +\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? + +To, co bychom ve~vìt¹inì pøípadù chtìli, je samozøejmì nejen zjistit, zda takové párování +existuje, ale také nìjaké konkrétní najít. V¹imnìme si ale, ¾e kdy¾ umíme rozhodovat +existenci párování v~polynomiálním èase, mù¾eme ho polynomiálnì rychle i najít: + +Mìjme èernou skøíòku (fungující v polynomiálním èase), která odpoví, zda daný +graf má nebo nemá párování o~$k$ hranách. Odebereme z~grafu libovolnou hranu +a zeptáme se, jestli i tento nový graf má párovaní velikosti~$k$. Kdy¾ má, pak tato +hrana nebyla pro existenci párování potøebná, a~tak ji odstraníme. Kdy¾ naopak +nemá (hrana patøí do ka¾dého párování po¾adované velikosti), 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. +Na~nový graf aplikujeme znovu tentý¾ postup. Výsledkem je mno¾ina hran, které patøí +do hledaného párování. Hran, a tedy i iterací na¹eho algoritmu, je polynomiálnì +mnoho a skøíòka funguje v polynomiálním èase, tak¾e celý algoritmus je polynomiální. + +A~jak ná¹ rozhodovací problém øe¹it? Nejsnáze tak, ¾e ho pøevedeme +na~{jiný,\footnote{${}^{\dag}$}{vìrni matfyzáckým vtipùm}} který +u¾ vyøe¹it umíme. Tento postup jsme (právì u~hledání párování) u¾ pou¾ili +v~kapitole o~Dinicovì algoritmu. Vytvoøili jsme vhodnou sí», pro kterou +platilo, ¾e v~ní existuje tok velikosti~$k$ právì tehdy, kdy¾ +v~pùvodním grafu existuje párování velikosti~$k$. + +Takovéto pøevody mezi problémy mù¾eme definovat obecnì: + +\s{Definice:} Jsou-li $A$, $B$ rozhodovací problémy, pak øíkáme, ¾e $A$ lze {\I +redukovat} (neboli {\it pøevést}) na $B$ (pí¹eme $A \rightarrow B$) právì tehdy, +kdy¾ existuje funkce $f$ spoèitatelná v polynomiálním èase taková, ¾e pro $\forall +x: A(x) = B(f(x))$. V¹imnìme si, ¾e $f$ pracující v polynomiálním èase vstup +zvìt¹í nejvíce polynomiálnì. + +\s{Pozorování:} $A\rightarrow B$ také znamená, ¾e problém~$B$ je alespoò tak tì¾ký +jako problém~$A$ (tím myslíme, ¾e pokud lze $B$ øe¹it v~polynomiálním èase, +lze tak øe¹it i~$A$): Nech» problém~$B$ umíme øe¹it v~èase $\O(b^k)$, kde +$b$ je délka jeho vstupu. Nech» dále funkce $f$ pøevádìjící $A$ na $B$ pracuje +v~èase $\O(a^\ell)$ pro vstup délky~$a$. Spustíme-li tedy $B(f(x))$ na~nìjaký +vstup~$x$ problému~$A$, bude mít $f(x)$ délku $\O(a^\ell)$, kde $a=|q|$; tak¾e +$B(f(x))$ pobì¾í v~èase $\O(a^\ell + (a^\ell)^k) = \O(a^{k\ell})$, co¾ je +polynomiální v~délce vstupu~$a$. + + +\s{Pozorování:} Pøevoditelnost je +\itemize\ibull +\:reflexivní (úlohu mù¾eme pøevést na tu stejnou identickým zobrazením): $A \rightarrow A$, +\:tranzitivní: Je-li $A \rightarrow B$ funkcí $f$, $B \rightarrow C$ funkcí $g$, +pak $A \rightarrow C$ slo¾enou funkcí $g \circ f$ +(slo¾ení dvou polynomiálních funkcí je zase polynomiální funkce, jak u¾ jsme zpozorovali +v~pøedchozím odstavci). +\endlist +\>Takovýmto relacím øíkáme kvaziuspoøádání -- nesplòují obecnì antisymetrii, tedy mù¾e nastat +$A\rightarrow B$ a $B\rightarrow A$. Omezíme-li se v¹ak na tøídy navzájem pøevoditelných +problémù, dostáváme ji¾ (èásteèné) uspoøádání. Existují i navzájem nepøevoditelné problémy -- +napøíklad problém v¾dy odpovídající 1 a problém v¾dy odpovídající 0. +Nyní se ji¾ podíváme na nìjaké zajímavé problémy. Obecnì to budou problémy, na které +polynomiální algoritmus není znám, a vzájemnými pøevody zjistíme ¾e jsou stejnì tì¾ké. + +\h{1. problém: SAT} +\>Splnitelnost (satisfiability) logických formulí, tj. dosazení 1 èi +0 za promìnné v logické formuli tak, aby formule dala výsledek 1. + +\>Zamìøíme se na speciální formu zadání formulí, {\I konjunktivní normální formu} (CNF), + které splòují následující podmínky: +\itemize\ibull +\:{\I formule} je zadána pomocí {\I klauzulí}\footnote{${}^{\dag}$}{bez politických konotací} 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 +\>Formule mají tedy tvar: +$$\psi = (\ldots\lor\ldots\lor\ldots\lor\ldots) \land (\ldots\lor\ldots\lor\ldots\lor\ldots) \land \ldots $$ + +\>{\I Vstup:} Formule $\psi$ v konjunktivní normální formì. + +\>{\I Výstup:} $\exists$ dosazení 1 a 0 za promìnné takové, ¾e hodnota formule $\psi(\ldots) = 1$. + + + +\>Pøevod nìjaké obecné formule $\psi$ na jí ekvivalentní $\chi$ v~CNF mù¾e +zpùsobit, ¾e $\chi$ je exponenciálnì velká vùèi $\psi$. +Pozdìji uká¾eme, ¾e lze podniknout pøevod na takovou formuli $\chi'$ v~CNF, která sice není +ekvivalentní s $\psi$ (pøibydou nám promìnné, a ne ka¾dý roz¹íøený model +$\psi$ je modelem $\chi'$), ale je splnitelná právì tehdy, kdy¾ je splnitelná $\psi$ -- co¾ nám +pøesnì staèí -- a je lineárnì velká vùèi $\psi$. + +\h{2. problém: 3-SAT} +\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:} +Vstup není potøeba nijak upravovat, 3-SAT splòuje vlastnosti SATu, proto 3-SAT +$\rightarrow$ SAT (SAT je alespoò tak tì¾ký jako 3-SAT) + +\s {Pøevod SAT na 3-SAT:} +Musíme formuli pøevést tak, abychom neporu¹ili splnitelnost. + +\>Trik pro dlouhé klauzule: Ka¾dou \uv{¹patnou} klauzuli +$$(\alpha \lor \beta) \hbox{, t¾. } \vert\alpha\vert + \vert\beta\vert \ge 4 +,\ \vert\alpha\vert \geq 2,\ \vert\beta\vert\geq 2$$ +pøepí¹eme na: $$(\alpha \lor x) \land (\beta \lor \lnot x),$$ +kde $x$ je nová promìnná (pøi ka¾dém dìlení klauzule {\it jiná} +nová promìnná). +%kterou nastavíme tak, abychom neovlivnili splnitelnost formule. + +\>Tento trik opakujeme tak dlouho, dokud je to tøeba -- formuli délky $k+l$ +roztrhneme na formule délky $k+1$ a $l+1$. Pokud klauzule pùlíme, dostaneme +polynomiální èas (strom rekurze má logaritmicky pater -- formule délky alespoò 6 +se nám pøi rozdìlení zmen¹í na dvì instance velikosti maximálnì $2/3$ pùvodní, krat¹í +formule nás netrápí; na ka¾dém patøe se vykoná tolik co na pøedchozím + $2^{hloubka}$ +za pøidané formule). Velikost výsledné formule je tím pádem polynomiální vùèi pùvodní: +v ka¾dém kroku se pøidají jen dva literály, tedy celkem {\it èas na pøevod}$\cdot +2$ nových. + +\>Platí-li: +\itemize\ibull +\:$\alpha \Rightarrow$ zvolíme $x = 0$ (zajistí splnìní druhé poloviny nové formule), +\:$\beta \Rightarrow$ zvolíme $x = 1$ (zajistí splnìní první poloviny nové formule), +\:$\alpha ,\beta / \lnot\alpha ,\lnot\beta \Rightarrow$ zvolíme $x = 0/1$ (je nám to + jedno, celkové øe¹ení nám to neovlivní). +\endlist + +Nabízí se otázka, proè mù¾eme pøidanou promìnnou $x$ nastavovat, 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 stejný trik: +$$(\alpha) \rightarrow (\alpha \vee \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) budeme øíkat ka¾dé mno¾inì vrcholù grafu +takové, ¾e mezi nimi nevede ¾ádná hrana. + +\figure{nezmna.eps}{Pøíklad nezávislé mno¾iny}{1in} + +\>{\I Vstup:} Neorientovaný graf $G$, $k \in {\bb N}$. + +\>{\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. Proto je potøeba zadat i minimální velikost hledané mno¾iny. + +\>Uká¾eme, jak na~tento probém pøevést 3-SAT. + +\s{Pøevod 3-SAT na NzMna:} Z ka¾dé klauzule vybereme jeden literál, jeho¾ nastavením se klauzuli +rozhodneme splnit. Samozøejmì 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) $. + +\>Pro ka¾dou klauzuli sestrojíme graf (trojúhelník) a pøidáme \uv{konfliktní} +hrany, tj. $x$ a $\lnot x$. Poèet vrcholù grafu odpovídá poètu literálù ve formuli, +poèet hran je maximálnì kvadratický a pøevod je tedy polynomiální. + +Existuje-li v grafu nezávislá mno¾ina velikosti $k$, pak z~ka¾dého z~$k$ trojúhelníkù +vybere právì jeden vrchol, a pøitom ¾ádné dva vrcholy nebudou odpovídat literálu a +jeho negaci -- tedy dostaneme ohodnocení promìnných splòujících alespoò $k$ klauzulí. +Na druhou stranu, existuje-li ohodnocení $k$ klauzulí, pak pøímo odpovídá nezávislé +mno¾inì velikosti $k$ (v ka¾dém trojúhelníku zvolíme právì jednu z ohodnocených +promìnných, nemù¾e se stát ¾e zvolíme vrcholy konfliktní hrany). Ptáme-li se tedy +na nezávislou mno¾inu velikosti odpovídající +poètu klauzulí, dostaneme odpovìï {\csc ano} právì tehdy, kdy¾ je formule splnitelná. + +Jsou-li ve formuli i klauzule krat¹í ne¾ 3, mù¾eme je buïto prodlou¾it metodou vý¹e +popsanou; nebo si v grafu necháme dvoj- a jedno-úhelníky, které ¾ádné z na¹ich úvah +vadit nebudou. + +\figure{nezmna_graf.eps}{Ukázka pøevodu 3-SAT na nezávislou mno¾inu}{3in} + +\s{Pøevod NzMna 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ì (tedy pøíslu¹né ohodnocení + promìnných bude vlastnì charakteristická funkce nezávislé mno¾iny). +\:Pro ka¾dou hranu $ij \in E(G)$ pøidáme klauzuli $(\lnot v_i \lor \lnot v_j)$. Tyto klauzule + nám ohlídají, ¾e vybraná mno¾ina je vskutku nezávislá. +\:Je¹tì potøebujeme zkontrolovat, ¾e je mno¾ina dostateènì velká, tak¾e si její prvky + oèíslujeme èísly od~1 do~$k$. Oèíslování popí¹eme maticí promìnných $x_{ij}$, pøièem¾ + $x_{ij}$ bude pravdivá právì tehdy, kdy¾ v~poøadí $i$-tý prvek nezávislé mno¾iny je vrchol~$v_j$ +-- pøidáme tedy klauzule, které nám øeknou, ¾e vybrané do nezávislé mno¾iny jsou právì + ty vrcholy, které jsou touto maticí oèíslované: $\forall i,j$, $x_{ij} \Rightarrow v_j$ + (jen dodejme, ¾e $a\Rightarrow b$ je definované jako $\neg a\vee b$). +\:Je¹tì potøebujeme zajistit, aby byla v~ka¾dém øádku i sloupci nejvý¹e jedna jednièka: + $\forall j,i,i^{'}, i\ne i^{'} : x_{ij} \Rightarrow \lnot x_{i^{'}j}$ a + $\forall i,j,j^{'}, j\ne j^{'} : x_{ij} \Rightarrow \lnot x_{ij^{'}}$. +\:A~nakonec si ohlídáme, aby v~ka¾dém øádku byla alespoò jedna jednièka, klauzulí $\forall i : + x_{i1} \lor x_{i2} \lor \ldots \lor x_{in}$. +\endlist +Tímto vynutíme NzMnu $\geq k$, co¾ jsme pøesnì chtìli. Takovýto pøevod je zøejmì polynomiální. + +\s{Pøíklad matice:} Jako pøíklad pou¾ijeme nezávislou mno¾inu z ukázky nezávislé mno¾iny. +Nech» jsou vrcholy grafu oèíslované zleva a zeshora. Hledáme nezávislou mno¾inu velikosti $2$. +Matice pak bude vypadat následovnì: +$$ \pmatrix{1&0&0&0&0 \cr 0&0&0&1&0}$$ +\s{Vysvìtlení:} Jako první vrchol mno¾iny bude vybrán vrchol $v_1$, proto v prvním +øádku a v prvním sloupci bude $1$. Jako druhý vrchol mno¾iny bude vybrán +vrchol $v_4$, proto na druhém øádku a ve ètvrtém sloupci bude $1$. Na ostatních místech bude $0$. + +\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}{2in} + +\s{Pøevod:} Prohodíme v grafu $G$ hrany a nehrany $\Rightarrow$ (hledání nezávislé mno¾iny $\leftrightarrow$ hledání kliky). + +\s{Dùvod:} Pokud existuje úplný graf na $k$ vrcholech, tak v~komplementárním grafu tyto vrcholy nejsou spojeny hranou, tj. tvoøí nezávislou mno¾inu, + a naopak. + +\figure{doplnek_nm.eps}{Prohození hran a nehran}{2in} + + +\h{5. problém: 3,3-SAT} +\s{Definice:} 3,3-SAT je speciální pøípad 3-SATu, kde ka¾dá promìnná se vyskytuje v~maximálnì tøech literálech. + +\s{Pøevod 3-SAT na 3,3-SAT:} +Pokud se promìnná $x$ vyskytuje v~$k > 3$ literálech, tak nahradíme výskyty novými promìnnými $x_1, \ldots , x_k$ a pøidáme klauzule: +$$ +(\lnot x_1 \lor x_2), +(\lnot x_2 \lor x_3), +(\lnot x_3 \lor x_4), +\ldots, +(\lnot x_{k-1} \lor x_k), +(\lnot x_k \lor x_1), +$$ + +co¾ odpovídá: + +$$ +(x_1 \Rightarrow x_2), +(x_2 \Rightarrow x_3), +(x_3 \Rightarrow x_4), +\ldots, +(x_{k-1} \Rightarrow x_k), +(x_k \Rightarrow x_1). +$$ + +Tímto zaruèíme, ¾e v¹echny nové promìnné budou mít stejnou hodnotu. + +Mimochodem, mù¾eme rovnou zaøídit, ¾e ka¾dý literál se vyskytuje nejvíce dvakrát (tedy ¾e +ka¾dá promìnná se vyskytuje alespoò jednou pozitivnì a alespoò jednou negativnì). Pokud by +se nìjaká promìnná objevila ve~tøech stejných literálech, mù¾eme na~ni +také pou¾ít ná¹ trik a nahradit ji tøemi promìnnými. V~nových klauzulích se pak bude +vyskytovat jak pozitivnì, tak negativnì. + +\h{6. 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 Výstup:} Perfektní podmno¾ina trojic -- tj. taková podmno¾ina trojic, která obsahuje v¹echna $K$, $H$ a $Z$. + +\>Uká¾eme, jak na tento problém pøevést 3,3-SAT (ov¹em to a¾ na dal¹í pøedná¹ce). + +\figure{3d_parovani.eps}{Ukázka 3D párování}{3in} + +\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} + +\h{NP-úplné problémy} Dosud jsme zkoumali problémy, které se nás ptaly na to, jestli nìco existuje. Napøíklad jsme dostali formuli a problém splnitelnosti se nás ptal, zda @@ -292,16 +570,16 @@ topologicky set \s{Lemma:} Obvodový SAT se dá pøevést na 3-SAT. \proof -Budeme postupnì budovat formuli v~konjunktivní normální formì. Ka¾dý booleovský obvod se dá pøevést v~polynomiálním èase na~ekvivalentní obvod, ve~kterém se vyskytují jen hradla {\sc and} a {\sc not}, tak¾e staèí najít klauzule odpovídající tìmto hradlùm. Pro ka¾dé hradlo v~obvodu zavedeme novou promìnnou popisující jeho výstup. Pøidáme klauzule, které nám kontrolují, ¾e toto hradlo máme ohodnocené konzistentnì. +Budeme postupnì budovat formuli v~konjunktivní normální formì. Ka¾dý booleovský obvod se dá pøevést v~polynomiálním èase na~ekvivalentní obvod, ve~kterém se vyskytují jen hradla {\csc and} a {\csc not}, tak¾e staèí najít klauzule odpovídající tìmto hradlùm. Pro ka¾dé hradlo v~obvodu zavedeme novou promìnnou popisující jeho výstup. Pøidáme klauzule, které nám kontrolují, ¾e toto hradlo máme ohodnocené konzistentnì. -\>{\I Pøevod hradla \sc not}: na vstupu hradla budeme mít nìjakou promìnnou $x$ (která pøi¹la buïto pøímo ze~vstupu toho celého obvodu nebo je to promìnná, která vznikla na výstupu nìjakého hradla) a na výstupu promìnnou $y$. Pøidáme klauzule, které nám zaruèí, ¾e jedna promìnná bude negací té druhé: +\>{\I Pøevod hradla \csc not}: na vstupu hradla budeme mít nìjakou promìnnou $x$ (která pøi¹la buïto pøímo ze~vstupu toho celého obvodu nebo je to promìnná, která vznikla na výstupu nìjakého hradla) a na výstupu promìnnou $y$. Pøidáme klauzule, které nám zaruèí, ¾e jedna promìnná bude negací té druhé: $$\matrix{ (x \lor y), \cr (\neg{x} \lor \neg{y}). \cr } \hskip 0.2\hsize \vcenter{\hbox{\epsfxsize=0.7cm\epsfbox{not.eps}}} $$ -\>{\I Pøevod hradla \sc and}: Hradlo má vstupy $x, y$ a~výstup $z$. Potøebujeme pøidat klauzule, které nám popisují, jak se má hradlo {\sc and} chovat. Tyto vztahy pøepí¹eme do~konjunktivní normální formy: +\>{\I Pøevod hradla \csc and}: Hradlo má vstupy $x, y$ a~výstup $z$. Potøebujeme pøidat klauzule, které nám popisují, jak se má hradlo {\csc and} chovat. Tyto vztahy pøepí¹eme do~konjunktivní normální formy: $$ \left. \matrix{ x\ \&\ y \Rightarrow z \cr @@ -320,7 +598,7 @@ $$ \vcenter{\hbox{\epsfxsize=0.7cm\epsfbox{and.eps}}} $$ -\>Kdy¾ chceme pøevádìt obvodový SAT na 3-SAT, obvod nejdøíve pøelo¾íme na takový, ve~kterém jsou jen hradla {\sc and} a~{\sc not}, a~pak hradla tohoto obvodu pøelo¾íme na klauzule. Formule vzniklá z~takovýchto klauzulí je splnitelná pravì tehdy, kdy¾ je splnitelný daný obvod. Pøevod pracuje v polynomiálním èase. +\>Kdy¾ chceme pøevádìt obvodový SAT na 3-SAT, obvod nejdøíve pøelo¾íme na takový, ve~kterém jsou jen hradla {\csc and} a~{\csc not}, a~pak hradla tohoto obvodu pøelo¾íme na klauzule. Formule vzniklá z~takovýchto klauzulí je splnitelná pravì tehdy, kdy¾ je splnitelný daný obvod. Pøevod pracuje v polynomiálním èase. \qed \s{Poznámka:} @@ -332,3 +610,5 @@ je ve~skute \bye + +\bye diff --git a/old/11-np/Makefile b/8-prevody/Makefile similarity index 64% rename from old/11-np/Makefile rename to 8-prevody/Makefile index e5d9652..117196c 100644 --- a/old/11-np/Makefile +++ b/8-prevody/Makefile @@ -1,3 +1,3 @@ -P=11-np +P=8-prevody include ../Makerules diff --git a/old/11-np/and.eps b/8-prevody/and.eps similarity index 100% rename from old/11-np/and.eps rename to 8-prevody/and.eps diff --git a/old/11-np/and.svg b/8-prevody/and.svg similarity index 100% rename from old/11-np/and.svg rename to 8-prevody/and.svg diff --git a/old/10-prevody/doplnek_nm.eps b/8-prevody/doplnek_nm.eps similarity index 100% rename from old/10-prevody/doplnek_nm.eps rename to 8-prevody/doplnek_nm.eps diff --git a/old/10-prevody/doplnek_nm.svg b/8-prevody/doplnek_nm.svg similarity index 100% rename from old/10-prevody/doplnek_nm.svg rename to 8-prevody/doplnek_nm.svg diff --git a/old/11-np/klauzule.eps b/8-prevody/klauzule.eps similarity index 100% rename from old/11-np/klauzule.eps rename to 8-prevody/klauzule.eps diff --git a/old/11-np/klauzule.svg b/8-prevody/klauzule.svg similarity index 100% rename from old/11-np/klauzule.svg rename to 8-prevody/klauzule.svg diff --git a/old/10-prevody/klika.eps b/8-prevody/klika.eps similarity index 100% rename from old/10-prevody/klika.eps rename to 8-prevody/klika.eps diff --git a/old/10-prevody/klika.svg b/8-prevody/klika.svg similarity index 100% rename from old/10-prevody/klika.svg rename to 8-prevody/klika.svg diff --git a/old/11-np/kobvod.eps b/8-prevody/kobvod.eps similarity index 100% rename from old/11-np/kobvod.eps rename to 8-prevody/kobvod.eps diff --git a/old/11-np/kobvod.svg b/8-prevody/kobvod.svg similarity index 100% rename from old/11-np/kobvod.svg rename to 8-prevody/kobvod.svg diff --git a/old/10-prevody/nezmna.eps b/8-prevody/nezmna.eps similarity index 100% rename from old/10-prevody/nezmna.eps rename to 8-prevody/nezmna.eps diff --git a/old/10-prevody/nezmna.svg b/8-prevody/nezmna.svg similarity index 100% rename from old/10-prevody/nezmna.svg rename to 8-prevody/nezmna.svg diff --git a/old/10-prevody/nezmna_graf.eps b/8-prevody/nezmna_graf.eps similarity index 100% rename from old/10-prevody/nezmna_graf.eps rename to 8-prevody/nezmna_graf.eps diff --git a/old/10-prevody/nezmna_graf.svg b/8-prevody/nezmna_graf.svg similarity index 100% rename from old/10-prevody/nezmna_graf.svg rename to 8-prevody/nezmna_graf.svg diff --git a/old/11-np/not.eps b/8-prevody/not.eps similarity index 100% rename from old/11-np/not.eps rename to 8-prevody/not.eps diff --git a/old/11-np/not.svg b/8-prevody/not.svg similarity index 100% rename from old/11-np/not.svg rename to 8-prevody/not.svg diff --git a/old/11-np/p-np.eps b/8-prevody/p-np.eps similarity index 100% rename from old/11-np/p-np.eps rename to 8-prevody/p-np.eps diff --git a/old/11-np/p-np.svg b/8-prevody/p-np.svg similarity index 100% rename from old/11-np/p-np.svg rename to 8-prevody/p-np.svg diff --git a/old/10-prevody/prevody.eps b/8-prevody/prevody.eps similarity index 100% rename from old/10-prevody/prevody.eps rename to 8-prevody/prevody.eps diff --git a/old/10-prevody/prevody.svg b/8-prevody/prevody.svg similarity index 100% rename from old/10-prevody/prevody.svg rename to 8-prevody/prevody.svg diff --git a/old/10-prevody/10-prevody.tex b/old/10-prevody/10-prevody.tex deleted file mode 100644 index 070d102..0000000 --- a/old/10-prevody/10-prevody.tex +++ /dev/null @@ -1,282 +0,0 @@ -\input lecnotes.tex - -\prednaska{10}{Pøevody problémù}{\vbox{\hbox{(zapsali Martin Chytil, Vladimír Kudelas,}\hbox{ Michal Kozák, Vojta Tùma)}}} - -\>Na této pøedná¹ce se budeme zabývat rozhodovacími problémy a jejich obtí¾ností. -Za jednoduché budeme trochu zjednodu¹enì pova¾ovat ty problémy, na~nì¾ známe algoritmus -pracující v~polynomiálním èase. - -\s{Definice:} {\I Rozhodovací problém} je takový problém, jeho¾ výstupem je v¾dy {\sc ano}, nebo {\sc ne}. -[Formálnì bychom se na~nìj mohli dívat jako na~mno¾inu $L$ vstupù, na~které je odpovìï {\sc ano}, -a místo $L(x)=\hbox{\sc ano}$ psát prostì $x\in L$.] - -Vstupy mìjme zakódované jen pomocí nul a jednièek (obecnì je jedno, jaký základ pro soustavu -kódování zvolíme, pøevody mezi soustavami o nìjakém základu $\neq$ 1 jsou co do velikosti -zápisu polynomiální). Rozhodovací problém je tedy -$f:\ \{0,1\}^{\ast} \to \{0,1\}$, to jest funkce z mno¾iny v¹ech øetìzcù jednièek a nul -do mno¾iny $\{1,0\}$, kde 1 na výstupu znamená {\sc ano}, 0 {\sc ne}. - -\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? - -To, co bychom ve~vìt¹inì pøípadù chtìli, je samozøejmì nejen zjistit, zda takové párování -existuje, ale také nìjaké konkrétní najít. V¹imnìme si ale, ¾e kdy¾ umíme rozhodovat -existenci párování v~polynomiálním èase, mù¾eme ho polynomiálnì rychle i najít: - -Mìjme èernou skøíòku (fungující v polynomiálním èase), která odpoví, zda daný -graf má nebo nemá párování o~$k$ hranách. Odebereme z~grafu libovolnou hranu -a zeptáme se, jestli i tento nový graf má párovaní velikosti~$k$. Kdy¾ má, pak tato -hrana nebyla pro existenci párování potøebná, a~tak ji odstraníme. Kdy¾ naopak -nemá (hrana patøí do ka¾dého párování po¾adované velikosti), 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. -Na~nový graf aplikujeme znovu tentý¾ postup. Výsledkem je mno¾ina hran, které patøí -do hledaného párování. Hran, a tedy i iterací na¹eho algoritmu, je polynomiálnì -mnoho a skøíòka funguje v polynomiálním èase, tak¾e celý algoritmus je polynomiální. - -A~jak ná¹ rozhodovací problém øe¹it? Nejsnáze tak, ¾e ho pøevedeme -na~{jiný,\footnote{${}^{\dag}$}{vìrni matfyzáckým vtipùm}} který -u¾ vyøe¹it umíme. Tento postup jsme (právì u~hledání párování) u¾ pou¾ili -v~kapitole o~Dinicovì algoritmu. Vytvoøili jsme vhodnou sí», pro kterou -platilo, ¾e v~ní existuje tok velikosti~$k$ právì tehdy, kdy¾ -v~pùvodním grafu existuje párování velikosti~$k$. - -Takovéto pøevody mezi problémy mù¾eme definovat obecnì: - -\s{Definice:} Jsou-li $A$, $B$ rozhodovací problémy, pak øíkáme, ¾e $A$ lze {\I -redukovat} (neboli {\it pøevést}) na $B$ (pí¹eme $A \rightarrow B$) právì tehdy, -kdy¾ existuje funkce $f$ spoèitatelná v polynomiálním èase taková, ¾e pro $\forall -x: A(x) = B(f(x))$. V¹imnìme si, ¾e $f$ pracující v polynomiálním èase vstup -zvìt¹í nejvíce polynomiálnì. - -\s{Pozorování:} $A\rightarrow B$ také znamená, ¾e problém~$B$ je alespoò tak tì¾ký -jako problém~$A$ (tím myslíme, ¾e pokud lze $B$ øe¹it v~polynomiálním èase, -lze tak øe¹it i~$A$): Nech» problém~$B$ umíme øe¹it v~èase $\O(b^k)$, kde -$b$ je délka jeho vstupu. Nech» dále funkce $f$ pøevádìjící $A$ na $B$ pracuje -v~èase $\O(a^\ell)$ pro vstup délky~$a$. Spustíme-li tedy $B(f(x))$ na~nìjaký -vstup~$x$ problému~$A$, bude mít $f(x)$ délku $\O(a^\ell)$, kde $a=|q|$; tak¾e -$B(f(x))$ pobì¾í v~èase $\O(a^\ell + (a^\ell)^k) = \O(a^{k\ell})$, co¾ je -polynomiální v~délce vstupu~$a$. - - -\s{Pozorování:} Pøevoditelnost je -\itemize\ibull -\:reflexivní (úlohu mù¾eme pøevést na tu stejnou identickým zobrazením): $A \rightarrow A$, -\:tranzitivní: Je-li $A \rightarrow B$ funkcí $f$, $B \rightarrow C$ funkcí $g$, -pak $A \rightarrow C$ slo¾enou funkcí $g \circ f$ -(slo¾ení dvou polynomiálních funkcí je zase polynomiální funkce, jak u¾ jsme zpozorovali -v~pøedchozím odstavci). -\endlist -\>Takovýmto relacím øíkáme kvaziuspoøádání -- nesplòují obecnì antisymetrii, tedy mù¾e nastat -$A\rightarrow B$ a $B\rightarrow A$. Omezíme-li se v¹ak na tøídy navzájem pøevoditelných -problémù, dostáváme ji¾ (èásteèné) uspoøádání. Existují i navzájem nepøevoditelné problémy -- -napøíklad problém v¾dy odpovídající 1 a problém v¾dy odpovídající 0. -Nyní se ji¾ podíváme na nìjaké zajímavé problémy. Obecnì to budou problémy, na které -polynomiální algoritmus není znám, a vzájemnými pøevody zjistíme ¾e jsou stejnì tì¾ké. - -\h{1. problém: SAT} -\>Splnitelnost (satisfiability) logických formulí, tj. dosazení 1 èi -0 za promìnné v logické formuli tak, aby formule dala výsledek 1. - -\>Zamìøíme se na speciální formu zadání formulí, {\I konjunktivní normální formu} (CNF), - které splòují následující podmínky: -\itemize\ibull -\:{\I formule} je zadána pomocí {\I klauzulí}\footnote{${}^{\dag}$}{bez politických konotací} 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 -\>Formule mají tedy tvar: -$$\psi = (\ldots\lor\ldots\lor\ldots\lor\ldots) \land (\ldots\lor\ldots\lor\ldots\lor\ldots) \land \ldots $$ - -\>{\I Vstup:} Formule $\psi$ v konjunktivní normální formì. - -\>{\I Výstup:} $\exists$ dosazení 1 a 0 za promìnné takové, ¾e hodnota formule $\psi(\ldots) = 1$. - - - -\>Pøevod nìjaké obecné formule $\psi$ na jí ekvivalentní $\chi$ v~CNF mù¾e -zpùsobit, ¾e $\chi$ je exponenciálnì velká vùèi $\psi$. -Pozdìji uká¾eme, ¾e lze podniknout pøevod na takovou formuli $\chi'$ v~CNF, která sice není -ekvivalentní s $\psi$ (pøibydou nám promìnné, a ne ka¾dý roz¹íøený model -$\psi$ je modelem $\chi'$), ale je splnitelná právì tehdy, kdy¾ je splnitelná $\psi$ -- co¾ nám -pøesnì staèí -- a je lineárnì velká vùèi $\psi$. - -\h{2. problém: 3-SAT} -\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:} -Vstup není potøeba nijak upravovat, 3-SAT splòuje vlastnosti SATu, proto 3-SAT -$\rightarrow$ SAT (SAT je alespoò tak tì¾ký jako 3-SAT) - -\s {Pøevod SAT na 3-SAT:} -Musíme formuli pøevést tak, abychom neporu¹ili splnitelnost. - -\>Trik pro dlouhé klauzule: Ka¾dou \uv{¹patnou} klauzuli -$$(\alpha \lor \beta) \hbox{, t¾. } \vert\alpha\vert + \vert\beta\vert \ge 4 -,\ \vert\alpha\vert \geq 2,\ \vert\beta\vert\geq 2$$ -pøepí¹eme na: $$(\alpha \lor x) \land (\beta \lor \lnot x),$$ -kde $x$ je nová promìnná (pøi ka¾dém dìlení klauzule {\it jiná} -nová promìnná). -%kterou nastavíme tak, abychom neovlivnili splnitelnost formule. - -\>Tento trik opakujeme tak dlouho, dokud je to tøeba -- formuli délky $k+l$ -roztrhneme na formule délky $k+1$ a $l+1$. Pokud klauzule pùlíme, dostaneme -polynomiální èas (strom rekurze má logaritmicky pater -- formule délky alespoò 6 -se nám pøi rozdìlení zmen¹í na dvì instance velikosti maximálnì $2/3$ pùvodní, krat¹í -formule nás netrápí; na ka¾dém patøe se vykoná tolik co na pøedchozím + $2^{hloubka}$ -za pøidané formule). Velikost výsledné formule je tím pádem polynomiální vùèi pùvodní: -v ka¾dém kroku se pøidají jen dva literály, tedy celkem {\it èas na pøevod}$\cdot -2$ nových. - -\>Platí-li: -\itemize\ibull -\:$\alpha \Rightarrow$ zvolíme $x = 0$ (zajistí splnìní druhé poloviny nové formule), -\:$\beta \Rightarrow$ zvolíme $x = 1$ (zajistí splnìní první poloviny nové formule), -\:$\alpha ,\beta / \lnot\alpha ,\lnot\beta \Rightarrow$ zvolíme $x = 0/1$ (je nám to - jedno, celkové øe¹ení nám to neovlivní). -\endlist - -Nabízí se otázka, proè mù¾eme pøidanou promìnnou $x$ nastavovat, 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 stejný trik: -$$(\alpha) \rightarrow (\alpha \vee \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) budeme øíkat ka¾dé mno¾inì vrcholù grafu -takové, ¾e mezi nimi nevede ¾ádná hrana. - -\figure{nezmna.eps}{Pøíklad nezávislé mno¾iny}{1in} - -\>{\I Vstup:} Neorientovaný graf $G$, $k \in {\bb N}$. - -\>{\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. Proto je potøeba zadat i minimální velikost hledané mno¾iny. - -\>Uká¾eme, jak na~tento probém pøevést 3-SAT. - -\s{Pøevod 3-SAT na NzMna:} Z ka¾dé klauzule vybereme jeden literál, jeho¾ nastavením se klauzuli -rozhodneme splnit. Samozøejmì 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) $. - -\>Pro ka¾dou klauzuli sestrojíme graf (trojúhelník) a pøidáme \uv{konfliktní} -hrany, tj. $x$ a $\lnot x$. Poèet vrcholù grafu odpovídá poètu literálù ve formuli, -poèet hran je maximálnì kvadratický a pøevod je tedy polynomiální. - -Existuje-li v grafu nezávislá mno¾ina velikosti $k$, pak z~ka¾dého z~$k$ trojúhelníkù -vybere právì jeden vrchol, a pøitom ¾ádné dva vrcholy nebudou odpovídat literálu a -jeho negaci -- tedy dostaneme ohodnocení promìnných splòujících alespoò $k$ klauzulí. -Na druhou stranu, existuje-li ohodnocení $k$ klauzulí, pak pøímo odpovídá nezávislé -mno¾inì velikosti $k$ (v ka¾dém trojúhelníku zvolíme právì jednu z ohodnocených -promìnných, nemù¾e se stát ¾e zvolíme vrcholy konfliktní hrany). Ptáme-li se tedy -na nezávislou mno¾inu velikosti odpovídající -poètu klauzulí, dostaneme odpovìï {\sc ano} právì tehdy, kdy¾ je formule splnitelná. - -Jsou-li ve formuli i klauzule krat¹í ne¾ 3, mù¾eme je buïto prodlou¾it metodou vý¹e -popsanou; nebo si v grafu necháme dvoj- a jedno-úhelníky, které ¾ádné z na¹ich úvah -vadit nebudou. - -\figure{nezmna_graf.eps}{Ukázka pøevodu 3-SAT na nezávislou mno¾inu}{3in} - -\s{Pøevod NzMna 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ì (tedy pøíslu¹né ohodnocení - promìnných bude vlastnì charakteristická funkce nezávislé mno¾iny). -\:Pro ka¾dou hranu $ij \in E(G)$ pøidáme klauzuli $(\lnot v_i \lor \lnot v_j)$. Tyto klauzule - nám ohlídají, ¾e vybraná mno¾ina je vskutku nezávislá. -\:Je¹tì potøebujeme zkontrolovat, ¾e je mno¾ina dostateènì velká, tak¾e si její prvky - oèíslujeme èísly od~1 do~$k$. Oèíslování popí¹eme maticí promìnných $x_{ij}$, pøièem¾ - $x_{ij}$ bude pravdivá právì tehdy, kdy¾ v~poøadí $i$-tý prvek nezávislé mno¾iny je vrchol~$v_j$ --- pøidáme tedy klauzule, které nám øeknou, ¾e vybrané do nezávislé mno¾iny jsou právì - ty vrcholy, které jsou touto maticí oèíslované: $\forall i,j$, $x_{ij} \Rightarrow v_j$ - (jen dodejme, ¾e $a\Rightarrow b$ je definované jako $\neg a\vee b$). -\:Je¹tì potøebujeme zajistit, aby byla v~ka¾dém øádku i sloupci nejvý¹e jedna jednièka: - $\forall j,i,i^{'}, i\ne i^{'} : x_{ij} \Rightarrow \lnot x_{i^{'}j}$ a - $\forall i,j,j^{'}, j\ne j^{'} : x_{ij} \Rightarrow \lnot x_{ij^{'}}$. -\:A~nakonec si ohlídáme, aby v~ka¾dém øádku byla alespoò jedna jednièka, klauzulí $\forall i : - x_{i1} \lor x_{i2} \lor \ldots \lor x_{in}$. -\endlist -Tímto vynutíme NzMnu $\geq k$, co¾ jsme pøesnì chtìli. Takovýto pøevod je zøejmì polynomiální. - -\s{Pøíklad matice:} Jako pøíklad pou¾ijeme nezávislou mno¾inu z ukázky nezávislé mno¾iny. -Nech» jsou vrcholy grafu oèíslované zleva a zeshora. Hledáme nezávislou mno¾inu velikosti $2$. -Matice pak bude vypadat následovnì: -$$ \pmatrix{1&0&0&0&0 \cr 0&0&0&1&0}$$ -\s{Vysvìtlení:} Jako první vrchol mno¾iny bude vybrán vrchol $v_1$, proto v prvním -øádku a v prvním sloupci bude $1$. Jako druhý vrchol mno¾iny bude vybrán -vrchol $v_4$, proto na druhém øádku a ve ètvrtém sloupci bude $1$. Na ostatních místech bude $0$. - -\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}{2in} - -\s{Pøevod:} Prohodíme v grafu $G$ hrany a nehrany $\Rightarrow$ (hledání nezávislé mno¾iny $\leftrightarrow$ hledání kliky). - -\s{Dùvod:} Pokud existuje úplný graf na $k$ vrcholech, tak v~komplementárním grafu tyto vrcholy nejsou spojeny hranou, tj. tvoøí nezávislou mno¾inu, - a naopak. - -\figure{doplnek_nm.eps}{Prohození hran a nehran}{2in} - - -\h{5. problém: 3,3-SAT} -\s{Definice:} 3,3-SAT je speciální pøípad 3-SATu, kde ka¾dá promìnná se vyskytuje v~maximálnì tøech literálech. - -\s{Pøevod 3-SAT na 3,3-SAT:} -Pokud se promìnná $x$ vyskytuje v~$k > 3$ literálech, tak nahradíme výskyty novými promìnnými $x_1, \ldots , x_k$ a pøidáme klauzule: -$$ -(\lnot x_1 \lor x_2), -(\lnot x_2 \lor x_3), -(\lnot x_3 \lor x_4), -\ldots, -(\lnot x_{k-1} \lor x_k), -(\lnot x_k \lor x_1), -$$ - -co¾ odpovídá: - -$$ -(x_1 \Rightarrow x_2), -(x_2 \Rightarrow x_3), -(x_3 \Rightarrow x_4), -\ldots, -(x_{k-1} \Rightarrow x_k), -(x_k \Rightarrow x_1). -$$ - -Tímto zaruèíme, ¾e v¹echny nové promìnné budou mít stejnou hodnotu. - -Mimochodem, mù¾eme rovnou zaøídit, ¾e ka¾dý literál se vyskytuje nejvíce dvakrát (tedy ¾e -ka¾dá promìnná se vyskytuje alespoò jednou pozitivnì a alespoò jednou negativnì). Pokud by -se nìjaká promìnná objevila ve~tøech stejných literálech, mù¾eme na~ni -také pou¾ít ná¹ trik a nahradit ji tøemi promìnnými. V~nových klauzulích se pak bude -vyskytovat jak pozitivnì, tak negativnì. - -\h{6. 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 Výstup:} Perfektní podmno¾ina trojic -- tj. taková podmno¾ina trojic, která obsahuje v¹echna $K$, $H$ a $Z$. - -\>Uká¾eme, jak na tento problém pøevést 3,3-SAT (ov¹em to a¾ na dal¹í pøedná¹ce). - -\figure{3d_parovani.eps}{Ukázka 3D párování}{3in} - -\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 diff --git a/old/10-prevody/Makefile b/old/10-prevody/Makefile deleted file mode 100644 index 04b5d58..0000000 --- a/old/10-prevody/Makefile +++ /dev/null @@ -1,3 +0,0 @@ -P=10-prevody - -include ../Makerules -- 2.39.5