\documentclass[11pt,a4paper]{article} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage[utf8]{inputenc} \usepackage[margin=2.5cm]{geometry} \usepackage{amsmath,amssymb} \usepackage{xcolor} \usepackage{tikz} \setlength{\parskip}{0.4em} \setlength{\parindent}{0pt} \emergencystretch=1.5em \definecolor{shadecolor}{gray}{0.94} % ---- graue Box fuer Pseudocode/Problem-Boxen (nur mit xcolor) ---- \makeatletter \newsavebox{\shadedbox} \newenvironment{shaded}% {\par\smallskip\noindent \begin{lrbox}{\shadedbox}% \begin{minipage}{\dimexpr\linewidth-2\fboxsep\relax}}% {\end{minipage}\end{lrbox}% \colorbox{shadecolor}{\usebox{\shadedbox}}\par\smallskip} \makeatother % ---- alphabetische Aufzaehlung a) b) c) ohne enumitem ---- \renewcommand{\theenumi}{\alph{enumi}} \renewcommand{\labelenumi}{\theenumi)} % ---- Makros ---- \newcommand{\problem}[1]{\textsc{#1}} \newcommand{\redp}{\le_p} \newcommand{\NP}{\textsf{NP}} \newcommand{\true}{\textsf{wahr}} \newcommand{\false}{\textsf{falsch}} \tikzset{knoten/.style={circle,draw,thick,minimum size=6.5mm,inner sep=1pt}} % ---- Aufgabenkopf ---- \newcommand{\aufgabe}[2]{\clearpage \noindent{\large\textbf{Aufgabe #1}}\hfill\textbf{(#2)}\par\nobreak \noindent\rule{\linewidth}{0.4pt}\par\medskip} \begin{document} % ================= Kopf ================= \begin{center} {\large\textbf{Christian-Albrechts-Universität zu Kiel}}\\[2pt] Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität\\ Prof.\ Dr.\ K.\ Jansen\\[10pt] {\large\textbf{Musterlösung -- Probeklausur 2}}\\[3pt] {\large\textbf{Analyse von Algorithmen und Komplexität}}\\[2pt] SS 2026 \end{center} % ====================================================================== \aufgabe{1 \quad ANWENDUNG -- LPT}{5 + 2 + 3 Punkte} \textbf{a)} \problem{LPT} sortiert die Jobs absteigend und wendet darauf \problem{ListScheduling} an; Lastvektor $(M_1, M_2, M_3)$, bei Gleichstand kleinster Index. \begin{itemize} \item Absteigend sortiert: $5,\ 5,\ 4,\ 4,\ 3,\ 3,\ 3$. \item $5 \to M_1$: $(5,0,0)$; \quad $5 \to M_2$: $(5,5,0)$; \quad $4 \to M_3$: $(5,5,4)$. \item $4 \to M_3$ (kleinste Last $4$): $(5,5,8)$. \item $3 \to M_1$ (kleinste Last $5$, Gleichstand $M_1,M_2$): $(8,5,8)$. \item $3 \to M_2$ (kleinste Last $5$): $(8,8,8)$. \item $3 \to M_1$ (kleinste Last $8$, Gleichstand, kleinster Index): $(11,8,8)$. \end{itemize} Belegung: $M_1 = \{5,3,3\}$ (Last $11$), $M_2 = \{5,3\}$ (Last $8$), $M_3 = \{4,4\}$ (Last $8$). Makespan $\mathrm{LPT} = C_{\max} = 11$. \begin{center} \begin{tikzpicture}[x=0.72cm,y=0.9cm] \draw[->] (0,-0.35) -- (12,-0.35) node[right]{$t$}; \foreach \t in {0,2,4,6,8,10} \draw (\t,-0.3)--(\t,-0.4) node[below,font=\scriptsize]{$\t$}; \draw (11,-0.3)--(11,-0.4) node[below,font=\scriptsize]{$11$}; \node[left] at (0,2.4) {$M_1$}; \draw[fill=black!12] (0,2) rectangle (5,2.8); \node at (2.5,2.4){$5$}; \draw[fill=black!20] (5,2) rectangle (8,2.8); \node at (6.5,2.4){$3$}; \draw[fill=black!12] (8,2) rectangle (11,2.8); \node at (9.5,2.4){$3$}; \node[left] at (0,1.4) {$M_2$}; \draw[fill=black!12] (0,1) rectangle (5,1.8); \node at (2.5,1.4){$5$}; \draw[fill=black!20] (5,1) rectangle (8,1.8); \node at (6.5,1.4){$3$}; \node[left] at (0,0.4) {$M_3$}; \draw[fill=black!12] (0,0) rectangle (4,0.8); \node at (2,0.4){$4$}; \draw[fill=black!20] (4,0) rectangle (8,0.8); \node at (6,0.4){$4$}; \draw[dashed] (11,-0.35)--(11,2.9); \node[right,font=\small] at (11.1,1.4){$C_{\max}=11$}; \end{tikzpicture} \end{center} \emph{Bemerkung:} Wegen $\sum_j p_j = 27 = 3 \cdot 9$ und der Aufteilung $\{5,4\},\{5,4\},\{3,3,3\}$ (Lasten $9,9,9$) ist $\mathrm{OPT} = 9$. \problem{LPT} ist hier also \emph{nicht} optimal: die Rate ist $\tfrac{11}{9}$. \textbf{b)} \problem{LPT} hat die approximative Güte \[ \frac{4}{3} - \frac{1}{3m}. \] Für $m = 3$ ergibt das $\frac43 - \frac19 = \frac{11}{9}$; die Instanz aus a) erreicht diese Schranke also exakt und ist ein worst-case-Beispiel. \textbf{c)} Instanz mit $m = 2$ und Jobs in der Reihenfolge $p = (1, 1, 2)$. \problem{ListScheduling} legt jeden Job auf die aktuell leerste Maschine (Lastvektor $(M_1, M_2)$): \begin{itemize} \item $1 \to M_1$: $(1,0)$;\quad $1 \to M_2$: $(1,1)$;\quad $2 \to M_1$ (Gleichstand, kleinster Index): $(3,1)$. \end{itemize} $\mathrm{LS} = 3$. Optimal ist $\{1,1\}$ auf einer Maschine und $\{2\}$ auf der anderen (Lasten $2,2$), also $\mathrm{OPT} = 2$. Die Rate ist $\frac{\mathrm{LS}}{\mathrm{OPT}} = \frac{3}{2} = 2 - \frac12 = 2 - \frac1m$. \hfill$\square$ % ====================================================================== \aufgabe{2 \quad VORLESUNGSBEWEIS -- TRANSITIVITÄT}{10 Punkte} Zu zeigen: Aus $L_1 \redp L_2$ und $L_2 \redp L_3$ folgt $L_1 \redp L_3$. \textbf{Voraussetzung.} Sei $R_1$ eine Polynomialzeitreduktion $L_1 \redp L_2$ mit Laufzeit $O(n^a)$ und $R_2$ eine Polynomialzeitreduktion $L_2 \redp L_3$ mit Laufzeit $O(n^b)$, wobei $a, b \ge 1$ konstant sind. Nach Definition gilt für alle $x, y$: \[ x \in L_1 \iff R_1(x) \in L_2, \qquad y \in L_2 \iff R_2(y) \in L_3. \] \textbf{Konstruktion.} Definiere die Komposition $R := R_2 \circ R_1$, also $R(x) = R_2(R_1(x))$: Berechne zuerst $R_1(x)$, wende darauf $R_2$ an. \textbf{Korrektheit.} Für jede Eingabe $x$ gilt \[ x \in L_1 \;\iff\; R_1(x) \in L_2 \;\iff\; R_2(R_1(x)) \in L_3, \] wobei die erste Äquivalenz aus der Korrektheit von $R_1$ und die zweite aus der Korrektheit von $R_2$ (angewandt auf $y = R_1(x)$) folgt. Insgesamt also $x \in L_1 \iff R(x) \in L_3$ -- in beiden Richtungen. \textbf{Laufzeit.} Sei $|x| = n$. \begin{itemize} \item Die Berechnung von $R_1(x)$ braucht $O(n^a)$ Zeit. Da in dieser Zeit höchstens $O(n^a)$ Symbole geschrieben werden, hat die Ausgabe $R_1(x)$ die Größe $|R_1(x)| = O(n^a)$. \item Auf dieser Eingabe der Größe $O(n^a)$ braucht $R_2$ die Zeit $O\bigl((n^a)^b\bigr) = O(n^{ab})$. \item Gesamtlaufzeit $O(n^a) + O(n^{ab}) = O(n^{ab})$; wegen $a, b \ge 1$ ist $n^{ab}$ ein Polynom in $n$. \end{itemize} Damit ist $R$ eine in Polynomialzeit berechenbare Funktion mit $x \in L_1 \iff R(x) \in L_3$, also eine Reduktion $L_1 \redp L_3$. \hfill$\square$ % ====================================================================== \aufgabe{3 \quad NP-VOLLSTÄNDIGKEIT}{10 Punkte} Sei $L$ das Problem \problem{SubsetSum-ohne-Dreierpotenzen}. \textbf{$\in$ NP:} Eingabe: Zahlen $c_1, \dots, c_n$, Zielwert $K$ und Zertifikat $S \subseteq [n]$. Der Verifizierer arbeitet wie folgt: \begin{itemize} \item Prüfe für jede Größe $c_i$, dass sie keine Dreierpotenz ist (teile $c_i$ so lange wie möglich durch $3$; ist das Ergebnis $\ne 1$ bzw.\ tritt ein Rest auf, so ist $c_i$ keine Dreierpotenz); lehne sonst ab. \item Prüfe $\sum_{i \in S} c_i = K$; lehne sonst ab. \item Sonst akzeptiere. \end{itemize} \textbf{Korrektheit:} Ist die Instanz eine gültige Variante mit Lösung, so ist diese ein akzeptiertes Zertifikat; andernfalls scheitert jedes Zertifikat an einer Prüfung. \textbf{Laufzeit:} Je Größe der Dreier-Test $O(\log c_i)$ und die Summe bilden $O(n)$ -- polynomiell. Also gilt $L \in \NP$. \textbf{NP-schwer:} Zeige die NP-Schwere durch die Reduktion \[ \problem{SubsetSum} \redp L. \] \problem{SubsetSum} ist bereits als NP-vollständig bekannt. \textbf{Konstruktion:} Sei $(c_1, \dots, c_n, K)$ eine \problem{SubsetSum}-Instanz mit $c_i \in \mathbb{N}_{>0}$. Skaliere mit $2$: \[ c_i' := 2 c_i \ \ (i \in [n]), \qquad K' := 2K. \] Jede neue Größe $c_i' = 2 c_i \ge 2$ ist gerade. Dreierpotenzen $3^t$ sind dagegen für jedes $t \in \mathbb{N}_0$ ungerade (Produkt ungerader Faktoren bzw.\ $3^0 = 1$). Eine gerade Zahl $\ge 2$ ist also nie eine Dreierpotenz; insbesondere ist $c_i' \ne 1$ und $c_i' \ne 3^t$ für alle $t \ge 1$. Damit liegt die konstruierte Instanz $(c_1', \dots, c_n', K')$ in $L$. \textbf{Beweis SubsetSum nach Variante:} \begin{itemize} \item Sei $S$ mit $\sum_{i \in S} c_i = K$. \item Dann gilt $\sum_{i \in S} c_i' = \sum_{i \in S} 2 c_i = 2 \sum_{i \in S} c_i = 2K = K'$. \item Also ist $S$ eine Lösung der Variante. \end{itemize} \textbf{Beweis Variante nach SubsetSum:} \begin{itemize} \item Sei $S$ mit $\sum_{i \in S} c_i' = K'$. \item Das heißt $2 \sum_{i \in S} c_i = 2K$. \item Division durch $2$ liefert $\sum_{i \in S} c_i = K$. \item Also ist $S$ eine \problem{SubsetSum}-Lösung. \end{itemize} \textbf{Laufzeit:} Jede der $n$ Zahlen und $K$ mit $2$ multiplizieren -- $O(n)$. Da \problem{SubsetSum} NP-vollständig ist, $\problem{SubsetSum} \redp L$ gilt und $L \in \NP$, ist $L = \problem{SubsetSum-ohne-Dreierpotenzen}$ NP-vollständig. \hfill$\square$ % ====================================================================== \aufgabe{4 \quad ETH}{1 + 4 + 1 + 4 Punkte} \textbf{Teil 1: $k$-\problem{IndependentSet}.} \textbf{a)} Der Komplementgraph hat dieselben Knoten und als Kanten genau die Nicht-Kanten von $G$: \[ |V'| = |V|, \qquad |E'| = \binom{|V|}{2} - |E| = \tfrac12 |V|(|V|-1) - |E| \ \le\ |V|^2. \] \textbf{b)} \textbf{Bzgl.\ $|V'|$:} \begin{itemize} \item Angenommen, $k$-\problem{IndependentSet} wäre in $2^{o(|V'|)} \cdot |I|^{O(1)}$ lösbar. \item Ein Independent Set in $G' = \bar G$ ist genau eine Clique in $G$; die Reduktion ist in Polynomialzeit berechenbar. Der Algorithmus löst also $k$-\problem{Clique}. \item Wegen $|V'| = |V|$ wird daraus ein $2^{o(|V|)} \cdot |I|^{O(1)}$-Algorithmus für $k$-\problem{Clique}. \item Widerspruch zum Hinweis. \end{itemize} \textbf{Bzgl.\ $|E'|$:} \begin{itemize} \item Angenommen, $k$-\problem{IndependentSet} wäre in $2^{o(\sqrt{|E'|})} \cdot |I|^{O(1)}$ lösbar. \item Wegen $|E'| \le |V|^2$ ist $\sqrt{|E'|} \le |V|$, also $\sqrt{|E'|} = O(|V|)$ und damit $o(\sqrt{|E'|}) \subseteq o(|V|)$. \item Via Komplementbildung wird daraus ein $2^{o(|V|)} \cdot |I|^{O(1)}$-Algorithmus für $k$-\problem{Clique}. \item Widerspruch zum Hinweis. \end{itemize} Bounds: kein $2^{o(|V'|)}$, kein $2^{o(\sqrt{|E'|})}$. \medskip \textbf{Teil 2: \problem{SubsetSum}.} \textbf{c)} Da die Reduktion pro Menge $S_j \in F$ genau ein Item erzeugt, gilt für die Itemzahl \[ n = |F|. \] \textbf{d)} \textbf{Bzgl.\ $n$:} \begin{itemize} \item Angenommen, \problem{SubsetSum} wäre in $2^{o(\sqrt[4]{n})} \cdot |I|^{O(1)}$ lösbar. \item Die Reduktion $\problem{3-ExactCover} \redp \problem{SubsetSum}$ ist in Polynomialzeit berechenbar und erzeugt eine Instanz mit $n = |F|$ Items. \item Verkettet man sie mit dem angenommenen Algorithmus, so entsteht wegen $n = |F|$ ein $2^{o(\sqrt[4]{|F|})} \cdot |I|^{O(1)}$-Algorithmus für \problem{3-ExactCover}. \item Widerspruch zum Hinweis. \end{itemize} Bound: kein $2^{o(\sqrt[4]{n})}$. \hfill$\square$ % ====================================================================== \aufgabe{5 \quad APPROXIMATIVE ALGORITHMEN -- 2ApproxVC}{2 + 5 + 3 + (10) Punkte} \textbf{a)} Der Algorithmus fügt bei einer Kante beide Endpunkte hinzu, falls beide noch frei (nicht in $C$) sind. Kantenreihenfolge $\{1,2\}, \{1,3\}, \{2,3\}, \{3,4\}, \{4,5\}, \{4,6\}, \{5,6\}$: \begin{itemize} \item $\{1,2\}$: beide frei $\Rightarrow$ aufnehmen, $C = \{1,2\}$. \item $\{1,3\}$: $1 \in C$ $\Rightarrow$ überspringen. \item $\{2,3\}$: $2 \in C$ $\Rightarrow$ überspringen. \item $\{3,4\}$: beide frei $\Rightarrow$ aufnehmen, $C = \{1,2,3,4\}$. \item $\{4,5\}$: $4 \in C$ $\Rightarrow$ überspringen. \item $\{4,6\}$: $4 \in C$ $\Rightarrow$ überspringen. \item $\{5,6\}$: beide frei $\Rightarrow$ aufnehmen, $C = \{1,2,3,4,5,6\}$. \end{itemize} Der Algorithmus liefert $C = \{1,2,3,4,5,6\}$ mit $|C| = 6$. \emph{Vergleich mit dem Optimum:} $G$ besteht aus den beiden knotendisjunkten Dreiecken $\{1,2,3\}$ und $\{4,5,6\}$ (verbunden durch die Brücke $\{3,4\}$). Jedes Dreieck erzwingt mindestens $2$ Knoten im Cover (bei nur einem bleibt eine Kante ungedeckt), und die Dreiecke sind disjunkt, also $|C^\ast| \ge 4$. Die Menge $\{1,2,4,5\}$ deckt alle Kanten ab (auch die Brücke via $4$), somit $|C^\ast| = 4$. Die Rate in diesem Fall ist $\frac{|C|}{|C^\ast|} = \frac{6}{4} = \frac{3}{2}$. \textbf{b)} Zu zeigen: $|C| \le 2\,|C^\ast|$ für ein minimales Vertex Cover $C^\ast$. Sei $A$ die Menge der Kanten, bei denen \emph{beide} Endpunkte aufgenommen wurden; da jede solche Kante genau zwei neue Knoten beisteuert und kein Knoten doppelt aufgenommen wird, gilt $|C| = 2|A|$. \textbf{$A$ ist ein Matching.} Hätten zwei Kanten aus $A$ einen gemeinsamen Endpunkt $w$, so wäre bei der später betrachteten dieser Kanten der Knoten $w$ bereits in $C$ gewesen -- die Bedingung „beide Endpunkte frei'' wäre verletzt und die Kante nicht aufgenommen worden. Also sind die Kanten aus $A$ paarweise knotendisjunkt. \textbf{Schranke für das Optimum.} $C^\ast$ deckt jede Kante aus $A$ mit mindestens einem Endpunkt ab. Da die Kanten aus $A$ knotendisjunkt sind, braucht jede einen \emph{eigenen} Knoten in $C^\ast$, also $|C^\ast| \ge |A|$. \textbf{Kombination.} \[ |C| = 2|A| \le 2\,|C^\ast|. \] Somit hat \problem{2ApproxVC} die Güte $2$. \hfill$\square$ \textbf{c)} Der Kreis $C_n$ (mit $n$ gerade) hat als größte unabhängige Menge die $n/2$ „jeden zweiten Knoten''; also ist die maximale Unabhängigkeitszahl $n/2$ und ein minimales Vertex Cover hat Größe \[ |C^\ast| = n - \frac{n}{2} = \frac{n}{2}. \] \emph{Schlechteste Kantenreihenfolge:} Man ordnet die $n/2$ paarweise disjunkten Kanten $\{v_1,v_2\}, \{v_3,v_4\}, \dots, \{v_{n-1},v_n\}$ zuerst an (danach beliebig die restlichen Kanten). Beim Abarbeiten dieser $n/2$ Kanten sind jeweils beide Endpunkte noch frei, sodass der Algorithmus \emph{alle} $n$ Knoten aufnimmt; die übrigen Kanten haben dann stets einen bereits bedeckten Endpunkt. Es folgt $|C| = n$ und die Rate \[ \frac{|C|}{|C^\ast|} = \frac{n}{n/2} = 2, \] also der nach b) größtmögliche Wert. \textbf{d) BONUS.} Wir geben die Familie der \emph{ungeraden} Kreise $C_{2k+1}$ für $k \ge 2$ an, mit Knoten $v_1, \dots, v_{2k+1}$ und Kanten $\{v_i, v_{i+1}\}$ (Indizes modulo $2k+1$). \begin{itemize} \item \emph{Optimum:} Die größte unabhängige Menge in $C_{2k+1}$ hat Größe $k$ (man kann höchstens jeden zweiten Knoten wählen, im ungeraden Kreis also $k$). Damit ist $|C^\ast| = (2k+1) - k = k+1$. \item \emph{Ungünstige Reihenfolge:} Ordne die $k$ paarweise disjunkten Kanten $\{v_1,v_2\}, \{v_3,v_4\}, \dots, \{v_{2k-1},v_{2k}\}$ zuerst an. Beim Abarbeiten sind jeweils beide Endpunkte frei, also nimmt der Algorithmus die $2k$ Knoten $v_1, \dots, v_{2k}$ auf. Der einzige unbedeckte Knoten wäre $v_{2k+1}$; seine beiden Kanten $\{v_{2k}, v_{2k+1}\}$ und $\{v_{2k+1}, v_1\}$ haben aber je einen Endpunkt in $C$, werden also übersprungen. Somit $|C| = 2k$. \item \emph{Rate:} \[ \frac{|C|}{|C^\ast|} = \frac{2k}{k+1} \;=\; 2 - \frac{2}{k+1} \;\xrightarrow[k \to \infty]{}\; 2, \] und die Rate ist streng monoton wachsend sowie für jedes endliche $k$ echt kleiner als $2$ (z.\,B.\ $C_5{:}\ \tfrac43$, $C_7{:}\ \tfrac32$, $C_9{:}\ \tfrac85$, $C_{11}{:}\ \tfrac53$). \end{itemize} Die Approximationsrate von \problem{2ApproxVC} konvergiert also entlang der Familie $(C_{2k+1})_{k \ge 2}$ gegen $2$; zusammen mit b) ist die Güte $2$ damit asymptotisch scharf. \hfill$\square$ \end{document}