Test Arka: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Arek (dyskusja | edycje)
687 edycji
Nie podano opisu zmian
m Zastępowanie tekstu – „\displaystyle ” na „”
 
(Nie pokazano 44 wersji utworzonych przez 4 użytkowników)
Linia 1: Linia 1:
<math>M</math> <math>M'</math> <math>M' </math>
<quiz type="exclusive">
<math>a^{\sum_{i=1}^{10}i}</math>
When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).
<rightoption>True</rightoption>
<wrongoption>False</wrongoption>
</quiz>
==Testy==


{{cwiczenie|[Uzupelnij]||
<quiz type="exclusive">
abc
When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).
}}
<rightoption>True</rightoption>
<wrongoption>False</wrongoption>
</quiz>


<hr>
<quiz>
When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).
<rightoption>True</rightoption>
<wrongoption>False</wrongoption>
</quiz>


{article}
<quiz type="exclusive">
In C++, 14 % 4 =
<option reply="Za mało">1</option>
<option>2</option>
<option reply="Za dużo">3</option>
<wrongoption reply="O wiele za dużo">4</wrongoption>
</quiz>
<quiz>
In C++, 14 % 4 =
<option reply="Za mało">1</option>
<option>2</option>
<option reply="Za dużo">3</option>
<wrongoption reply="O wiele za dużo">4</wrongoption>
</quiz>


{}{0.5cm} {}{0.8cm} {}{ -0.4cm} {}{ -0.4cm} {}{1mm}
<quiz>
Variables that are declared, but not initialized, contain
<wrongoption>blank spaces</wrongoption>
<rightoption reply="Tak, pod warunkiem, że są globalne">zeros</rightoption>
<rightoption reply="Jeśli nie są globalne">"garbage" values</rightoption>
<wrongoption reply="Dostajesz pałę!">nothing - they are empty</wrongoption>
</quiz>


{theorem}{Twierdzenie}[section]
<quiz type="exclusive">
{lemma}[theorem]{Lemat}
Variables that are declared, but not initialized, contain
{definition}[theorem]{Definicja}
<wrongoption>blank spaces</wrongoption>
{example}{Przykład}[section]
<rightoption reply="Tak, pod warunkiem, że są globalne">zeros</rightoption>
{excercise}{Ćwiczenie}[section]
<rightoption reply="Jeśli nie są globalne">"garbage" values</rightoption>
{remark}{Uwaga}[section]
<wrongoption reply="Dostajesz pałę!">nothing - they are empty</wrongoption>
</quiz>


{proof}{ ''Dowód: ''}{ <math>\square</math>}
{hint}{ ''Wskazówka: ''}{}
{solution}{ ''Rozwiązanie: ''}{}


Złożoność obliczeniowa
<div style="background-color: #bbbbbb; padding: 2em; border: 1px solid black">
Dlaczego suma <math>\sum_{i=1}^{10}i</math> jest źle wyświetlana w wykładniku potęgi?


Moduł 5
<math>z^{\sum_{i=1}^{10}i}</math>


Problemy NP-zupełne


==Wstęp==
</div>


Jak czytelnikowi wiadomo, w aktualnym stanie wiedzy NP-zupełność
jest podstawowym narzędziem do badania probelu algorytmicznego pod
kątem jego trudności obliczeniowej. Na tym wykładzie dla wielu
znanych klasycznych problemów z teorii grafów, kombinatoryki, logiki
i innych podajemy definicje ich decyzyjnych wersji i wykazujemy ich
NP-zupełność. Z problematyką ta spotkaliśmy się już na kursie ''Algorytmy i struktury danych''. Tutaj rozbudowujemy te wiadomości,
czynimy je bardziej formalnymi posługując się modelem maszyny
Turinga i redukcją logarytmiczną. Na przedstawionych przykładach
omawiamy również techniki dowodzenia NP-zupełności. Następny wykład
pokazuje wykorzystanie tych technik do analizy złożoności problemu i
jego zawężeń.


==O problemie SAT==
<div id="content">
<div id="navcontainer">
<ul id="navlist">
<div><a href="index.xml" class="withChild">Start</a></div>


Aby wykazać, że dany problem <math>Q</math> z klasy NP jest NP-zupełny, zgodnie
<div id="active" class="withoutChild">Zadanie 1.</div>
z własnościami redukcji logarytmicznej (przechodniość) wystarcza
<div><a href="zadanie_2.xml" class="withoutChild">Zadanie 2.</a></div>
pokazać, dla dowolnego problemu <math>Q' \in NPC</math>, że <math>Q'</math> redukuje się
<div><a href="zadanie_3.xml" class="withoutChild">Zadanie 3.</a></div>
do <math>Q</math>. Innymi słowy, proces dowodzenia że dany problem <math>Q</math> jest w
<div><a href="zadanie_4.xml" class="withoutChild">Zadanie 4.</a></div>
NPC składa sie z nastepujących kroków:
<div><a href="zadanie_5.xml" class="withoutChild">Zadanie 5.</a></div>
<div><a href="zadanie_6.xml" class="withoutChild">Zadanie 6.</a></div>


* dowieść że <math>Q</math> należy do NP
</ul>
</div>
<div id="main">
<div id="nodeDecoration">
<p id="nodeTitle">Zadanie 1.</p>
</div>
<script type="text/javascript" src="common.js"></script> <script
type="text/javascript" src="libot_drag.js"></script>
<div class="iDevice emphasis1"><img alt="Ikona obiektu Pytanie"
class="iDevice_icon" src="icon_question.gif" /> <span
class="iDeviceTitle">Zadanie 1,</span><br />
<div class="iDevice_inner">
Liczba <math><msqrt><mrow><mn>3</mn>


* wybrać znany problem NP-zupełny <math>Q'</math> i skonstruować redukcję z <math>Q'</math>
<mo class="MathClass-bin">+</mo> <mn>2</mn><msqrt><mrow>
do <math>Q</math>.
<mn>2</mn></mrow></msqrt></mrow></msqrt> <mo class="MathClass-bin">&minus;</mo><msqrt><mrow><mn>3</mn>
<mo class="MathClass-bin">&minus;</mo> <mn>2</mn><msqrt><mrow>
<mn>2</mn></mrow></msqrt></mrow></msqrt></math> &nbsp;&nbsp;
<table>
<tbody>


Przypomnijemy, że redukcja z problemu A do B dowodzi, że B jest
<tr>
niełatwiejszy niż A. Zatem dla konstrukcji takiej redukcji łatwiej
<td><input type="checkbox" name="option9" id="ia0b9"
jest, gdy (są to rozważania czysto intuicyjne):
value="vTrue"
onclick="document.getElementById('sa0b9').style.display = this.checked ? 'block' : 'none';" /></td>
<td>jest dodatnia</td>
<td>
<div id="sa0b9" style="color: rgb(0, 51, 204);display: none;">Poprawnie</div>
</td>
</tr>
<tr>


* problem A nie jest skomplikowany, tzn. instancje tego problemu
<td><input type="checkbox" name="option9" id="ia1b9"
wykazują pewną regularność, łatwą do "opisu" lub "zmierzenia"
value="vTrue"
onclick="document.getElementById('sa1b9').style.display = this.checked ? 'block' : 'none';" /></td>
<td>jest wymierna</td>
<td>
<div id="sa1b9" style="color: rgb(0, 51, 204);display: none;">Poprawnie</div>
</td>
</tr>
<tr>
<td><input type="checkbox" name="option9" id="ia2b9"
value="vFalse"
onclick="document.getElementById('sa2b9').style.display = this.checked ? 'block' : 'none';" /></td>


* problem B dopuszcza konstrukcje różnorodnych instancji, jest "bogaty
<td>nale&raquo;y do tr&oacute;jkowego zbioru Cantora.</td>
strukturalnie"
<td>
<div id="sa2b9" style="color: rgb(0, 51, 204);display: none;">Źle</div>
</td>
</tr>
</tbody>
</table>


