863 lines
40 KiB
Plaintext
863 lines
40 KiB
Plaintext
CHRISTIAN-ALBRECHTS-UNIVERSITÄT ZU KIEL
|
||
Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität
|
||
Prof. Dr. K. Jansen
|
||
|
||
19. Juli 2024
|
||
|
||
Modulprüfung zur Vorlesung
|
||
»Analyse von Algorithmen und Komplexität (Komplexitätsteil)«
|
||
SS 2024
|
||
Name: Matrikel-Nr.:
|
||
|
||
|
||
Hinweise:
|
||
|
||
• Bearbeiten Sie alle Aufgaben.
|
||
• Sie haben 10 Minuten Einlesezeit. Danach haben Sie 120 Minuten Zeit für die Klausurbearbeitung.
|
||
• Erlaubte Hilfsmittel: Ein doppelseitig handschriftlich beschriebenes Blatt Papier, (bunte) Stifte (kein
|
||
Rot, kein Grün, kein Bleistift).
|
||
• Einsichtnahme: 18.08.2024.
|
||
Note 4,0 3,7 3,3 3,0 2,7 2,3 2,0 1,7 1,3 1,0
|
||
•
|
||
Mindestpunkzahl 17,5 19,5 21,5 23,5 25 27 29 31 33 35
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 1 von 12
|
||
Aufgabe 1 KOMPLEXITÄT: ANWENDUNG LPT (4+2+2+2 Punkte)
|
||
Gegeben ist folgende Scheduling Instanz:
|
||
Jj J1 J2 J3 J4 J5 J6 J7
|
||
m=3
|
||
pj 5 3 7 8 1 4 2
|
||
|
||
a) Wenden Sie den LPT-Scheduling Algorithmus auf die obige Instanz an. Geben Sie dafür alle
|
||
relevanten Zwischenschritte an, sowie die Reihenfolge in der die Jobs auf Maschinen platziert
|
||
werden. Stellen Sie den resultierende Schedule graphisch dar. Eine beispielhafte Darstellung
|
||
ist:
|
||
|
||
J3
|
||
J6
|
||
J2
|
||
J5 J7
|
||
J1
|
||
J4
|
||
m1 m2 m3
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 2 von 12
|
||
b) Geben Sie die approximative Güte des Algorithmus LPT an.
|
||
|
||
|
||
|
||
|
||
c) Geben Sie eine Instanz für m = 2 Maschinen an, bei denen der Algorithmus ListScheduling
|
||
eine Güte von 2 − 1/m erzielt. Geben Sie zusätzlich an, welche Werte die optimale Lösung
|
||
OPT und die Lösung von LPT für diese Instanz erzielen.
|
||
|
||
|
||
|
||
|
||
d) Geben Sie eine Instanz für m = 3 Maschinen an, bei denen der Algorithmus ListScheduling
|
||
eine Güte von 2 − 1/m erzielt. Geben Sie zusätzlich an, welche Werte die optimale Lösung
|
||
OPT und die Lösung von LPT für diese Instanz erzielen.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 3 von 12
|
||
Aufgabe 2 KOMPLEXITÄT: BEWEIS : K -CLIQUE (10 Punkte)
|
||
Beweisen Sie folgende Aussage aus der Vorlesung:
|
||
SAT ≤ k-Clique.
|
||
Hinweis: NICHT 3-SAT, sondern allgemeines SAT!
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 4 von 12
|
||
Aufgabe 3 KOMPLEXITÄT: NP-VOLLSTÄNDIGKEIT (5+5 Punkte) a)
|
||
Wir betrachten folgendes Problem:
|
||
Problem: CliqueAndIndependetSet
|
||
Eingabe: Ein ungerichteter Graph G = (V, E) mit V = 1, . . . , |V | und eine ganze Zahl k ≥ 1.
|
||
Entscheide: Gibt es in G sowohl ein Independent Set (Menge von Knoten, die paarweise
|
||
nicht adjazent sind, d.h. zwischen denen es keine Kanten gibt) der Größe k und als auch eine
|
||
Clique der Größe k?
|
||
Zeigen Sie die NP-Schwere von CliqueAndIndependetSet durch Angabe einer Reduktion
|
||
eines nach Vorlesung/Übung bekanntermaßen NP-schweren Problems.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 5 von 12
|
||
b) Wir betrachten folgendes Problem:
|
||
Problem: (a1 = 1)-SubsetSum
|
||
Eingabe: Eine Menge von n Items, jedes Item i ∈ [n] hat eine Größe ai ∈ N>0 , wobei a1 = 1,
|
||
und ein Zielwert T .
|
||
Entscheide: Gibt es I ⊆ [n] sodass ∑i∈I ai = T ?
|
||
Zeigen Sie die NP-Schwere von (a1 = 1)-SubsetSum durch Angabe einer Reduktion eines
|
||
nach Vorlesung/Übung bekanntermaßen NP-schweren Problems.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 6 von 12
|
||
Aufgabe 4 KOMPLEXITÄT: APPROXIMATIVE ALGORITHMEN (3+7 Punkte)
|
||
Wir betrachten folgendes Problem:
|
||
Problem: APPROXIMATE SUBSET SUM
|
||
Eingabe: n ganze Zahlen a1 , . . . an und ein Zielwert T . Es gilt ai ≤ T ∀i ∈ [n] sowie ∑i∈[n] ai >
|
||
T.
|
||
Ziel: Wähle Zahlenmenge S ⊆ {1, . . . n} mit ∑ j∈S a j ≤ T und maximiere ∑ j∈S a j .
|
||
|
||
Betrachten Sie zu diesem Problem den folgenden Algorithmus GA.
|
||
|
||
Algorithmus GA((A,T))
|
||
|
||
1 sortiere Zahlen absteigend, sodass a1 ≥ a2 ≥ · · · ≥ an gilt;
|
||
2 integer i = 1;
|
||
3 integer sum = 0;
|
||
4 boolean tooLarge = false;
|
||
5 while i ≤ n and tooLarge = false do
|
||
6 if sum+ai ≤ T then
|
||
7 sum=sum+ai ;
|
||
8 i = i + 1;
|
||
9 else
|
||
10 tooLarge = true;
|
||
11 fi
|
||
12 od
|
||
13 return sum;
|
||
|
||
a) Geben Sie eine Konstruktionsvorschrift für eine Instanz I an, mit der der Algorithmus GA
|
||
beliebig nah an eine Güte von 2 kommt, also A(I) ≈ OPT2 (I) .
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 7 von 12
|
||
b) Zeigen Sie, dass der Algorithmus GA eine approximative Güte von 2 hat, also A(I) ≥ OPT2 (I)
|
||
gilt.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 8 von 12
|
||
Aufgabe 5 KOMPLEXITÄT: ETH (5+5 Punkte)
|
||
|
||
a) Betrachten Sie nachfolgende Reduktion von 3-SAT auf k-Color:
|
||
1. Eliminiere doppelte Klauseln und Variablen, die in keiner Klausel auftauchen
|
||
2. Elimiere Klauseln die eine Variable und ihre Negation enthalten (diese sind immer erfüllt)
|
||
3. Seien C1 , . . . ,Cm die Klauseln in der SAT Formel
|
||
4. Definiere
|
||
V := { xi , x̄i , vi | i ∈ [n] } ∪ C j j ∈ [m] ∪ {z} ,
|
||
sowie
|
||
|
||
E := {vi , v j }, {vi , x j }, {vi , x̄ j } i ∈ [n], j ∈ [n] \ {i}
|
||
∪ { {xi , x̄i } | i ∈ [n] }
|
||
|
||
∪ {xi ,C j } i ∈ [n], j ∈ [m], xi ∈ / Cj
|
||
|
||
∪ {x̄i ,C j } i ∈ [n], j ∈ [m], x̄i ∈ / Cj
|
||
∪ { {vi , z} | i ∈ [n] }
|
||
|
||
∪ {C j , z} j ∈ [m]
|
||
Welche Lower Bounds ergeben sich unter Annahme der ETH for k-Colour aus dieser Re-
|
||
duktion in Hinblick auf
|
||
(i) die Anzahl der Knoten |V |; sowie
|
||
(ii) die Anzahl der Kanten |E|?
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 9 von 12
|
||
b) Wir betrachten folgendes Scheduling Problem:
|
||
Problem: 2|prec, pi ∈ {1, 2}|Cmax
|
||
Eingabe: Eine Menge J von n Jobs, jeder Job J ∈ J hat eine Ausführungszeit pJ ∈ {1, 2}
|
||
sowie Präzedenzconstraints in Form eines gerichteten, azyklischem Graphen G = (J , A),
|
||
sowie ein ganze Zahl T ≥ 0.
|
||
Entscheide: Existiert ein Schedule, d.h. eine Abbildung, die jedem Job eine Startzeit und
|
||
eine Maschine zuweist, sodass (a) sich Jobs auf einer Maschine nicht überlappen (b) für alle
|
||
Jobs j, k ∈ J mit ( j, k) ∈ A, dass k erst startet nachdem j vollständig abgearbeitet ist und
|
||
(c) der Makespan höchstens T ist?
|
||
Wir betrachten die folgende Reduktion von k-Clique auf 2|prec, pi ∈ {1, 2}|Cmax .
|
||
Seien G = (V, E) und k gegeben. Wir setzen n = 4|V | + 3|E| und erstellen einen Knoten-Job Ji
|
||
für alle i ∈ V mit pi = 1. Des Weiteren erstellen wir Kanten-Jobs J{i, j} für jede Kante {i, j} ∈ E
|
||
mit p{i, j} = 2. Abschließend erstellen wir noch 3|V | + 2|E| Dummy Jobs. Diese Jobs haben
|
||
Ausführungszeit pdummy = 1.
|
||
Wir setzen unsere Präzedenzen nach dem folgenden Schema:
|
||
1) (Ji , J{i, j} ) für alle i ∈ V, {i, j} ∈ E
|
||
2) Präzedenzen innerhalb der Dummy Jobs.
|
||
Zuletzt setzen wir den Makespan T = 2|V | + 2|E|.
|
||
(i) Geben Sie die Lower Bounds für 2|prec, pi ∈ {1, 2}|Cmax in Hinblick auf n an, die sich
|
||
unter der ETH aus dieser Reduktion, basierend auf den Lower Bounds für k-Clique,
|
||
ergeben.
|
||
(ii) Geben Sie die Lower Bounds für 2|prec, pi ∈ {1, 2}|Cmax in Hinblick auf T an, die sich
|
||
unter der ETH aus dieser Reduktion, basierend auf den Lower Bounds für k-Clique,
|
||
ergeben.
|
||
Hinweis: Ein beispielhafter Schedule ist unten dargestellt. Die Präzedenzen sind im Graphen
|
||
durch gerichtete Kanten abgebildet, daher startet J4 erst nach dem Ende von J1 . Nutzen Sie
|
||
für diese Aufgabe die bekannten Lower Bounds aus der Präsenzübung. Diese wurden aus der
|
||
Reduktion von 3-SAT auf k-Clique hergeleitet. Hierbei ist der Clique Graph zusammenhän-
|
||
gend!
|
||
|
||
J3
|
||
|
||
J1
|
||
J3 J4
|
||
J4
|
||
|
||
J1 J2
|
||
J2
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 10 von 12
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 11 von 12
|
||
Aufgabe 6 BONUSAUFGABE (10 Punkte)
|
||
Beweisen oder widerlegen Sie folgende Aussage:
|
||
Wenn die ETH fehlschlägt gilt P = NP.
|
||
|
||
|
||
|
||
|
||
Viel Erfolg!
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 12 von 12
|
||
CHRISTIAN-ALBRECHTS-UNIVERSITÄT ZU KIEL
|
||
Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität
|
||
Prof. Dr. K. Jansen
|
||
|
||
11. Oktober 2024
|
||
|
||
Modulprüfung zur Vorlesung
|
||
»Analyse von Algorithmen und Komplexität (Komplexitätsteil)«
|
||
SS 2024
|
||
Name: Matrikel-Nr.:
|
||
Hinweise:
|
||
|
||
• Bearbeiten Sie alle Aufgaben.
|
||
• Sie haben 10 Minuten Einlesezeit. Danach haben Sie 120 Minuten Zeit für die Klausurbearbeitung.
|
||
• Erlaubte Hilfsmittel: Ein doppelseitig handschriftlich beschriebenes Blatt Papier, (bunte) Stifte (kein
|
||
Rot, kein Grün, kein Bleistift).
|
||
• Einsichtnahme: 30.10.2024
|
||
Note 4,0 3,7 3,3 3,0 2,7 2,3 2,0 1,7 1,3 1,0
|
||
•
|
||
Mindestpunktzahl 17,5 19,5 21,5 23,5 25 27 29 31 33 35
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 1 von 16
|
||
Aufgabe 1 ∆TSP1 (6+2+2 Punkte)
|
||
Gegeben sei folgender Graph G = (V, E), bei dem die Kantengewichte jeweils an der nach außen
|
||
gerichteten Seite der Kante stehen:
|
||
|
||
a
|
||
4 2
|
||
|
||
3
|
||
e b
|
||
4 2
|
||
|
||
4 3
|
||
6 5
|
||
|
||
d c
|
||
2
|
||
|
||
a) Wenden Sie den Algorithmus ∆TSP1 auf den Graphen G beginnend bei a an. Geben Sie dabei
|
||
die Ergebnisse jedes Zwischenschrittes des Algorithmus an.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 2 von 16
|
||
b) Beschreiben Sie, was der Algorithmus ∆TSP1 berechnet und geben Sie die Bedingungen an,
|
||
die an den Graphen gestellt sind, damit der Algorithmus eine korrekte Lösung berechnet.
|
||
|
||
|
||
|
||
|
||
c) Begründen Sie, warum der Algorithmus ∆TSP1 eine approximative Güte von 2 besitzt.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 3 von 16
|
||
Aufgabe 2 KOMPLEXITÄT: VORLESUNGSBEWEIS SAT (10 Punkte)
|
||
Beweisen Sie folgende Aussage:
|
||
3-SAT ist NP-vollständig. Zeigen Sie dafür SAT ≤ 3-SAT, nehmen Sie also 3-SAT ∈ NP als
|
||
gegeben an.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 4 von 16
|
||
Aufgabe 3 KOMPLEXITÄT: NP-VOLLSTÄNDIGKEIT (5+5 Punkte)
|
||
|
||
a) Wir betrachten folgendes Problem:
|
||
Problem: Hitchhiker’s-HamiltonianCycle
|
||
Eingabe: Ein ungerichteter Graph G = (V, E) mit V = {1, . . . , |V |} und für alle v ∈ V gilt
|
||
deg(v) ≥ 42.
|
||
Entscheide: Gibt es einen Hamiltonkreis in G?
|
||
Beweisen Sie die NP-Schwere von Hitchhiker’s-HamiltonianCycle durch Angabe einer
|
||
Reduktion eines nach Vorlesung/Übung bekanntermaßen NP-schweren Problems.
|
||
Hinweis: Als Hilfe, geben Sie graphisch die Reduktion für Knotengrad ≥ 10 an.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 5 von 16
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 6 von 16
|
||
b) Wir betrachten folgendes Problem:
|
||
Problem: AtMostTwoPerSize-SubsetSum
|
||
Eingabe: Ein ganzzahliger Zielwert T > 0, eine Menge von n Items, jedes Item i ∈ [n]
|
||
hat eine Größe ai ∈ N>0 , jede Größe tritt höchstens zwei Mal auf, d.h. für alle i ∈ [n] gilt
|
||
| { i′ ∈ [n] | ai′ = ai } | ≤ 2.
|
||
Entscheide: Gibt es S ⊆ [n] sodass ∑i∈S ai = T ?
|
||
Beweisen Sie die NP-Schwere von AtMostTwoPerSize-SubsetSum durch Angabe einer Re-
|
||
duktion eines nach Vorlesung/Übung bekanntermaßen NP-schweren Problems.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 7 von 16
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 8 von 16
|
||
Aufgabe 4 KOMPLEXITÄT: APPROXIMATIVE ALGORITHMEN (10+(10) Punkte)
|
||
Wir betrachten das aus der Vorlesung bekannte Makespan Scheduling Problem P||Cmax . Dazu ist
|
||
folgender Algorithmus gegeben:
|
||
|
||
Algorithmus ROUND ROBIN SCHEDULING(I=(J,m))
|
||
|
||
1 sortiere die Jobs in J so, dass p1 ≥ p2 ≥ · · · ≥ pn gilt;
|
||
2 setze B1 = · · · = Bm = 0;
|
||
/
|
||
3 integer j = 1;
|
||
4 integer i = 1;
|
||
5 while j <= n do
|
||
6 Platziere Job J j auf Maschine Mi ;
|
||
7 Bi = Bi ∪ {J j };
|
||
8 j = j + 1;
|
||
9 if i < m then
|
||
10 i=i+1
|
||
11 else
|
||
12 i=1
|
||
13 fi
|
||
14 od
|
||
15 return B1 , . . . , Bm
|
||
|
||
Betrachten Sie folgendes Beispiel zu der Funktionsweise des Round Robin Scheduling Algorith-
|
||
mus’. Gegeben sind 3 Maschinen und 6 Jobs J1 , . . . J6 , die bereits richtig sortiert sind. Es gilt
|
||
p1 = 7, p2 = 5, p3 = 5, p4 = 4, p5 = 3, p6 = 1. Daraus ergibt sich folgender Schedule:
|
||
|
||
|
||
|
||
|
||
J4
|
||
|
||
J5
|
||
J6
|
||
|
||
J1
|
||
J2 J3
|
||
|
||
|
||
m1 m2 m3
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 9 von 16
|
||
a) Zeigen Sie per Widerspruch, dass der Algorithmus Round Robin Scheduling eine approxima-
|
||
tive Güte von 2 hat.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 10 von 16
|
||
b) BONUS: Geben Sie die Konstruktionsvorschrift für eine Instanz an, mit der der Algorithmus
|
||
Round Robin Scheduling beliebig nah an eine Güte von 2 kommt, also A(I) ≈ 2 · OPT (I).
|
||
Nutzen Sie dafür mindestens 3 Maschinen und 7 Jobs, womit eine Rate von A(I) = 53 OPT
|
||
zu erreichen ist. Geben sie die optimale Makespan an und die, die der Algorithmus bei Ihrer
|
||
Instanz erreicht. Für eine Güte von 53 können bis zu 3 Punkten erreicht werden, bei einer
|
||
Güte von 47 sind bis zu 5 Punkte zu erreichen. Geben Sie eine Konstruktionsvorschrift an,
|
||
bei denen bei einer beliebigen, festen Anzahl von Maschinen m eine Güte von 2 − m1 erreicht
|
||
wird, können Sie die vollen 10 Punkte erreichen.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 11 von 16
|
||
Aufgabe 5 KOMPLEXITÄT: ETH (5+5 Punkte)
|
||
|
||
a) Wir betrachten folgendes Problem:
|
||
Problem: DominatingSet
|
||
Eingabe: Ein ungerichteter Graph G = (V, E) mit V = 1, . . . , |V | und eine Ganzzahl k ≥ 1.
|
||
Entscheide: Gibt es eine Menge M ⊆ V der Kardinalität |M| = k derart, dass jeder Knoten
|
||
v ∈ V entweder in M ist oder zu einem Knoten in M benachbart ist.
|
||
Wir untersuchen nun folgende Reduktion von 3-SAT auf DominatingSet:
|
||
1. Seien C1 , . . . ,Cm die Klauseln der 3-SAT-Formel
|
||
2. Seien x1 , . . . , xn die Variablen der 3-SAT-Formel
|
||
3. Erzeuge die Knoten xi , xi und di für jede Variable xi
|
||
4. Erzeuge die Kanten {xi , xi }, {xi , di } und {di xi } für jede Variable xi
|
||
5. Für jede Klausel C j erzeuge einen Knoten C j
|
||
6. Für jedes Literal ℓ einer Klausel C j erzeuge die Kanten {C j , ℓ}
|
||
Welche unteren Schranken für die Laufzeit folgen damit für DominatingSet unter der ETH
|
||
in Bezug auf
|
||
(i) die Anzahl der Knoten |V |?
|
||
(ii) die Anzahl der Kanten |E|?
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 12 von 16
|
||
b) Wir betrachten folgendes Problem:
|
||
Problem: GridTiling
|
||
Eingabe: Zwei ganze Zahlen k und j und für jedes i ∈ [k] und j ∈ [k] eine Menge Si, j ⊆ [n]2 .
|
||
Entscheide: Gibt es (ei, j )(i, j)∈[k]2 derart, dass
|
||
1. für alle (i, j) ∈ [k]2 gilt ei, j ∈ Si, j ;
|
||
2. für alle i ∈ [k] und j ∈ [k − 1] gilt für ei, j = (a, b) und ei, j+1 = (a′ , b′ ), dass a = a′ (dh. die
|
||
ausgewählten Tupel müssen in der ersten Komponente übereinstimmen, wenn der erste
|
||
Index derselbe ist); und
|
||
3. für alle i ∈ [k − 1] und j ∈ [k] gilt für ei, j = (a, b) und ei+1, j = (a′ , b′ ), dass b = b′ (dh.
|
||
die ausgewählten Tupel müssen in der zweiten Komponente übereinstimmen, wenn der
|
||
zweite Index derselbe ist)
|
||
Betrachten Sie folgende Beispielinstanz für k = 2, die Elemente der Lösung sind unterstrichen:
|
||
|
||
|
||
S1,1 = {(1, 1), (2, 2)} S1,2 = {(1, 2), (2, 1), (2, 2)}
|
||
|
||
|
||
|
||
S2,1 = {(1, 2), (2, 1)} S2,2 = {(1, 1), (2, 2)}
|
||
|
||
|
||
Wir untersuchen folgende Reduktion von Clique:
|
||
1. Sei G = (V, E) und eine Zahl k als zu untersuchende Clique Instanz gegeben
|
||
2. Wir nehmen ohne Beschränkung der Allgemeinheit an, dass V = {1, . . . , |V |} sowie k ≥ 2
|
||
gilt und dass keine isolierten Knoten existieren.
|
||
3. Wir übernehmen den Wert von k
|
||
4. Für jedes Paar (i, j) ∈ [k]2 definieren wir
|
||
(
|
||
{ (a, a) | a ∈ V } if i = j
|
||
Si, j :=
|
||
{ (a, b) | a ̸= b, {a, b} ∈ E } if i ̸= j
|
||
Welche unteren Schranken für die Laufzeit folgen damit für Grid Tiling (mit der aus der
|
||
Vorlesung bekannten Reduktion von Clique auf 3-SAT) in Hinblick auf
|
||
(i) der Gesamtanzahl X := ∑(i, j)∈[k]2 |Si, j | der Tupel in den Mengen; sowie
|
||
(ii) der maximalen Anzahl Y := max(i, j)∈[k]2 |Si, j | an Tupeln in einer der Mengen?
|
||
Hinweis: Aus der Reduktion in der Vorlesung wissen wir, dass Clique selbst dann noch NP-
|
||
schwer ist, wenn k ∈ Θ(|V |) gilt. Sie dürfen also annehmen, dass es eine (globale) Konstante
|
||
c > 0 gibt, sodass c · n ≤ k ≤ n.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 13 von 16
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 14 von 16
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 15 von 16
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 16 von 16
|
||
CHRISTIAN-ALBRECHTS-UNIVERSITÄT ZU KIEL
|
||
Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität
|
||
Prof. Dr. K. Jansen
|
||
|
||
14. Juli 2023
|
||
|
||
Modulprüfung zur Vorlesung
|
||
»Analyse von Algorithmen und Komplexität (Komplexitätsteil)«
|
||
SS 2023
|
||
Name: Matrikel-Nr.:
|
||
|
||
|
||
Hinweise:
|
||
|
||
• Bearbeiten Sie alle Aufgaben.
|
||
• Sie haben 10 Minuten Einlesezeit. Danach haben Sie 120 Minuten Zeit für die Klausurbearbeitung.
|
||
• Erlaubte Hilfsmittel: Ein doppelseitig handschriftlich beschriebenes Blatt Papier, (bunte) Stifte (kein
|
||
Rot, kein Grün, kein Bleistift).
|
||
• Einsichtnahme: Nach Absprache.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 1 von 11
|
||
Aufgabe 1 RUCKSACKPROBLEM (3+2+5 Punkte)
|
||
Wir betrachten die Anwendung der Approximationsheuristiken für das Rucksackproblem aus der
|
||
Vorlesung.
|
||
Gegeben sei dafür folgende Instanz des Rucksackproblems mit Kapazität B = 16. Items sind in
|
||
der Form (pi , wi ) angegeben.
|
||
I = [(1, 4), (1, 1), (1, 3), (11, 13), (3, 3), (5, 6), (1, 5), 16]
|
||
a) Wenden Sie den normalen Greedy-Algorithmus auf obige Instanz an. Begründen Sie kurz,
|
||
warum die gewählten Items ausgewählt werden. Was ist der Lösungswert?
|
||
|
||
|
||
|
||
|
||
b) Wenden Sie nun den ModifiedGreedy-Algorithmus an. Wie ändert sich die Lösung?
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 2 von 11
|
||
c) Was ist die Güte des ModifiedGreedy-Algorithmus? Geben Sie eine kurze Idee an, wie man
|
||
diesen Ansatz modifizieren kann, um die Güte auf 32 oder 43 zu verbessern.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 3 von 11
|
||
Aufgabe 2 LONGEST PATH (3+3+4 Punkte)
|
||
Betrachten Sie das folgende Problem:
|
||
Problem: LONGEST PATH
|
||
Eingabe: Eine ungerichteter Graph G = (V, E) und eine Zahl k.
|
||
Entscheide: Gibt es einen Pfad in G, der mindestens Länge k hat?
|
||
|
||
Zeigen Sie auf verschiedene Weisen, dass das Problem in NP liegt:
|
||
|
||
a) Geben Sie ein Zertifikat für LONGEST PATH an.
|
||
b) Beschreiben Sie einen Verifizierer für LONGEST PATH und geben Sie dessen Laufzeit konkret
|
||
an.
|
||
c) Beschreiben Sie eine nicht-deterministische Turing-Maschine (in Worten), die LONGEST PATH
|
||
löst. Geben Sie auch hier die Laufzeit konkret an.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 4 von 11
|
||
Aufgabe 3 APPROXIMATIVE ALGORITHMEN (6+4 Punkte)
|
||
Das Problem MAX -3-SAT sei folgendermaßen definiert:
|
||
Problem: MAX -3-SAT
|
||
Eingabe: Eine Formel φ in konjunktiver Normalform, wobei jede Klausel drei Literale enthält.
|
||
Ausgabe: Eine Belegung β der Variablen, die die Anzahl v(β ) der erfüllten Klauseln maximiert.
|
||
|
||
Betrachten Sie folgenden Algorithmus A:
|
||
|
||
• Sei β0 die Belegung, die alle Variablen auf false setzt.
|
||
• Sei β1 die Belegung, die alle Variablen auf true setzt.
|
||
• Falls v(β0 ) ≥ v(β1 ), gib β0 zurück.
|
||
• Sonst gib β1 zurück.
|
||
|
||
a) Zeigen Sie, dass obiger Algorithmus Güte 2 hat, d.h. A(φ ) ≥ 12 OPT (φ ) gilt für alle Eingaben
|
||
φ.
|
||
b) Geben Sie eine Formel an, bei der der Algorithmus eine Belegung ausgibt, die genau die Hälfte
|
||
der maximal erfüllbaren Klauseln erfüllt. Begründen Sie kurz, warum Ihre Formel geeignet ist.
|
||
Hinweis: Sie brauchen nur höchstens zwei Klauseln und sechs Variablen.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 5 von 11
|
||
Aufgabe 4 BEWEIS ZUR VORLESUNG (10 Punkte)
|
||
Betrachten Sie folgendes Problem aus der Vorlesung:
|
||
|
||
Problem: k-CLIQUE
|
||
Eingabe: Ein ungerichteter Graph G = (V, E) und eine Zahl k ≥ 1. Eine Clique ist eine Teil-
|
||
menge C ⊆ V mit {u, v} ∈ E für alle u, v ∈ C mit u ̸= v.
|
||
Entscheide: Hat der gegebene Graph G eine Clique C ⊆ V mit mindestens k Knoten (d.h. mit
|
||
|C| ≥ k)?
|
||
|
||
Beweisen Sie: Das Problem k-CLIQUE ist NP-vollständig.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 6 von 11
|
||
Aufgabe 5 NP UND NP-VOLLSTÄNDIGKEIT (4+4+7 Punkte)
|
||
|
||
|
||
a) Beweisen Sie die NP-Vollständigkeit von SUBSET SUM, bei der jede Itemgröße jeweils durch
|
||
3 oder durch 7 teilbar ist.
|
||
b) Beweisen Sie die NP-Vollständigkeit von 3-COLOR, wobei jeder Knoten im Graph mindes-
|
||
tens Grad 3 hat.
|
||
c) Zeigen Sie: Für kein α > 1 gibt es einen approximativen Algorithmus mit Güte α (d.h. mit
|
||
Zielfunktionswert ≤ α · OPT) für TSP, außer P = NP (Denken Sie an Wiliam Rowan Hamil-
|
||
ton).
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 7 von 11
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 8 von 11
|
||
Aufgabe 6 UNTERE SCHRANKEN UND ETH (7+8 Punkte)
|
||
Betrachten Sie folgende Reduktionen:
|
||
Problem: HITTING SET
|
||
Eingabe: Eine Menge U sowie r Teilmengen F1 , . . . , Fr ⊆ U und eine Zahl k.
|
||
Entscheide: Gibt es eine Menge S ⊆ U mit |S| ≤ k und S ∩ Fi ̸= 0/ für alle i ∈ [r]?
|
||
|
||
a) 3-SAT ⪯ HITTING SET: Seien v1 , . . . , vn die Variablen der Formel und C1 , . . . ,Cm die Klau-
|
||
seln. Setze U = { v1 , v1 , . . . , vn , vn } und k = n. Für jede Variable vi definiere eine Menge
|
||
Fi = {vi , vi } und für jede Klausel C j definiere eine Menge Fn+ j = C j
|
||
Welche unteren Schranken ergeben sich durch obige Reduktion für die Laufzeit von Algorith-
|
||
men für HITTING SET unter Annahme der ETH in Abhängigkeit von
|
||
(i) r?
|
||
(ii) |U|?
|
||
Beweisen Sie die entsprechenden unteren Schranken!
|
||
Hinweis: Sie dürfen – wie in den Hausaufgaben zur ETH – Faktoren, die polynomiell in der
|
||
Eingabekodierung sind, vernachlässigen.
|
||
b) 3-SAT ⪯ SUBSET SUM: Seien v1 , . . . , vn die Variablen der Formel und C1 , . . . ,Cm die Klauseln.
|
||
Für jede Variable vi erzeuge zwei Items ai und bi , mit den Größen
|
||
|
||
s(ai ) = 10i−1 + ∑ 10n+ j−1 und s(bi ) = 10i−1 + ∑ 10n+ j−1 .
|
||
j∈[m] j∈[m]
|
||
xi ∈C j xi ∈C j
|
||
|
||
Zusätzlich erzeuge zwei Items c j und d j für jede Klausel C j mit Größen
|
||
|
||
s(c j ) = s(d j ) = 10n+ j−1 .
|
||
|
||
Der Zielwert sei
|
||
B = ∑ 3 · 10n+ j−1 + ∑ 10i−1 .
|
||
|
||
j∈[m] i∈[n]
|
||
|
||
Welche unteren Schranken ergeben sich durch obige Reduktion für die Laufzeit von Algorith-
|
||
men für SUBSET SUM unter Annahme der ETH in Abhängigkeit von
|
||
(i) der Anzahl der unterschiedlichen Itemgrößen d?
|
||
(ii) der binären Kodierungslänge L der größten Itemgröße ∆ (d.h. L = log(∆))?
|
||
Beweisen Sie die entsprechenden unteren Schranken!
|
||
Hinweis: Sie dürfen auch hier – wie in den Hausaufgaben zur ETH – Faktoren, die polynomiell
|
||
in der Eingabekodierung sind, vernachlässigen.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 9 von 11
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 10 von 11
|
||
Viel Erfolg!
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 11 von 11
|
||
CHRISTIAN-ALBRECHTS-UNIVERSITÄT ZU KIEL
|
||
Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität
|
||
Prof. Dr. K. Jansen
|
||
|
||
19. Oktober 2023
|
||
|
||
Modulprüfung zur Vorlesung
|
||
»Analyse von Algorithmen und Komplexität (Komplexitätsteil)«
|
||
SS 2023
|
||
Name: Matrikel-Nr.:
|
||
|
||
|
||
Hinweise:
|
||
|
||
• Bearbeiten Sie alle Aufgaben.
|
||
• Sie haben 120 Minuten Zeit für die Klausurbearbeitung.
|
||
• Erlaubte Hilfsmittel: Ein einseitig handschriftlich beschriebenes Blatt Papier, (bunte) Stifte (kein Rot,
|
||
kein Grün, kein Bleistift, kein Tintenkiller, kein Tipp-Ex).
|
||
• Schreiben Sie auf jedes Blatt ihren Namen.
|
||
• Wenn Sie Schmierzettel verwenden um eine Aufgabe zu bearbeiten, verweisen Sie in der Aufgabe auf
|
||
diese.
|
||
• Einsichtnahme: 2.11.23, 13:30-14:30 Uhr.
|
||
• Die Klausur hat 6 Aufgaben auf 13 Seiten – überprüfen Sie bitte vor der Bearbeitung, dass Ihre Klausur
|
||
vollständig ist.
|
||
Aufgabe 1 CHRISTOFIDES ’ ALGORITHMUS (3+7 Punkte)
|
||
Gegeben sei folgender Graph G = (V, E) :
|
||
|
||
d
|
||
|
||
2
|
||
3
|
||
|
||
3
|
||
a c
|
||
|
||
|
||
1
|
||
2
|
||
|
||
b
|
||
|
||
a) Geben Sie an, was Christofides’ Algorithmus berechnet, und welche approximative Güte er
|
||
hat. Welche Eigenschaft müssen die Distanzen neben der Symmetrie noch erfüllen, damit
|
||
Christofides’ Algorithmus korrekt arbeitet.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 1 von 19
|
||
b) Wenden Sie den Algorithmus von Christofides auf den Graphen G mit Startknoten a an. Ge-
|
||
ben Sie dabei alle Graphen an, die in Zwischenschritten entstehen. Erwähnen Sie ebenfalls
|
||
Schritte, die bei dieser Anwendung zu keiner Änderung führen, die der Algorithmus aber
|
||
überprüfen muss.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 2 von 19
|
||
Aufgabe 2 DOMINATING SET (3+3+4 Punkte)
|
||
Betrachten Sie das folgende Problem:
|
||
Problem: DOMINATING SET
|
||
Eingabe: Ein ungerichteter Graph G = (V, E) (wobei V = {1, . . . , n} für eine Zahl n ∈ N≥1 )
|
||
und eine Zahl k ∈ N0 .
|
||
Entscheide: Gibt es eine Teilmenge D ⊆ V der Knoten mit |D| ≤ k, sodass jeder Knoten v ∈ V
|
||
in D enthalten ist oder benachbart zu mindestens einem der Knoten in D ist?
|
||
|
||
Zeigen Sie auf verschiedene Weisen, dass das Problem in NP liegt:
|
||
a) Geben Sie ein Zertifikat für DOMINATING SET an.
|
||
b) Beschreiben Sie einen polynomiellen Verifizierer für DOMINATING SET und schätzen Sie die
|
||
Laufzeit in O-Notation konkret ab.
|
||
c) Beschreiben Sie (in Worten) eine polynomielle, nicht-deterministische Turing-Maschine, die
|
||
DOMINATING SET löst. Schätzen Sie auch hier die Laufzeit in O-Notation konkret ab.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 3 von 19
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 4 von 19
|
||
Aufgabe 3 APPROXIMATIVE ALGORITHMEN (6+4 Punkte)
|
||
Das Problem MIN -EDGE -COVER sei folgendermaßen definiert:
|
||
Problem: MIN -EDGE -COVER
|
||
Eingabe: Ein zusammenhängender, ungerichteter Graph G = (V, E).
|
||
Ausgabe: Eine Teilmenge der Kanten C ⊆ E mit minimaler Kardinalität, sodass jeder Knoten
|
||
v ∈ V zu mindestens einer Kante aus C inzident ist.
|
||
|
||
Betrachten Sie folgenden Algorithmus A:
|
||
|
||
• Gehe (in beliebiger Reihenfolge) alle Knoten durch:
|
||
• Falls der aktuelle Knoten v noch nicht abgedeckt ist, wähle zufällig eine der zu v inzidenten
|
||
Kanten und füge sie zu C hinzu.
|
||
• Gib anschließend die entstehende Menge C zurück.
|
||
|
||
a) Zeigen Sie, dass obiger Algorithmus Güte 2 hat, d.h. A(G) ≤ 2 · OPT(G) gilt für alle Eingaben
|
||
G.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 5 von 19
|
||
b) Sei n ∈ N≥4 gerade. Betrachten Sie den Graphen Gn , der genau n Knoten und n Kanten hat und
|
||
einen Kreis beschreibt. D.h. Gn = ({1, . . . , n}, {{i, i+1} | i ∈ {1, . . . , n−1}}∪{{n, 1}}). Wie viele
|
||
Kanten hat ein MIN -EDGE -COVER des Graphen Gn ? Wie schlecht ist die Approximationsrate
|
||
des Algorithmus A für Gn im schlimmsten Fall? Geben Sie eine Reihenfolge der Knoten (für
|
||
Schritt 1) und eine Auswahl der Kanten (für Schritt 2) an, die zu einer möglichst schlechten
|
||
Approximationsrate führen.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 6 von 19
|
||
Aufgabe 4 BEWEIS – SCHEDULING AUF IDENTISCHEN MASCHINEN (10 Punkte)
|
||
Betrachten Sie das Scheduling-Problem P||Cmax :
|
||
Problem: P||Cmax
|
||
Eingabe: Eine Liste L = (J1 , . . . , Jn ) von n Jobs mit Ausführungszeiten p1 , . . . , pn ∈ N, und m
|
||
identische Maschinen.
|
||
Ausgabe: Ein Schedule (Partition von J in m Teilmengen B1 , . . . , Bm ) mit minimaler maximaler
|
||
Last Cmax := max ∑ p j .
|
||
1≤i≤m J ∈B
|
||
j i
|
||
|
||
|
||
Betrachten Sie den folgenden Algorithmus ListScheduling, der einen Schedule berechnet. Sei
|
||
LS(I) die Last Cmax eines Schedules des Algorithmus, und OPT(I) die Last Cmax eines optimalen
|
||
Schedules zur Eingabe I. Zeigen Sie: Für alle Eingaben I = (L, m) gilt LS(I)/OPT(I) ≤ 2 − 1/m.
|
||
|
||
Algorithmus LIST SCHEDULING(L = (J1 , . . . , Jn ), m)
|
||
|
||
1 for i = 1 to m do
|
||
2 Ei = 0; Bi = 0/ ;
|
||
3 od
|
||
4 for j = 1 to n do
|
||
5 wähle Job J j aus Liste L;
|
||
6 wähle Maschine Mi mit minimaler Last Ei ;
|
||
7 Bi = Bi ∪ {J j };
|
||
8 Ei = Ei + p j ;
|
||
9 od
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 7 von 19
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 8 von 19
|
||
Aufgabe 5 NP UND NP-VOLLSTÄNDIGKEIT (4+5+6 Punkte)
|
||
|
||
Problem: HAMILTONIAN PATH
|
||
Eingabe: Ein ungerichteter Graph G = (V, E)
|
||
Entscheide: Existiert ein Pfad in G, der jeden Knoten genau einmal besucht?
|
||
Problem: HAMILTONIAN CYCLE
|
||
Eingabe: Ein ungerichteter Graph G = (V, E)
|
||
Entscheide: Existiert ein Kreis in G, der jeden Knoten genau einmal besucht?
|
||
|
||
(a) Sei L ⊆ SUBSET SUM die Menge der (positiven) SubsetSum-Instanzen, bei denen keine der
|
||
Itemgrößen eine Zweierpotenz ist. Zeigen Sie, dass L NP-vollständig ist.
|
||
(b) Geben Sie eine polynomielle Reduktion von HAMILTONIAN PATH auf HAMILTONIAN C Y-
|
||
CLE an.
|
||
|
||
(c) Geben Sie eine polynomielle Reduktion von HAMILTONIAN CYCLE auf HAMILTONIAN -
|
||
PATH an.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 9 von 19
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 10 von 19
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 11 von 19
|
||
Aufgabe 6 UNTERE SCHRANKEN UND ETH (5+5 Punkte)
|
||
Im Folgenden bezeichne ⟨I⟩ die Kodierungslänge der Instanz.
|
||
(a) Wir betrachten folgendes Problem:
|
||
Problem: HITTING SET
|
||
Eingabe: Eine Menge U ′ sowie r′ Teilmengen F1′ , . . . , Fr′′ ⊆ U ′ und eine Zahl k′ .
|
||
Entscheide: Gibt es eine Menge S′ ⊆ U ′ mit |S′ | ≤ k′ und S′ ∩ Fi′ ̸= 0/ für alle i′ ∈ {1, . . . , r′ }?
|
||
|
||
Sie dürfen nutzen, dass sich HITTING SET unter Annahme der ETH nicht in Zeit 2o(r ) ⟨I⟩O(1)
|
||
′
|
||
|
||
|
||
und nicht in Zeit 2o(|U |) ⟨I⟩O(1) lösen lässt.
|
||
′
|
||
|
||
|
||
Problem: SET COVER
|
||
Eingabe: Eine Menge U sowie r Teilmengen F1 , . . . , Fr ⊆ U und eine Zahl k.
|
||
Entscheide: Gibt es eine Menge S ⊆ {1, . . . , r} mit |S| ≤ k und i∈S Fi = U?
|
||
S
|
||
|
||
|
||
Welche unteren Schranken ergeben sich
|
||
(i) in Hinblick auf |U| sowie
|
||
(ii) in Hinblick auf r
|
||
für SET COVER unter Annahme der ETH aus den unteren Schranken für HITTING SET, wenn
|
||
man folgende Reduktion von SetCover auf HittingSet verwendet?
|
||
Sei (F ,U, k) eine SET COVER-Instanz. Setze V1 := U und V2 := {1, . . . , r}. Sei V := V1 ∪V˙ 2.
|
||
Weiter sei E = { {v, w} | v ∈ V1 , w ∈ V2 , v ∈ Fw }. Damit ist G = (V, E) ein bipartiter Graph
|
||
mit Partitionen V1 ,V2 . Setze U ′ := {1, . . . , r}. Erzeuge nun eine Menge Fw′ für jeden Knoten
|
||
w ∈ V1 , indem Fw′ := { v ∈ V2 | {v, w} ∈ E } gesetzt wird. Sei F ′ := { Fw′ | w ∈ V1 }. Mit k′ = k
|
||
iie berechnete Instanz ist nun durch (F ′ ,U ′ , k′ ) gegeben.
|
||
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 12 von 19
|
||
(b) Wir wollen uns mit einem Problem beschäftigen, das ein mächtiges Werkzeug im Bereich
|
||
der Optimierung ist: Integrale Lineare Programme (ILPs).
|
||
Problem: ILP-FEASIBILITY
|
||
Eingabe: Eine Matrix A ∈ ZM×N , eine rechte Seite b ∈ ZM .
|
||
Entscheide: Gibt es einen Vektor x ∈ ZN≥0 mit Ax ≤ b, d.h. Ai xi ≤ bi für alle i ∈ {1, . . . , M}?
|
||
Welche unteren Schranken ergeben sich
|
||
(i) in Hinblick auf M sowie
|
||
(ii) im Hinblick auf N
|
||
für ILP-FEASIBILITY unter Annahme der ETH, wenn man folgende Reduktion von 3-SAT
|
||
auf ILP-FEASIBILITY verwendet?
|
||
Sei φ eine 3-SAT Instanz mit m Klauseln (Ci )i∈m und n Variablen. Analog zu linearen Glei-
|
||
chungssystemen (Ax = b), die aus M Gleichungen bestehen, haben wir bei Ax ≤ b einen
|
||
Satz von M linearen Ungleichungen. Wir konstruieren diese wie folgt: Wir nutzen N := 2n
|
||
Variablen in unserem ILP, eine für jedes (mögliche) Literal in der SAT-Formel. Für je-
|
||
de SAT-Variable v sei xv die ILP-Variable, die zum SAT-Literal v korrespondiert, und xv̄
|
||
die, die zum SAT-Literal v̄ korrespondiert. Für jede Klausel Ci erzeugen wir eine Unglei-
|
||
chung − ∑ℓ∈Ci xℓ ≤ −1. Weiter erzeugen wir für jede SAT-Variable v zwei Ungleichungen:
|
||
xv +xv̄ ≤ 1 und −xv −xv̄ ≤ −1. Durch das Eintragen der entsprechenden Koeffizienten in eine
|
||
erweiterte Koeffizientenmatrix (bestehend aus Matrix A und rechter Seite b) erhalten wir die
|
||
ILP-FEASIBILITY Instanz.
|
||
|
||
|
||
|
||
|
||
Viel Erfolg!
|
||
|
||
|
||
|
||
Klausur »Analyse von Algorithmen und Komplexität (Komplexitätsteil)« Seite 13 von 19
|
||
|