Stąd dla wypracowania sobie "warsztatu" dla konstruowania dowodów
</div>
NP-zupełności warto rozpocząć od dowiedzenia tej własności dla kilku
</div>
nieskomplikowanych (pod wzgledem opisu struktury) problemów. W
<div class="noprt" align="right"><a href="index.xml">&laquo;
rzeczywistości, w literaturze dotyczącej tych zagadnień, można
previous</a> | <a href="zadanie_2.xml">next &raquo;</a></div>
wyodrębnić niewielką grupę klasycznych w tym sensie problemów, które
</div>
najczęściej wystepują jako lewa strona redukcji w dowodach
</div>
NP-zupełnosci. Poniżej definiujemy lub przypominamy grupe takich
problemów, dość różnorodnego pochodzenia i zastosowania, i dowodzimy
ich NP-zupełności.
 
===Najpierw 3SAT===
 
Zaczynamy od sytuacji, w której jedynym znanym problemem NP-zupełnym
(a więc możliwą lewą stroną redukcji) jest problem SAT. Jest on dość
niewygodny jako problem źródłowy, redukcja z SAT do innego problemu
na ogół wymaga skomplikowanego opisu. Okazuje się (wykazał to już
Cook w swojej fundamentalnej pracy o NP-zupełności), że podproblem
problemu SAT, w którym wymagamy aby każda klauzula zawierała nie
więcej niz 3 literały jest sam w sobie NP-zupełny, a dowód tego
faktu jest dość łatwy.
 
{{twierdzenie|[Uzupelnij]||
Problem 3SAT jest NP-zupełny.
}}
 
{{dowod|[Uzupelnij]||
Problem 3SAT, jako podproblem problemu w klasie NP, sam należy do
NP, zatem pierwsza część dowodu jest za nami.
 
Konstruujemy redukcję z problemu SAT do 3SAT. Na wejściu mamy
formułe <math>\phi = C_1 \wedge \ldots \wedge C_m</math> nad zmiennymi
<math>x_1,\ldots,x_n</math>. Każdą z klauzul <math>C_j</math> przekształcamy osobno. Bez
straty ogólności załóżmy, że <math>C_j = x_1\vee\ldots\vee x_k</math>, gdzie
<math>x_i, i=1,\ldots,k</math> są parami różne. Jeśli <math>k\leq 3</math> to kładziemy
<math>D_j = C_j</math>.
 
Niech <math>k>3</math>. Dodajemy <math>k-3</math> nowych zmiennych <math>y_2, \ldots, y_{k-2}</math>,
i zastepujemy <math>C_j</math> przez
 
<center><math>
D_j = (x_1\vee x_2\vee y_2)\wedge(\neg y_2\vee x_3\vee y_3)
\wedge(\neg y_3\vee x_4\vee y_4) \wedge \ldots
\wedge (\neg y_{k-2}\vee x_{k-1}\vee x_k)</math></center>
 
Nietrudno spostrzec, że jeśli <math>C_j</math> jest spełniona przez pewne
wartościowanie zmiennych <math>x_1,\ldots,x_k</math>, to da się tak dobrać
wartości dla zmiennych <math>y_2,\ldots,y_{k-2}</math>, aby spełnione były
wszystkie klauzule w <math>D_j</math>. Na odwrót, jeśli <math>D_j</math> jest spełniona
dla pewnego wartościowania zmiennych
<math>x_1,\ldots,x_k,y_2,\ldots,y_{k-2}</math>, to łatwo wydedukować, że
<math>x_i=1</math> dla pewnego <math>1\leq i \leq k</math>. Mianowicie, jeśli <math>x_1=x_2=0</math>,
to z pierwszej klauzuli w <math>D_j</math> wynika że <math>y_2=1</math>. Ale wtedy z
drugiej klauzuli mamy <math>x_3=1</math> lub <math>y_3=1</math>. W pierwszym przypadku
rozumowanie jest zakończone, w drugim przenosimy rozumowanie na
trzecią klauzulę i tak dalej.
 
Zatem, po przekształceniu kolejno wszystkich alternatyw powstaje
równoważna formuła o co najwyżej trójskładnikowych alternatywach.
Pozostaje wykazać, że przekształcenie to realizowalne jest w pamięci
logarytmicznej. Zauważmy jednak, że aby wypisać formułę wynikową, MT
potrzebuje pamięć roboczą tylko na licznik bieżącej alternatywy
<math>C_j</math> oraz licznik wygenerowanych do tej pory nowych zmiennych.
}}
 
{{uwaga|[Uzupelnij]||
Zapewne zauważyłaś(-łeś), że w wielu podręcznikach do algorytmiki
również mówi się o NP-zupełności. Na ogół korzysta się wtedy z
redukcji wielomianowej. Złożoność czasowa jest łatwiejsza do analizy
w przypadku modelu obliczeń takiego jak (uproszczony) język
programowania wysokiego poziomu. Analiza złożoności pamięciowej (i
to tylko z uwzględnieniem pamięci roboczej) może być trudniejsza.
 
Redukcja logarytmiczna jest bardziej uniwersalna i dlatego stosujemy
ją w teorii złożoności.
}}
 
{{uwaga|[Uzupelnij]||
W literaturze przyjmuje sie również nieco inną definicję problemu
3SAT, w której zakłada sie dodatkowo, że w każdej klauzuli występują
dokładnie 3 parami różne literały. Dowód NP-zupełności tej wersji
otrzymujemy przez uzupełnienie dowodu powyższego w następujący
sposób:
 
Załóżmy że <math>k=2</math>. Wprowadzamy nową zmienną <math>y</math> i kładziemy <math>D_j =
(x_1 \vee x_2 \vee y) \wedge (x_1 \vee x_2 \vee \neg y)</math>. Jeśli
istnieje wartościowanie spełniające formułę <math>\phi</math>, to w tym
wartościowaniu formuła <math>\psi</math> powstała z <math>\phi</math> przez zastąpienie
klauzuli <math>C_j</math> formułą <math>D_j</math> jest również spełniona. I na odwrót,
jeśli pewne wartościowanie spełnia formułę <math>\psi</math>, to aby <math>D_j</math> było
prawdziwe <math>x_1</math> lub <math>x_2</math> musi mieć wartość 1, a zatem to samo
wartościowanie (bez zmiennej <math>y</math>) spełnia formułę <math>\phi</math>.
 
Analogicznie, jesli <math>C_j</math> składa się tylko z jednego literału, to
przekształcamy go w koniunkcję czterech trójskładnikowych klauzul, z
dodanymi dwiema nowymi zmiennymi.
 
Z tego spostrzeżenia będziemy korzystać w następnych dowodach
NP-zupełności.
}}
 
Odnotujmy w tym miejscu, że dalsze zawężenie problemu polegające na
dopuszczeniu klauzul o co najwyżej dwóch literałach, 2SAT, jest
problemem obliczeniowo łatwym. Dowód tego faktu odkładamy do
nastepnej lekcji.
 
===MAXSAT===
 
Warto wspomnieć o innych NP-zupełnych wersjach problemu
spełnialnosci. Na przykład, możemy zapytać o istnienie
wartościowania spełniającego co najmniej zadaną liczbe <math>k</math> klauzul
(a niekoniecznie wszystkie). Problem ten nosi nazwę MAXSAT, i jest
ogólniejszy niż SAT (a zatem jest również w NPC). Jego trudność
przejawia sie również w tym, że zawężenie do klauzul długości dwa w
przeciwieństwie do SAT, pozostawia ten problem trudnym.
 
{{twierdzenie|[Uzupelnij]||
Problem MAX2SAT jest NP-zupełny.
}}
 
{{dowod|[Uzupelnij]||
Konstruujemy redukcję z problemu 3SAT. Na wejściu mamy formułę
<math>\phi=C_1 \vee \ldots\vee C_m</math>. Każdą klauzulę <math>C_j=a\vee b\vee c</math>
przekształcamy w zbiór 10 klauzul, dla wygody rozważań podzielonych
na trzy grupy, następujacej postaci:
 
# <math>(a)(b)(c)(z)</math>
 
# <math>(\neg a\vee\neg b)(\neg b\vee\neg c)(\neg a\vee\neg c)</math>
 
# <math>(a\vee\neg z)(b\vee\neg z)(c\vee\neg z)</math>
 
Tych 10 klauzul ma następujace własności:
 
# Jeśli <math>a=b=c=0</math>, to niezależnie od wartości zmiennej <math>z</math> co
najwyżej 6 klauzul jest spełnionych.
 
# Jeśli któryś z literałów <math>a</math>, <math>b</math> lub <math>c</math> jest równy 1, to
można dobrać wartość <math>z</math> tak, że 7 klauzul jest spełnionych. Można
sie o tym przekonać analizując wszystkie przypadki. Na przykład,
jeśli <math>a=1</math>, <math>b=c=0</math>, to kładziemy <math>z=0</math>; jeśli <math>a=b=1</math>, <math>c=0</math>, to
również kładziemy <math>z=0</math>, jeśli natomiast <math>a=b=c=1</math> to 7 klauzul jest
spełnionych gdy <math>z=1</math>.
 
Pozostaje zdefiniować żądaną liczbę spełnionych klauzul w formule
wynikowej na <math>7m</math>. Z wymienionych własności wynika, że formuła
wynikowa posiada wartościowanie spełniające dokładnie <math>7m</math>
alternatyw wtedy i tylko wtedy gdy formuła wejściowa jest
spełnialna.
 
Maszyna Turinga realizująca redukcję potrzebuje pamieci roboczej
jedynie na liczniki, zatem działa w pamięci logarytmicznej.
}}
 
==NP-zupełne problemy grafowe==
 
===Pokrycie wierzchołkowe===
 
Pierwszym z serii problemów grafowych, dla których udowodnimy
NP-zupełność, jest problem pokrycia wierzchołkowego. Dla grafu
nieskierowanego <math>G=(V,E)</math> mówimy, że podzbiór <math>V'\subseteq V</math> jest
pokryciem wierzchołkowym, jeśli każda krawędź w G ma co najmniej
jeden z końców w zbiorze <math>V'</math>.
 
'''Problem''' NODE COVER<br>
''Wejście:'' Graf nieskierowany <math>G=(V,E)</math>, liczba całkowita <math>k\leq
|V|</math><br>
''Wyjście'': TAK jeśli G ma pokrycie wierzchołkowe o liczności k,
NIE w przeciwnym przypadku.
 
{{twierdzenie|[Uzupelnij]||
Problem NODE COVER jest NP-zupełny.
}}
 
{{dowod|[Uzupelnij]||
Dla podanego podzbioru zbioru wierzchołków bardzo łatwo sprawdzić
czy stanowi on pokrycie, zatem <math>{\textsc NODE COVER}\in NP</math>.
 
Redukujemy problem 3SAT do NODE COVER. Na wejściu mamy formułę
<math>\phi=C_1 \wedge\ldots\wedge C_m</math>, i zgodnie z uwagą poczyniona przy
dowodzie NP-zupełności 3SAT zakładamy, że każda alternatywa <math>C_j</math>
zawiera dokładnie 3 różne literały. Konstruujemy graf następujący:
każde wystąpienie literału jest wierzchołkiem grafu, wystąpienia
wewnątrz jednej klauzuli tworzą trójkąt. Ponadto, dla każdej pary
literałów przeciwnych wystepujących w różnych klauzulach
odpowiadające im wierzchołki łączymy krawędzią. Na koniec, kładziemy
<math>k=2m</math>.
 
{1cm}
 
[width<nowiki>=</nowiki>12cm]{rys_5_1.jpg}<br>
Redukcja 3SAT do NODE COVER
 
{1cm}
 
Teraz należy wykazać, że formuła wejsciowa jest spełnialna wtedy i
tylko wtedy gdy wygenerowany graf ma pokrycie wierzchołkowe o
liczności <math>k</math>. Z ograniczenia na wielkość pokrycia wynika, że z
każdego trójkąta do pokrycia muszą być wybrane dokładnie dwa
wierzchołki. Jeśli formuła jest spełnialna, to w każdym trójkącie
można wyróżnić jeden wierzchołek <math>v</math> odpowiadający literałowi
równemu 1. Do pokrycia wybieramy pozostałe dwa wierzchołki.
Pokrywają one wszystkie krawędzie trójkątów oraz wychodzące z tych
wierzchołków krawędzie między trójkątami. Każda pozostała krawędź,
wychodząca z wierzchołka <math>v</math>, prowadzi do pewnego wierzchołka <math>w</math>
odpowiadającego zaprzeczeniu literału wierzchołka <math>v</math>, zatem literał
wierzchołka <math>w</math> ma wartość zero i <math>w</math> jest wybrane do pokrycia w
trójkącie w którym występuje. Zatem krawędź <math>(v, w)</math> też jest
pokryta.
 
W drugą stronę, załóżmy, że dane jest pokrycie. W każdym trójkącie,
dla wierzchołka który nie jest w pokryciu, ustawiamy wartość
odpowiedniej zmiennej tak aby literał w tym wierzchołku był równy 1.
Należy zauważyć że takie wartościowanie jest niesprzeczne. Wynika to
stąd, że przeciwne literały zawsze odpowiadają dwóm wierzchołkom z
różnych trójkątów połączonych krawędzią. Co najmniej jeden z tych
wierzchołków jest w pokryciu, a więc odpowiadający mu literał nie
bierze udziału w obliczaniu wartościowania.
 
Zauważmy, że tak jak i poprzednio, do realizacji redukcji wystarczy
pamięć robocza rzędu <math>\log n</math>, co kończy dowód.
}}
 
===Klika, zbiór niezależny===
 
Przypomnijmy definicje obu problemów:
 
'''Problem''' INDEPENDENT SET<br>
''Wejście:'' Graf nieskierowany <math>G=(V,E)</math>, liczba całkowita <math>k\leq
|V|</math><br>
''Wyjście'': TAK jeśli <math>G</math> ma zbiór niezależny (indukowany podgraf
bez krawędzi) o <math>k</math> wierzchołkach, NIE w przeciwnym przypadku.
 
'''Problem''' CLIQUE<br>
''Wejście:'' Graf nieskierowany <math>G=(V,E)</math>, liczba całkowita <math>k\leq
|V|</math><br>
''Wyjście'': TAK jeśli <math>G</math> ma podgraf pełny (klikę) o <math>k</math>
wierzchołkach, NIE w przeciwnym przypadku.
 
{{cwiczenie||
Wykaż, że problem INDEPENDENT SET jest NP-zupełny.
}}
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  Jeśli <math>V'</math> jest pokryciem wierzchołkowym, to jaką własność
ma zbiór <math>V-V'</math>?
</div></div>
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> Dopełnienie pokrycia jest oczywiście zbiorem
niezależnym. Zatem redukcja z problemu NODE COVER, mając na wejściu
graf <math>G=(V,E)</math> i liczbę <math>k</math> generuje instancję <math>G'=(V',E'),k'</math>
problemu INDEPENDENT SET, kładąc <math>G'=G</math>, <math>k'=|V|-k</math>.
</div></div>
 
{{cwiczenie||
Wykaż, że problem INDEPENDENT SET jest NP-zupełny, wykorzystując
pokazaną wyżej redukcję z 3SAT do NODE COVER, zmieniając tylko
rozumowanie tak, aby odnosiło sie do problemu INDEPENDENT SET.
}}
 
{{cwiczenie||
Wykaż, że problem CLIQUE jest NP-zupełny.
}}
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  Rozważ dopełnienie grafu.
</div></div>
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  Redukcja z problemu INDEPENDENT SET. Graf wynikowy
jest dopełnieniem grafu źródłowego, a parametr <math>k</math> ma tę sama wartość.
</div></div>
 
===Cykl i ścieżka Hamiltona===
 
'''Problem''' HAMILTONIAN CYCLE<br>
''Wejście:'' Graf nieskierowany <math>G=(V,E)</math><br>
''Wyjście'': TAK jeśli <math>G</math> ma cykl Hamiltona, czyli cykl
przchodzący przez każdy wierzchołek dokładnie raz, NIE w przeciwnym
przypadku.
 
{{twierdzenie|[Uzupelnij]||
CYKL HAMILTONA jest NP-zupełny.
}}
 
{{dowod|[Uzupelnij]||
Przynależnośc do klasy NP jest oczywista. Konstruujemy redukcje z
problemu NODE COVER. na wejściu mamy nieskierowany graf <math>G=(V,E)</math>
oraz liczbę całkowitą <math>k\leq |V|</math>. Oznaczmy graf wynikowy jako
<math>G'=(V',E')</math>.
 
Redukcja przeprowadzona jest techniką gadżetu (w literaturze
angielskiej uzywa sie również terminu ''widget''). Gadżet to
fragment struktury wynikowej, o określonych własnościach. W naszym
przypadku pierwszym krokiem redukcji jest wygenerowanie, dla każdej
krawędzi <math>(u,v)\in E</math> gadżetu <math>G_{uv}=(V_{uv}, E_{uv})</math> będącego
grafem przedstawionym na rysunku 5.2.
 
{1cm}
 
[width<nowiki>=</nowiki>12cm]{rys_5_2.jpg}<br>
 
{1cm}
 
Jedynie narożne wierzchołki grafu <math>G_{uv}</math> będą połączone z
wierzchołkami spoza <math>G_{uv}</math>. Stąd wynika, że jeśli <math>G'</math> ma cykl
Hamiltona, to musi on przechodzić przez <math>G_{uv}</math> tylko na jeden z
przedstawionych na rysunku 5.3 sposobów. Konstrukcja gadżetu
uniemożliwia inne usytuowanie cyklu Hamiltona względem <math>G_{uv}</math>.
 
{1cm}
 
[width<nowiki>=</nowiki>12cm]{rys_5_3.jpg}<br>
 
{1cm}
 
Drugi krok redukcji to wygenerowanie krawędzi w <math>G'</math> łączących
gadżety w tak zwane ścieżki. Dla każdego wierzchołka <math>v \in V</math>
najpierw porządkujemy dowolnie wszystkie jego sąsiednie wierzchołki,
oznaczmy je przez <math>u_v^1,\ldots,u_v^{d(v)}</math>, gdzie <math>d(v)</math> jest
stopniem wierzchołka <math>v</math>. Konstrukcja ścieżki odpowiadającej
wierzchołkowi <math>v</math>, łączącej wszystkie gadżety odpowiadające
krawędziom incydentnym z <math>v</math>, dokonuje sie przez dołączenie do <math>G'</math>
zbioru krawędzi postaci
 
<center><math>
E_v=\{([v,u_v^i,6],[v,u_v^{i+1},1]), i=1,\ldots,d(v)-1\}</math></center>
 
Ostatni krok to dodanie wierzchołków-selektorów <math>s_1,\ldots,s_k</math>, i
połączenie krawędzią każdego selektora z początkiem i końcem ścieżki
odpowiadającej wierzchołkowi <math>v</math>, dla każdego <math>v</math>.
 
<center><math>
E_S=\{(s_i,[v,u_v^1,1]):v\in V, 1\leq i\leq k\} \cup
\{(s_i,[v,u_v^d(v),6]):v\in V, 1\leq i\leq k\}</math></center>
 
Kładziemy zatem
 
<center><math>
V'=\bigcup_{(uv)\in E}V_{uv}\cup\{s_j, 1\leq j\leq k\}</math></center>
 
<center><math>
E'=\bigcup_{(uv)\in E}E_{uv}\cup \bigcup_{v\in V}E_v \cup E_S</math></center>
 
{1cm}
 
[width<nowiki>=</nowiki>12cm]{rys_5_4.jpg}<br>
 
{1cm}
 
Na rys. 5.4 pokazano graf o 4 wierzchołkach i rezultat redukcji.
Zacieniowane zostały dwa wierzchołki grafu które tworzą pokrycie.
Pogrubione krawędzie tworza cykl Hamiltona. Zaczynając od selektora
<math>s_1</math> przechodzimy do początku ścieżki odpowiadającej pierwszemu
wierzchołkowi z pokrycia, czyli <math>x</math>. Po przejściu gadżetów na tej
ścieżce wracamy do <math>s_2</math>, a stąd do początku ścieżki odpowiadajacej
drugiemu węzłowi z pokrycia, <math>y</math>.
 
Wykażemy, że <math>G'</math> ma cykl Hamiltona wtedy i tylko wtedy gdy G ma
pokrycie o liczności <math>k</math>.
 
Załóżmy, że <math>G'</math> ma cykl Hamiltona i prześledźmy jego bieg
zaczynając od <math>s_1</math> (w dowolnym kierunku). Następny wierzchołek na
cyklu musi być początkiem (lub końcem - załóżmy to pierwsze) ścieżki
gadżetów dla pewnego wierzchołka <math>v_1\in V</math>. Dodajemy <math>v_1</math> do
generowanego pokrycia. Zgodnie z własnością gadżetu, cykl przebiega
całą ścieżkę i na końcu przechodzi do innego selektora, załóżmy że
jest to <math>s_2</math>. Z <math>s_2</math> musi przejść na początek lub koniec innej
ścieżki, odpowiadającej wierzchołkowi <math>v_2</math>. Dodajemy <math>v_2</math> do
pokrycia i kontynuujemy. Z ostatniej, <math>k</math>-tej ścieżki, cykl musi
wrócić do <math>s_1</math>. Ponieważ cykl Hamiltona przeszedł przez wszystkie
wierzchołki <math>G'</math>, a więc przez wszystkie gadżety <math>G_{uv}</math>, zatem
wybrane w ten sposób wierzchołki <math>v_1,\ldots,v_k</math> stanowią pokrycie.
 
Teraz załóżmy, że <math>G</math> ma pokrycie <math>\{v_1,\ldots,v_k\}</math>. Konstruujemy
cykl Hamiltona w <math>G'</math>. Zaczynamy od selektora <math>s_1</math> i przechodzimy
na początek ścieżki związanej z <math>v_1</math>, czyli do węzła
<math>[v_1,u_{v_1}^1,1]</math>. Przechodzimy przez kolejne gadżety aż do końca
ścieżki. Dla danego gadżetu <math>G_{v_1u_{v_1}^i}</math> musimy podjąć decyzję
czy przechodzimy przez wszystkie wierzchołki czy tylko przez połowę
(jedną "ścianę"). Decyzja zależy od tego czy <math>u_{v_1}^i</math> również
należy do pokrycia. Jeśli nie, to przechodzimy cały gadżet, jeśli
tak, to drugą "ścianę" pozostawiamy, aby później, gdy trawersowana
będzie ścieżka dla <math>u_{v_1}^i</math> również można było przejść przez
<math>G_{v_1u_{v_1}^i}</math>. Z ostatniego węzła na ścieżce przechodzimy do
selektora <math>s_2</math> i powtarzamy konstrukcję. Z ostatniego węzła na
<math>k</math>-tej ścieżce wracamy do <math>s_1</math>, zamykając w ten sposób cykl
Hamiltona.
 
Ostatnim krokiem dowodu jest stwierdzenie, że konstrukcję grafu <math>G'</math>
można wykonać posługując się pamięcią roboczą rozmiaru
logarytmicznego. Wynika to, jak i w poprzednich dowodach, z tego że
maszynie wystarcza pamięć na licznik położenia w wejściowym grafie
oraz licznik numeru (nazwy) generowanego wierzchołka i krawędzi
grafu <math>G'</math>.
 
}}
 
Bardzo podobny w sformułowaniu jest problem ścieżki Hamiltona
(HAMILTONIAN PATH). Na weściu jest graf nieskierowany, na wyjściu
jest TAK jeśli w grafie istnieje ścieżka przechodząca przez każdy
wierzchołek dokładnie raz. Oczywiste jest że istnienie cyklu
Hamiltona implikuje istnienie ścieżki Hamiltona, jednak są to różne
problemy, i NP-zupełnośc tego drugiwgo wymaga osobnego dowodu. Tym
niemniej, na przykładzie tych problemów można pokazać pewne techniki
dowodzenia NP-zupełności w takich przypadkach. Jedną z nich jest
modyfikacja znanego już dowodu NP-zupełności problemu podobnego,
drugą zaś redukcja z problemu podobnego.
 
{{twierdzenie|[Uzupelnij]||
Problem HAMILTONIAN PATH jest NP-zupełny.
}}
 
{{cwiczenie||
Metoda 1: zmodyfikuj konstrukcję grafu <math>G'</math> w dowodzie NP-zupełności
problemu HAMILTONIAN CYCLE tak aby stanowił dowód NP-zupełności
problemu HAMILTONIAN PATH.
}}
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
Należy "wymusić" rozpoczęcie i zakończenie ścieżki dodatkowymi
selektorami
</div></div>
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
Dodajemy selektor <math>s_0</math> i łączymy go krawędzią z <math>s_1</math>.
następnie dodajemy selektor <math>s_{k+1}</math> i łączymy go z początkami i
końcami wszystkich ścieżek. na koniec dodajemy <math>s_{k+2}</math> i łączymy
go z <math>s_{k+1}</math>. Jeśli graf wynikowy posiada ścieżkę Hamiltona, to
jej końcami muszą być selektory <math>s_0</math> i <math>s_{k+2}</math>. Pozostała część
rozumowania jest analogiczna.
</div></div>
 
{{cwiczenie||
Metoda 2: Skonstruuj redukcję z problemu CYKL HAMILTONA.
}}
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
Dodaj nowe wierzchołki które będą końcami ścieżki Hamiltona i
powiąż je odpowiednio z innym wierzchołkami.
</div></div>
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
Nie prowadzi do celu narzucający się pomysł aby dowiązać 2
nowe wierzchołki do końców dowolnie ustalonej krawędzi. Skuteczna
jest natomiast modyfikacja tej idei: wybrać dowolny wierzchołek <math>v</math>,
utworzyć wierzchołek <math>v'</math> o takim samym zbiorze sąsiadów w grafie
(inaczej: rozszczepić v na dwa identyczne), a nastepnie dołączyć
nowy wierzchołek <math>u_1</math> do <math>v</math> i jeszcze jeden nowy <math>u_2</math> do <math>v'</math>.
Łatwo sie przekonać że w nowym grafie istnieje ścieżka Hamiltona
(koniecznie o końcach <math>u_1, u_2</math>) wtedy i tylko wtedy gdy w
oryginalnym grafie istnieje cykl Hamiltona.
</div></div>
 
==Problemy na zbiorach i liczbach==
 
===Trójdzielne skojarzenie i pokrycie zbiorami===
 
Uogólnieniem klasycznego problemu skojarzenia w grafie dwudzielnym
jest następujący problem:
 
'''Problem '''TRIPARTITE MATCHING<br>
''Wejście: ''parami rozłączne równoliczne zbiory <math>W,X,Y</math> o mocy
<math>p>0</math> oraz relacja <math>R\subseteq W\times X\times Y</math><br>
''Wyjście: ''TAK, jeśli istnieje skojarzenie w <math>R</math>, czyli podzbiór
<math>R' \subseteq R</math> taki, że dla dowolnych trójek
<math>(w,x,y),(w',x',y')\in R</math> zachodzi
<math>w\neq w'</math>, <math>x\neq x'</math> oraz <math>y\neq y'</math>. NIE w przeciwnym przypadku.<br>
 
Problem skojarzenia dwudzielnego jest obliczeniowo łatwy.
Uogólnienie do trzech wymiarów utrudnia problem radykalnie.
 
{{twierdzenie|[Uzupelnij]||  
Problem TRIPARTITE MATCHING jest NP-zupełny.
}}
 
{{dowod|[Uzupelnij]||
Ponownie mamy do czynienia z dość skomplikowaną konstrukcją
posługującą się gadżetami, redukującą problem 3SAT do naszego
problemu.
 
Na wejściu mamy zbiór klauzul <math>C=\{C_1,\ldots,C_m\}</math> nad zmiennymi
<math>U=\{u_1,\ldots,u_n\}</math>. Najpierw dla każdej zmiennej <math>u\in U</math>
konstruujemy gadżet <math>T_u</math>, który będzie odpowiadał za wybór
wartościowania tej zmiennej. Składa się on z dwóch zbiorów trójek:
 
<center><math>
T_u^t=\{(w_{2j}^u,x_j^u,y_j^u), 1\leq j\leq m\}</math></center>
 
<center><math>
T_u^f=\{(w_{2j+1}^u,x_{j+1}^u,y_j^u), 1\leq j<m\}\cup\{(w_1^u,x_1^u,y_m^u)\}</math></center>
 
Przykładowy gadżet dla zmiennej <math>u</math>, w przypadku gdy liczba klauzul
wynosi <math>m=4</math> pokazano na rysunku 5.5. Grubą linią zaznaczono trójki
ze zbioru
 
{1cm}
 
[width<nowiki>=</nowiki>12cm]{rys_5_5.jpg}<br>
 
{1cm}
 
Dla każdego gadżetu pierwsze elementy trójek, <math>w_1^u,\ldots,w_m^u</math>,
występują jeszcze w innych trójkach, które za chwilę zdefiniujemy.
Pozostałe elementy występuja tylko w danym gadżecie. Zatem, jeśli
wybrano skojarzenie, to dla ustalonego gadżetu to skojarzenie
zawiera albo cały zbiór <math>T_u^f</math> i żadnej trójki z <math>T_u^t</math>, albo na
odwrót. W toku dalszego rozumowania, wybór do skojarzenia zbioru
<math>T_u^f</math> będzie oznaczał wartościowanie zmiennej <math>u</math> na ''false'' i
pozostawi niepokryte elementy <math>w</math> o indeksach parzystych. Wybór
przeciwny ustali wartościowanie <math>u</math> na ''true'' i pozostawi
niepokryte elementy <math>w</math> o indeksach nieparzystych. Sytuacja taka
została przedstawiona na rysunku 5.5, pogrubioną linią zaznaczono
wybór trójek <math>T_u^t</math>.
 
Trójki które zdefiniujemy teraz mogą być nazwane "składową
testowania". Skojarzą one niepokryte elementy z gadżetów z
odpowiednimi wystąpieniami literałów w klauzulach. Dla każdej
klauzuli <math>C_j=(p_j\vee q_j\vee r_j)</math> składowa testowania <math>S_j</math>
zawiera 3 trójki <math>s_j^1,s_j^2,s_j^3</math> odpowiadajace kolejnym
literałom <math>p,q,r</math>, zdefiniowane następująco: Jeśli <math>p=u_i</math> to
<math>s_j^1=(w_{2j-1}^u,a_j, b_j)</math>. Jeśli <math>p=\neg u_i</math> to
<math>s_j^1=(w_{2j}^u,a_j,b_j)</math>. Analogicznie dla literałów <math>q, r</math>.
 
Elementy <math>a_j, b_j</math> występują tylko w trzech trójkach zbioru <math>S_j</math>,
zatem skojarzenie wybiera dokładnie jedną z tych trójek. Aby móc
daną trójkę wybrać, element na pierwszej współrzędnej w tej trójce
musi być niepokryty trójkami z odpowiedniego gadżetu. Ale to oznacza
że wartość danego literału jest ''true'', czyli klauzula <math>C_j</math>
jest spełniona. Innymi słowy, możliwość pokrycia elementów <math>a_j,
b_j</math> jest równoważna temu, że istnieje w klauzuli <math>C_j</math> literał o
wartości logicznej ''true''.
 
Skojarzenie wybrane dla gadżetów ma liczność <math>nm</math>, składowa
testowania daje kolejnych <math>m</math> trójek w skojarzeniu, zatem ze
wszystkich <math>2nm</math> elementów na pierwszej współrzędnej (elementy <math>u</math>)
<math>(n-1)m</math> pozostaje nieskojarzonych. Zatem w konstrukcji potrzebna
jest jeszcze trzecia "składowa odśmiecania" zdefiniowana
nastepująco:
 
<center><math>
G=\{(w_i^u,g_k,h_k):u\in U, 1\leq i\leq 2m, 1\leq k\leq (n-1)m\}</math></center>
 
Pozwala ona skojarzyć elementy <math>u</math> pozostałe po wyborze
wartościowania i testu spełnialności.
 
Na podstawie opisanej konstrukcji i komentarzy jej towarzyszących
możemy juz łatwo stwierdzić, że formuła wejściowa posiada
wartościowanie spełniające wtedy i tylko wtedy gdy utworzony w
wyniku redukcji zbiór trójek ma skojarzenie.
}}
 
Rozważmy jeszcze trzy podobne problemy na zbiorach. Ich NP-zupełność
stanie sie oczywista gdy zauważymy że stanowią one kolejne
uogólnienia problemu trójdzielnego skojarzenia.
 
'''Problem '''EXACT COVER BY 3-SETS (pokrycie trójelementowymi podzbiorami)<br>
''Wejście: ''Rodzina <math>\cal F</math> trójelementowych podzbiorów zbioru
<math>X</math>
takiego że <math>|X|=3k</math> dla pewnej calkowitej <math>k</math><br>
''Wyjście: ''TAK jesli istnieje podrodzina <math>\cal F' \subseteq \cal
F</math> taka, że każdy element zbioru <math>X</math> należy do dokładnie jednego zbioru rodziny <math>\cal F"</math>,
NIE w przeciwnym przypadku<br>
 
{{cwiczenie||
Wykaż że EXACT COVER BY 3-SETS jest NP-zupełny.
}}
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> 
Zauważ, że jeśli ograniczymy sie do instancji w których X jest
podzielone na trzy rozłączne równoliczne zbiory, a wszystkie
podzbiory w rodzinie <math>F</math> zawieraja po jednym elemencie z każdego z
tych trzech podzbiorów, to otrzymujemy problem TRIPARTITE MATCHING
(formalnie są to izomorficzne struktury). Zatem EXACT COVER BY
3-SETS jest uogólnieniem TRIPARTITE MATCHING, a ponieważ, co
oczywiste, jest w NP, więc jest NP-zupełny.
</div></div>
 
'''Problem''' SET COVERING (pokrycie zbiorami)<br>
''Wejście: ''Rodzina <math>F=\{S_1,\ldots,S_n\}</math> podzbiorów zbioru
<math>|X|</math>,
liczba całkowita <math>k\leq n</math><br>
''Wyjście: ''TAK, jeśli istnieje k-elementowa podrodzina rodziny
<math>F</math>,
która pokrywa cały zbiór <math>|X|</math>, w przeciwnym przypadku NIE.<br>
 
{{cwiczenie||
Wykaż NP-zupełność problemu SET COVERING.
}}
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> 
Ponownie przez ograniczenie do podproblemu: jeśli założymy że
<math>|X|=3k</math> a wszystkie zbiory rodziny <math>F</math> są 3-elementowe, to
otrzymujemy problem EXACT COVER BY 3-SETS.
</div></div>
 
===Suma podzbioru i inne problemy liczbowe===
 
Teraz zajmiemy się kilkoma problemami związanymi z liczbami.
Najwięcej trudu będzie kosztować udowodnienie NP-zupełności
pierwszego z nich -- następne pójdą już łatwiej. Ta pierwsza
trudność zasadza się na tym, że jak do tej pory dowodziliśmy
NP-zupełność tylko dla problemów, w których tak naprawdę nie ma
liczb, jako elementów struktury kombinatorycznej. Oczywiście, każde
słowo wejściowe może byc traktowane jako liczba, kod maszyny Turinga
tez jest liczbą. Tutaj jednak chodzi o naturalne sformułowanie
problemu, w odniesieniu do obiektów abstrakcyjnych takich jak
liczby, funkcje, relacje, grafy itd. Problematyka trudności
obliczeniowej problemów z liczbami jest rozwinięta w następnej
lekcji.
 
'''Problem '''SUBSET SUM (suma podzbioru)<br>
''Wejście: ''Skończony zbiór <math>A</math> elementów, dla każdego elementu
<math>a\in A</math> waga <math>s(a)\in Z^+</math> oraz liczba <math>B\in Z^+</math>.  <br>
''Wyjście: ''TAK jeśli istnieje podzbiór <math>A'\subseteq A</math> taki że
<math>\sum_{a\in A'}s(a) = B</math>, NIE w przeciwnym przypadku. <br>
 
{{twierdzenie|[Uzupelnij]||
Problem SUBSET SUM jest NP-zupełny.
}}
 
{{dowod|[Uzupelnij]||
Skonstruujemy redukcję z problemu EXACT COVER BY 3 SETS. Na wejściu
mamy zatem zbiór <math>X</math> o liczności <math>3m</math> i rodzinę
<math>F=\{U_1,\ldots,U_n\} </math> jego podzbiorów. Naszym zadaniem jest
skonstruować zbiór <math>Y</math> elementów z pewnymi wagami oraz liczbę B
taką, że istnienie podzbioru w <math>Y</math> o sumie wag elementów równej <math>B</math>
"wymusza" istnienie pokrycia zbioru <math>X</math> wybranymi rozłącznymi
podzbiorami z rodziny <math>F</math>.
 
Niech <math>p=\lceil\log_2(n+1)\rceil</math>. Najpierw ustalamy porządek
elementów w zbiorze <math>|X|</math> i zapisujemy każdy zbiór <math>U_j</math> jako wektor
<math>3m</math>-bitowy (czyli jest to struktura danych -- wektor bitowy --
reprezentująca podzbiór danego zbioru). W każdym wektorze są
oczywiście 3 bity równe 1 a pozostałe są zerowe. Następnie przed
każdym bitem wstawiamy dodatkowo <math>p-1</math> bitów zerowych i traktujemy
ten wektor kjako liczbe zapisaną binarnie. Powstaje w ten sposób <math>n</math>
liczb <math>3mp</math>-bitowych -- są to wagi elementów zbioru Y. Liczba <math>B</math>
jest również takiej długości, powstaje przez wypisanie <math>3m</math> jedynek
a następnie wstawienie przed każdą jedynką <math>p-1</math> zer.
 
Jeśli istnieje podrodzina <math>F'\subseteq F</math> stanowiąca rozłączne
pokrycie zbioru <math>X</math>, to wektory bitowe poszczególnych trójek z <math>F'</math>
arytmetycznie sumują sie do <math>B</math>, a na żadnej pozycji nie występuje
przeniesienie. Zatem z istnienia pokrycia wynika istnienie podzbioru
dającego w sumie wagę <math>B</math>.
 
Bloki zer dodane przed każdym bitem reprezentacji wektorowej
podzbioru gwarantują, że sumując dowolny podzbiór wygenerowanych
liczb nie napotkamy na przeniesienie poza taki blok zer. A zatem,
jeśli istnieje podzbiór liczb dający w sumie <math>B</math>, to wszystkie te
liczby w swoich rozwinięciach binarnych zawierają w sumie tyle
jedynek ile jest ich w <math>B</math>, na różnych pozycjach. A więc
odpowiadajace tym liczbom podzbiory pokrywają cały zbiór <math>X</math>.
 
Zatem opisane przekształcenie jest redukcją. Jak w poprzednich
dowodach, potrzebna jest pamięć robocza jedynie na stałą liczbę
liczników. A więc jest to redukcja logarytmiczna.
}}
 
W tej części lekcji wykażemy NP-zupełność dwóch podobnych
problemów liczbowych.
 
'''Problem '''PARTITION (podział)<br>
''Wejście: ''Skończony zbiór <math>A</math> elementów oraz dodatnia całkowita
waga <math>s(a)</math> każdego elementu<br>
''Wyjście: ''TAK jeśli istnieje podzbiór <math>A'\subseteq A</math> taki że
<math>\sum_{a\in A'}s(a) = \sum_{a\in A-A'}s(a)</math>, NIE w przeciwnym
przypadku.
 
{{cwiczenie||
Wykaż NP-zupełność problemu podziału.
}}
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> 
Skorzystaj z SUBSET SUM. Wystarczy dodać dwa elementy o odpowiednio
dobranej dużej wadze.
</div></div>
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> 
Niech <math>S=\sum_{a\in A}s(a)</math>. Dodajemy do zbioru dwa elementy <math>b_1</math> i
<math>b_2</math>, <math>s(b_1)=2S-B, s(b_2)=S+B</math>. Łatwo sprawdzić, że:
 
* Jeśli w zbiorze <math>A</math> istnieje podzbiór <math>A'</math> o sumie równej <math>B</math>,
to podzbiór ten z dołączonym elementem <math>b_1</math> daje sumę równą <math>2S</math>,
tyle co pozostałe elementy uzupełnione o <math>b_2</math>.
 
* jeśli w zbiorze <math>A\cup \{b_1,b_2\}</math> istnieje podział na 2
podzbiory o jednakowych wagach, to elementy <math>b_1</math> i <math>b_2</math> sa w
różnych podzbiorach, bo ich wagi sumują się do <math>3S</math>. W tym
podzbiorze do którego należy <math>b_1</math> suma wag pozostałych elementów
wynosi <math>B</math>.
 
</div></div>
 
'''Problem '''KNAPSACK (plecak)<br>
''Wejście: ''Skończony zbiór <math>A</math> elementów, rozmiar <math>s(a)\in Z^+</math>
i wartość <math>v(a)\in Z^+</math> dla każdego elementu, ograniczenie
pojemności <math>B\in Z^+</math> oraz żądana wartość <math>K\in Z^+</math><br>
''Wyjście: ''TAK jeśli istnieje podzbiór <math>A'\subseteq A</math> taki że
<math>\sum_{a\in A'}s(a) \leq B</math> oraz <math>\sum_{a\in A}v(a)\geq K</math>, NIE w
przeciwnym przypadku.
 
{{cwiczenie||
Pokaż że KNAPSACK jest NP-zupełny.
}}
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> 
Wykorzystaj SUBSET SUM lub PARTITION.
</div></div>
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> 
Jeśli założymy, że rozmiary elementów są równe ich wartościom, a
pojemnośc plecaka jest równa żądanej wartości, to otrzymamy problem
SUBSET SUM.
</div></div>
 
==Podsumowanie technik dowodów NP-zupełności==
 
Najprostsze redukcje otrzymujemy metodą zacieśnienia. Przez
narzucenie dodatkowych zależności w instancjach problemu, o którym
dowodzimy NP-zupełności, otrzymujemy instancje znanego problemu
NP-zupełnego. W ten sposób wykazujemy, że nasz problem jest
uogólnieniem problemu znanego, a więc jest niełatwiejszy. Przykłady
takich redukcji zastosowaliśmy do problemów: EXACT COVER BY 3SETS,
SET COVERING, KNAPSACK.
 
Pozostałe dowody można by zaliczyć do metody gadżetów. Fragmenty
instancji problemu wejściowego przekształca się we fragmenty
instancji probelmu wynikowego (gadżety), i wiąże się zależnościami
(innymi gadżetami), których zachodzenie w problemie wynikowym ma
mieć ścisłe odzwierciedlenie w spełnieniu wymagań problemu
źródłowego. Czasem gadżet jest trywialny (np. w redukcji SUBSET SUM
do PARTITION jest to ta sama waga elementu), kiedy indziej dość
naturalny i nietrudny (SAT DO 3SAT), czasem bardzo pomysłowy (VERTEX
COVER do HAMILTONIAN CYCLE, 3SAT do TRIPARTITE MATCHING, 3SAT do
MAX2SAT).
 
==Ćwiczenia końcowe==
 
{{cwiczenie|| Wykaż, że następujący problem izomorfizmu podgrafu jest NP-zupełny:
 
'''Problem''' SUBGRAPH ISOMORPHISM<br>
''Wejście: ''<math>G_1=(V_1, E_1)</math>, <math>G_2=(V_2, E_2)</math> - grafy nieskierowane<br>
''Wyjście: ''TAK jeśli <math>G_1</math> ma podgraf izomorficzny z <math>G_2</math>, NIE
w przeciwnym przypadku.<br>
}}
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> 
Istnieje redukcja najprostszego typu z jednego z analizowanych
powyżej problemów.
</div></div>
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> 
Jest to proste ugólnienie problemu CLIQUE: szczególnym przypadkiem
podgrafu o który pytamy w problemie SUBGRAPH ISOMORPHISM jest klika
o liczności <math>k</math> o która pytamy w problemie CLIQUE.
</div></div>
 
{{cwiczenie|| W tym ćwiczeniu pytamy o trudność obliczeniową
problemu pochodzącego z teorii szergowania. Wykaż, że NP-zupełny
jest następujący problem:
 
'''Problem''' SEQUENCING WITHIN INTERVALS<br>
''Wejście: ''Zbiór zadań <math>T</math>, dla każdego zadania <math>t</math> trzy liczby
całkowite: długość zadania <math>l(t)> 0</math>, moment pojawienia się
<math>r(t)\geq 0</math>,oraz ograniczenie czasowe <math>d(t)>0</math><br>
''Wyjście: ''TAK, jeśli wszystkie zadania można wykonać na jednym
procesorze, bez przerywania, spełniając ograniczenia czasowe, NIE w
przeciwnym przypadku. Formalnie, pytamy o funkcję alokacji <math>A</math>
przydzielająca każdemu zadaniu <math>t</math> czas rozpoczęcia wykonywania
<math>A(t)</math> taki, że <math>[A(t), A(t)+l(t)] \subseteq [r(t),d(t)]</math> oraz
<math>[A(t), A(t)+l(t)) \cap [A(t'), A(t')+l(t')) = \emptyset</math>, dla
każdego zadania <math>t' \neq t</math>.<br>
}}
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> 
Spróbuj, układając na prostej (osi liczbowej) odpowiednio
zdefiniowany ciąg odcinków (zadań), wymusić istnienie podzbioru o
zadanej sumie.
</div></div>
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> 
Redukcja z problemu SUBSET SUM za pomocą bardzo prostych gadżetów.
Niech <math>s_1, \ldots,s_n</math> oraz <math>B</math> będą odpowiednio wagami elementów
oraz żądana sumą podzbioru elementów. Niech <math>D=\sum_{i=1}^n s_i</math>.
Konstruujemy <math>n+1</math> zadań, przy czym dla <math>i=1,\ldots,n</math> zadanie <math>t_i</math>
ma długość <math>l_i=s_i</math>, czas gotowości <math>r_i=0</math> oraz granicę <math>d_i=D+1</math>.
Zadanie <math>t_{n+})</math> jest "wymuszaczem podziału", o parametrach
<math>l_i=1</math>, <math>r_i=B</math>, <math>d_i=B+1</math>.
 
Zadania <math>s_1, \ldots,s_n</math> mają pozorną swobodę wykonywania sie w
dowolnym miejscu osi czasu, zauważmy jednak że każde ulokowanie
wszystkich zadań nie zostawia żadnej luki na osi. Dla wymuszacza
jest tylko jedna możliwa wartość alokacji, <math>B</math>. Takie położenie
dzieli cały przedział, w którym moga byc wykonywane zadania, na dwa
podprzedziały, rozdzielone wymuszaczem. Jeden z tych przedziałów ma
długość <math>B</math>, zatem ulokowanie zadań na osi, zgodne z warunkami
zadania, jest możliwe wtedy i tylko wtedy gdy istnieje podzbiór
zbioru elementów w instancji problemu SUBSET SUM, ktych wagi dają w
sumie <math>B</math>.
</div></div>
 
{{cwiczenie||
Problem cięcia w grafie zdefiniowany jest następująco:
 
'''Problem''' FEEDBACK VERTEX SET<br>
''Wejście: ''Graf skierowany <math>G=(V, E)</math>, liczba całkowita <math>k, 0<k\geq |V|</math>.<br>
''Wyjście: ''TAK jeśli istnieje w <math>G</math> podzbiór <math>k</math>-wierzchołkowy,
taki że graf pozostały po usunięciu tego podzbioru jest
acykliczny.<br>
Udowodnij, że FEEDBACK VERTEX SET jest NP-zupełny.
}}
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> 
Jak zwykle, najtrudniej dobrać problem źródłowy dla redukcji.
Proponujemy pokrycie wierzchołkowe. Jak powinien wyglądać wynik
redukcji -- graf skierowany -- aby rozcinanie wszsytkich cykli przez
usuwanie wierzchołków znaczyło to samo co definiowanie pokrycia w
grafie źródłowym?
</div></div>
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> 
Na wejściu mamy graf nieskierowany <math>G=(V,E)</math> i liczbę <math>k</math>.
Zamieniamy ten graf na graf skierowany <math>G'</math>, z tym samym zbiorem
wierzchołków, zastępując każdą krawędź nieskierowaną <math>(u,v)</math> przez
dwie krawędzie skierowane: <math>(u,v)</math> oraz <math>(v,u)</math>. Liczba <math>k</math> jest
taka sama dla obu instancji.
 
Nietrudno zauważyć, że każde pokrycie wierzchołkowe w <math>G</math> jest
zbiorem rozcinającym wszystkie cykle w <math>G'</math> i na odwrót.
</div></div>
 
{{cwiczenie||
Kolorowanie (wierzchołkowe) grafu jest klasycznym problemem
optymalizacyjnym w teorii grafów. Przypomnijmy, że chodzi o
przypisanie wierzchołkom grafu nieskierowanego kolorów tak, aby
końce każdej krawędzi miały różne kolory, a liczba kolorów była
możliwie najmniejsza.
 
Okazuje sie że nawet jeśli ustalimy żądaną liczbe kolorów na 3, to
problem jest NP-zupełny. Dowód tego faktu nie jest natychmiastowy.
 
'''Problem''' 3COLORING<br>
''Wejście: ''Graf nieskierowany <math>G=(V,E)</math>. <br>
''Wyjście: ''TAK, jeśli istnieje funkcja <math>c : V \rightarrow
\{0,1,2\}</math> taka, że dla każdej krawędzi <math>(u,v)\in E</math>, <math>c(u)\neq
c(v)</math>.<br>
Za pomocą redukcji z problemu 3SAT udowodnij, że problem
trójkolorowania jest NP-zupełny.
}}
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> 
Można użyć gadżetu przedstawionego na rysunku 5.6.
{1cm}
 
[width<nowiki>=</nowiki>12cm]{rys_5_6.jpg}<br>
 
{1cm}
'''UWAGA DLA REDAKCJI: RYSUNEK POJAWIA
SIĘ JAKO CZĘŚĆ WSKAZÓWKI'''
</div></div>
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> 
Gadżet ma następujące własności:
 
* jeśli wierzchołkom <math>u,v,z</math> przypisano kolory tak, że co najmniej
jeden z nich ma kolor 1, to istnieje uzupełnienie trójkolorowania
pozostałych wierzchołków takie, że <math>c(z)=1</math>
 
* jeśli w danym trójkolorowaniu <math>c(u)=c(v)=c(z)=0</math>, to
również <math>c(z)=0</math>.
 
Redukcję przeprowadzamy następująco:
 
# generujemy wierzchołki <math>s,t,z</math> i trójkat oparty na nich
 
# Dla każdej zmiennej <math>x</math> występującej w instancji 3SAT definiujemy
wierzchołki <math>x, \neg x</math> oraz trójkąt oparty na <math>x,\neg x</math> oraz <math>t</math>
 
# dla każdej klauzuli <math>C_j=(u\vee v\vee w)</math> definiujemy kopię gadżetu,
przy czym wierzchołki <math>u,v,w</math> to już wygenerowane w punkcie 2
wierzchołki literałów o tych samych nazwach, wierzchołek <math>z</math> został
wygenerowany w kroku 1, natomiast pozostałe wierzchołki są nowe,
unikalne dla każdej klauzuli
 
{1cm}
 
[width<nowiki>=</nowiki>12cm]{rys_5_7.jpg}<br>
 
{1cm}
 
Wykazemy, że formuła źródłowa ma spełniające wartościowanie wtedy i
tylko wtedy gdy wygenerowany graf można pokolorować trzema kolorami.
 
Jeśli istnieje wartościowanie spełniające formułę, to
 
* kładziemy <math>c(s)=0</math>, <math>c(z)=1</math> <math>c(t)=2</math>
 
* kolorujemy każdy z wierzchołków <math>x_i, \neg x_i</math> jego wartością
logiczną, 0 lub 1
 
* uzupełniamy kolory 0, 1, i 2 w gadżetach -- można to zrobić gdyż
zadane wartościowanie spełnia formułę, a więc na wejściu do każdego
gadżetu jest co najmniej jeden wierzchołek koloru 1
 
Jeśli zadane jest trójkolorowanie grafu, to obliczamy wartościowanie
spełniające formułę następująco:
 
* kolory wierzchołków <math>s,t,z</math> są różne, więc umawiamy się, że <math>c(s)=0,
c(t)=2, c(z)=1</math>
 
* dla każdej zmiennej <math>x_i</math> kładziemy wartość tej zmiennej równą
<math>c(x_i)</math>. Ponieważ <math>c(t)=2</math> więc wartość ta wynosi 0 lub 1.
 
Ponieważ <math>c(z)=1</math>, więc dla każdego gadżetu co najmniej jeden z jego
trzech wejściowych wierzchołków ma kolor 1, a zatem w każdej
klauzuli mamy co najmniej jedną jedynkę.
 
</div></div>

Aktualna wersja na dzień 08:57, 28 sie 2023

When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).

True

False

Testy

When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).

True

False

When working with character arrays, always reserve enough array elements to hold the string AND its null-terminating character (\0).

True

False

In C++, 14 % 4 =

1

2

3

4

In C++, 14 % 4 =

1

2

3

4

Variables that are declared, but not initialized, contain

blank spaces

zeros

"garbage" values

nothing - they are empty

Variables that are declared, but not initialized, contain

blank spaces

zeros

"garbage" values

nothing - they are empty


Dlaczego suma ∑i=110i jest źle wyświetlana w wykładniku potęgi?

z∑i=110i



Zadanie 1.

<script type="text/javascript" src="common.js"></script> <script type="text/javascript" src="libot_drag.js"></script>

<img alt="Ikona obiektu Pytanie"

class="iDevice_icon" src="icon_question.gif" /> Zadanie 1,

Liczba Parser nie mógł rozpoznać (błąd składni): {\displaystyle <msqrt><mrow><mn>3</mn> <mo class="MathClass-bin">+</mo> <mn>2</mn><msqrt><mrow> <mn>2</mn></mrow></msqrt></mrow></msqrt> <mo class="MathClass-bin">&minus;</mo><msqrt><mrow><mn>3</mn> <mo class="MathClass-bin">&minus;</mo> <mn>2</mn><msqrt><mrow> <mn>2</mn></mrow></msqrt></mrow></msqrt>}   

<tbody> </tbody>
<input type="checkbox" name="option9" id="ia0b9"

value="vTrue"

onclick="document.getElementById('sa0b9').style.display = this.checked ? 'block' : 'none';" />		 jest dodatnia
<input type="checkbox" name="option9" id="ia1b9"

value="vTrue"

onclick="document.getElementById('sa1b9').style.display = this.checked ? 'block' : 'none';" />		 jest wymierna
<input type="checkbox" name="option9" id="ia2b9"

value="vFalse"

onclick="document.getElementById('sa2b9').style.display = this.checked ? 'block' : 'none';" />		 nale»y do trójkowego zbioru Cantora.
<a href="index.xml">« previous</a> | <a href="zadanie_2.xml">next »</a>
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Test_Arka&oldid=79852”