cleanup main

1 files changed, 778 insertions, 0 deletions

diff --git a/bonusaufgabe/doc/bonusaufgabe.tex b/bonusaufgabe/doc/bonusaufgabe.tex
new file mode 100644
index 0000000..9ae52ad
--- /dev/null
+++ b/bonusaufgabe/doc/bonusaufgabe.tex
@@ -0,0 +1,778 @@
+\documentclass[a4paper,10pt,ngerman]{scrartcl}
+\usepackage{babel}
+\usepackage[T1]{fontenc}
+\usepackage[utf8x]{inputenc}
+\usepackage[a4paper,margin=2.5cm,footskip=0.5cm]{geometry}
+
+\newcommand{\Aufgabe}{Bonusaufgabe: Zara Zackigs Zurückkehr}
+\newcommand{\TeilnahmeId}{61099}
+\newcommand{\Name}{Malte Voos}
+
+\usepackage{fontspec}
+\setmonofont{mononoki}
+
+% Anführungszeichen
+\usepackage{csquotes}
+\MakeOuterQuote{"}
+
+% Kopf- und Fußzeilen
+\usepackage{scrlayer-scrpage, lastpage}
+\setkomafont{pageheadfoot}{\large\textrm}
+\lohead{\Aufgabe}
+\rohead{Teilnahme-ID: \TeilnahmeId}
+\cfoot*{\thepage{}/\pageref{LastPage}}
+
+% Position des Titels
+\usepackage{titling}
+\setlength{\droptitle}{-1.0cm}
+
+% Für mathematische Befehle und Symbole
+\usepackage{amsmath}
+\usepackage{amssymb}
+
+\newtheorem{problem}{Problem}
+
+\usepackage{siunitx}
+
+% Für Bilder
+\usepackage{graphicx}
+
+% Für Algorithmen
+\usepackage{algpseudocode}
+
+\usepackage{biblatex}
+\addbibresource{refs.bib}
+
+\usepackage{float}
+\usepackage{multirow}
+
+\usepackage{color}
+\usepackage{listings}
+\definecolor{GrayCodeBlock}{RGB}{241,241,241}
+\definecolor{BlackText}{RGB}{110,107,94}
+\definecolor{RedTypename}{RGB}{182,86,17}
+\definecolor{GreenString}{RGB}{96,172,57}
+\definecolor{PurpleKeyword}{RGB}{184,84,212}
+\definecolor{GrayComment}{RGB}{170,170,170}
+\definecolor{GoldDocumentation}{RGB}{180,165,45}
+\lstdefinelanguage{rust}
+{
+    columns=fullflexible,
+    keepspaces=true,
+    frame=single,
+    framesep=0pt,
+    framerule=0pt,
+    framexleftmargin=4pt,
+    framexrightmargin=4pt,
+    framextopmargin=5pt,
+    framexbottommargin=3pt,
+    xleftmargin=4pt,
+    xrightmargin=4pt,
+    backgroundcolor=\color{GrayCodeBlock},
+    basicstyle=\ttfamily\color{BlackText}\footnotesize,
+    keywords={
+        true,false,
+        unsafe,async,await,move,
+        use,pub,crate,super,self,mod,
+        struct,enum,fn,const,static,let,mut,ref,type,impl,dyn,trait,where,as,
+        break,continue,if,else,while,for,loop,match,return,yield,in
+    },
+    keywordstyle=\color{PurpleKeyword},
+    ndkeywords={
+        bool,u8,u16,u32,u64,u128,i8,i16,i32,i64,i128,char,str,
+        Self,Option,Some,None,Result,Ok,Err,String,Box,Vec,Rc,Arc,Cell,RefCell,HashMap,BTreeMap,
+        macro_rules
+    },
+    ndkeywordstyle=\color{RedTypename},
+    comment=[l][\color{GrayComment}\slshape]{//},
+    morecomment=[s][\color{GrayComment}\slshape]{/*}{*/},
+    morecomment=[l][\color{GoldDocumentation}\slshape]{///},
+    morecomment=[s][\color{GoldDocumentation}\slshape]{/*!}{*/},
+    morecomment=[l][\color{GoldDocumentation}\slshape]{//!},
+    morecomment=[s][\color{RedTypename}]{\#![}{]},
+    morecomment=[s][\color{RedTypename}]{\#[}{]},
+    stringstyle=\color{GreenString},
+    string=[b]"
+}
+
+% Diese beiden Pakete müssen zuletzt geladen werden
+%\usepackage{hyperref} % Anklickbare Links im Dokument
+\usepackage{cleveref}
+
+% Daten für die Titelseite
+\title{\textbf{\Huge\Aufgabe}}
+\author{\LARGE Teilnahme-ID: \LARGE \TeilnahmeId \\\\
+      \LARGE Bearbeiter/-in dieser Aufgabe: \\ 
+      \LARGE \Name\\\\}
+\date{\LARGE\today}
+
+\begin{document}
+
+\maketitle
+\tableofcontents
+
+\section{Lösungsidee}
+Gegeben ist eine Menge $C = \{c_1, \dots, c_n\}$ von $n$ Karten, die aus $w$ von Zara stammenden echten Karten und $n - w$ von den "Freunden" hinzugefügten Zufallskarten besteht. Jede Karte ist dabei als Bit-Vektor von $b$ Bits zu verstehen. Gesucht ist die Untermenge $R \subseteq C$ der $w$ echten Karten, sodass eine Karte der Untermenge (die Sicherungskarte) genau das exklusive Oder der restlichen Karten der Untermenge (der Öffnungskarten) ist. Es wird angenommen, dass diese Untermenge für jede gegebene Instanz des Problems eindeutig ist.
+
+Bei einer solchen Untermenge kann aber jede Karte als Sicherungskarte betrachtet werden, da jede Karte das exklusive Oder der jeweils restlichen Karten ist. Es ist also geschickter, die Untermenge $R$ der echten Karten dadurch zu charakterisieren, dass das exklusive Oder aller Karten in $R$ $0$ ist.
+
+$R$ kann auch durch einen Lösungsvektor $s = \begin{pmatrix} s_1 & s_2 & \cdots & s_n \end{pmatrix}^\top$ von $n$ Bits und mit Hamming-Gewicht $w$ ausgedrückt werden, wobei $s_n$ genau dann $1$ ist, wenn $c_n$ eine echte Karte ist:
+\begin{equation}
+  R = \{c_n \mid s_n = 1\}
+\end{equation}
+
+Damit lässt sich folgendes Gleichungssystem aufstellen:
+\begin{align*}
+  (c_{11} \wedge s_1) \oplus (c_{21} \wedge s_2) \oplus \dots \oplus (c_{n1} \wedge s_n) & = 0 \\
+  (c_{12} \wedge s_1) \oplus (c_{22} \wedge s_2) \oplus \dots \oplus (c_{n2} \wedge s_n) & = 0 \\
+  \noalign{\centering$\vdots$}
+  (c_{1m} \wedge s_1) \oplus (c_{2m} \wedge s_2) \oplus \dots \oplus (c_{nm} \wedge s_n) & = 0
+\end{align*}
+
+$c_{nm}$ ist dabei das $m$-te Bit der Karte $c_n$, $\oplus$ ist das exklusive Oder, und $\wedge$ ist die logische Konjunktion. Für jedes Bit der Karten wird eine Gleichung aufgestellt, wobei das Bit der Karte $c_n$ immer nur dann eingerechnet wird, wenn $s_n = 1$ ist, also $c_n$ eine echte Karte ist.
+
+Bei diesem Gleichungssystem handelt es sich sogar um ein lineares Gleichungssystem, da die Bits $\{0, 1\}$ zusammen mit dem exklusiven Oder $\oplus$ als Addition und der logischen Konjunktion $\wedge$ als Multiplikation den endlichen Körper $\mathbb{F}_2$ bilden. In Matrixschreibweise lässt sich das obige Gleichungssystem also als
+\begin{equation}
+  \label{eq:paritycheck}
+  \mathbf{H} s = 0
+\end{equation}
+schreiben, wobei $\mathbf{H}$ die Matrix ist, die in der $n$-ten Spalte die Bits der Karte $c_n$ enthält.
+
+$\mathbf{H}$ lässt sich auch als Kontrollmatrix eines linearen Codes über $\mathbb{F}_2$ betrachten: Die Codewörter dieses Codes sind genau die $s$, für die Gleichung \ref{eq:paritycheck} gilt. Ein Codewort repräsentiert also eine Auswahl von Karten, die XOR einander 0 ergeben.
+
+Gesucht ist aber nicht ein beliebiges Codewort, sondern ein Codewort mit dem Hamming-Gewicht $w$, da genau $w$ Karten von Zara stammen. Damit lässt sich Zara Zackigs Problem auf folgendes reduzieren:
+\begin{problem}
+Gegeben ist die Kontrollmatrix $\mathbf{H}$ eines linearen Binärcodes und ein positive ganze Zahl $w$. Der durch $\mathbf{H}$ definierte Code enthält ein Codewort des Hamming-Gewichts $w$. Wie lautet dieses Codewort?
+\end{problem}
+Ein verwandtes Problem lautet wie folgt:
+\begin{problem}
+Gegeben ist die Kontrollmatrix $\mathbf{H}$ eines linearen Binärcodes und ein positive ganze Zahl $w$. Enthält der durch $\mathbf{H}$ definierte Code ein Codewort des Hamming-Gewichts $w$?
+\end{problem}
+
+Dieses Entscheidungsproblem ist in der Literatur als \textsc{Subspace Weights} bekannt und bewiesenermaßen NP-vollständig \cite{bmt78}. Das zugehörige Berechnungsproblem, ein Codewort mit Hamming-Gewicht $w$ zu finden und eine Fehlermeldung auszugeben, falls keines existiert, gehört zur Komplexitätsklasse FNP und ist offensichtlich NP-schwer, da eine Lösung gleichzeitig auch eine Lösung für \textsc{Subspace Weights} ist. Zara Zackigs Problem (Problem 1) aber ist etwas einfacher: Es ist garantiert, dass ein Codewort des gegebenen Hamming-Gewichts existiert. Damit gehört es zur Komplexitätsklasse TFNP. Obwohl vermutet wird, dass TFNP keine NP-schweren Probleme enthält \cite{gp18}, wurde für viele Probleme in TFNP, wie zum Beispiel für das Faktorisierungsproblem für ganze Zahlen, bis jetzt kein in Polynomialzeit laufender Algorithmus entdeckt. Die Verwandtschaft zu Problem 2 legt auch für Problem 1 die Vermutung nahe, dass kein Algorithmus die Lösung in Polynomialzeit ermitteln kann.
+
+Das bedeutet aber nicht, dass das Problem nicht effizienter als mit der Brute-Force-Methode gelöst werden kann. Im Folgenden wird zunächst ein einfacher Brute-Force-Algorithmus und dann ein effizienterer Las-Vegas-Algorithmus vorgestellt, und im Anschluss werden die beiden Algorithmen hinsichtlich ihrer Rechenkomplexität verglichen.
+
+\subsection{Brute-Force-Algorithmus}
+
+Es wird über alle $\binom{n}{w}$ Möglichkeiten, aus den $n$ Karten $w$ auszuwählen, iteriert, und jeweils überprüft, ob es sich um die echten Karten handelt (ob das exklusive Oder der ausgewählten Karten $0$ ist). In diesem Fall ist die Lösung gefunden.
+
+\subsubsection{Rechenkomplexität}
+
+Die echten Karten werden im Durchschnitt nach $\frac{1}{2} \binom{n}{w}$ Versuchen gefunden. Bei jedem Versuch wird $(w - 1) b$ das exklusive Oder zweier Bits gebildet, und anschließend werden $b$ Bits mit $0$ verglichen. Ein Versuch benötigt demnach ungefähr $(w - 1) b + b = w b$ Bit-Operationen, und die durchschnittliche Bit-Komplexität des Brute-Force-Algorithmus liegt näherungsweise bei
+\begin{equation}
+  C_{BF} = \binom{n}{w} \frac{w b}{2}
+\end{equation}
+Bit-Operationen.
+
+\subsection{Lee-Brickell-Algorithmus}
+
+Der Lee-Brickell-Algorithmus \cite{lb88} ist einer von vielen Algorithmen für Problem 1, die nach dem Prinzip des \textit{information set decoding} (ISD) arbeiten. Die Grundidee hinter ISD ist, dass es einfacher ist, eine bestimmte Verteilung der Einsen im gesuchten Codewort richtig zu erraten, als alle Bits des \mbox{Codewortes} richtig zu erraten (wie es der Brute-Force-Algorithmus tut). Die genaue Verteilung ist dabei von Algorithmus zu Algorithmus unterschiedlich. Gemeinsam ist den ISD-Algorithmen aber, dass sie alle Las-Vegas-Algorithmen sind, d.h., dass sie ausgehend von einer Zufallsvariable die Lösung mit einer bestimmten Wahrscheinlichkeit finden oder anderenfalls eine Fehlermeldung zurückgeben. Dieses Vorgehen wird so oft in unabhängigen Iterationen wiederholt, bis die Lösung gefunden ist.
+
+Eine Iteration des Lee-Brickell-Algorithmus läuft wie folgt ab:
+\begin{enumerate}
+  \item Eine zufällige Permutation $\mathbf{P}$ von $n$ Elementen wird generiert und ihre umgekehrte Permutation $\mathbf{P}^{-1}$ wird berechnet.
+  \item Die zufällige Permutation $\mathbf{P}$ wird auf die Spalten der Kontrollmatrix $\mathbf{H}$ angewandt.
+  \item Die permutierte Kontrollmatrix $\mathbf{P} \mathbf{H}$ wird mithilfe des Gauß-Jordan-Algorithmus in die reduzierte Stufenform gebracht. Dabei werden die Spaltenindizes der Basisvariablen bzw. freien Variablen in zwei Listen gespeichert. Hier ist anzumerken, dass die Zuteilung der Spalten zu Basisvariablen und freien Variablen stark von der gewählten Permutation $\mathbf{P}$ abhängt: Je weiter links eine Spalte in der permutierten Kontrollmatrix liegt, desto eher gehört die Spalte zu einer Basisvariable in der reduzierten Stufenform.
+  \item Nun wird angenommen, dass bei dem ebenfalls permutierten gesuchten Codewort $\mathbf{P} s$ mit Hamming-Gewicht $w$ genau $p$ Einsen zu den $k$ freien Variablen, und genau $w - p$ Einsen zu den $n - k$ Basisvariablen gehören. Ob diese Annahme stimmt, hängt davon ab, ob in Schritt 1 eine glückliche Permutation gewählt wurde. $p \in \mathbb{Z}^+$ ist ein Parameter des Lee-Brickell-Algorithmus, für den offensichtlich ein paar Einschränkungen gelten:
+  \begin{gather*}
+    p \leq w \\
+    p \leq k \\
+    w - p \leq n - k \iff p \geq -n + k + w
+  \end{gather*}
+  \item Um festzustellen, welche $p$ freien Variablen in $\mathbf{P} s$ den Wert $1$ annehmen, wird über alle $\binom{k}{p}$ Möglichkeiten, aus den $k$ freien Variablen $p$ auszuwählen, iteriert.
+  \begin{enumerate}
+    \item Zunächst wird das exklusive Oder $x$ der zu den $p$ ausgewählten freien Variablen gehörenden Spalten errechnet. Aus der Struktur der reduzierten Stufenform folgt, dass genau in den Zeilen, in denen $x$ den Wert $1$ hat, auch die Basisvariable der Zeile den Wert $1$ haben muss, damit jede Zeile aufsummiert $0$ ergibt und Gleichung \ref{eq:paritycheck} erfüllt ist.
+  \item Es wird überprüft, ob $x$ ein Hamming-Gewicht von $w - p$ hat. In diesem Fall haben nämlich genau $w - p$ Basisvariablen in $\mathbf{P} s$ den Wert $1$, und die Annahme aus Schritt 4 hat sich bewahrheitet. Im permutierten Lösungsvektor $\mathbf{P} s$ haben dann von den freien Variablen die ausgewählten $p$ den Wert $1$, und von den Basisvariablen die der $w - p$ Zeilen, in denen $x$ eine $1$ hat. Damit ergibt sich die Menge $R$ der echten Karten wie folgt:
+    \begin{enumerate}
+      \item Der Lösungsvektor $s$ kann durch Anwendung der umgekehrten Permutation $\mathbf{P}^{-1}$ auf den permutierten Lösungsvektor $\mathbf{P} s$ rekonstruiert werden: $s = \mathbf{P}^{-1} \mathbf{P} s$
+      \item Die Menge der echten Karten $R$ ist gegeben durch $R = \{c_n \mid s_n = 1\}$. Damit ist die Lösung gefunden.
+    \end{enumerate}
+  \end{enumerate}
+  \item Falls in Schritt 5 die Lösung nicht gefunden wurde, ist die Annahme aus Schritt 4 falsch. Damit ist die Iteration fehlgeschlagen.
+\end{enumerate}
+
+\subsubsection{Rechenkomplexität}
+
+Die durchschnittliche Rechenkomplexität $C_{LB}$ des Lee-Brickell-Algorithmus setzt sich aus der Komplexität einer einzelnen Iteration $C_{LB1}$ und der zu erwartenden Anzahl an Iterationen $N_{LB}$ zusammen. Letztere kann auch durch den Kehrwert der Erfolgswahrscheinlichkeit einer einzelnen Iteration $P_{LB1}$ ausgedrückt werden:
+\begin{equation}
+  C_{LB} = C_{LB1} \cdot N_{LB} = \frac{C_{LB1}}{P_{LB1}}
+\end{equation}
+
+Die beiden ressourcenintensiven Schritte einer einzelnen Iteration sind erstens die Berechnung der reduzierten Stufenform mittels des Gauß-Jordan-Algorithmus und zweitens das Durchgehen der $\binom{k}{p}$ Möglichkeiten für die Position der $p$ Einsen unter den $k$ freien Variablen.
+
+Der Gauß-Jordan-Algorithmus transformiert die Matrix zunächst in die "gewöhnliche" (nicht-reduzierte) Stufenform. Dafür wird gleichzeitig "diagonal" über die Zeilen und Spalten der Matrix iteriert, bis die letzte Zeile bzw. Spalte bearbeitet wurde. In den allermeisten nicht-trivialen Fällen bleiben auf der rechten Seite noch mehrere zu freien Variablen gehörende Spalten übrig, sodass diese äußere Schleife dann $b$-mal ($b$ ist die Anzahl der Zeilen) durchlaufen wird. In jedem Durchlauf sucht der Algorithmus in der derzeitigen Spalte ein Pivotelement (eine $1$), welches $b$ Bit-Vergleiche im schlimmsten Fall benötigt. Falls ein Pivotelement gefunden wurde, wird die entsprechende Zeile nach oben gebracht, und die weiter unten liegenden Einsen der Spalte (nie mehr als $b$) werden eliminiert, indem die entsprechenden Zeilen mit der Zeile des Pivotelements XOR gerechnet werden. Für eine Zeile benötigt dies $n$ Bit-Operationen. Die Berechnung der "gewöhnlichen" Stufenform benötigt also grob $b (b + bn) = b^2 (n + 1)$ Bit-Operationen.
+
+Bei dieser Annäherung wurden aber tatsächlich zu viele Bit-Operationen eingerechnet, da nicht berücksichtigt wurde, dass für weiter rechts liegende Spalten weniger weiter unten liegende Einsen eliminiert werden müssen. Dies wird aber dadurch ausgeglichen, dass für die Berechnung der reduzierten Stufenform auch die Einsen über den Pivotelementen eliminiert werden müssen. Für die Berechnung der reduzierten Stufenform ergibt sich also eine Bit-Komplexität von ungefähr $b^2 (n + 1)$ Bit-Operationen.
+
+Um die Position der $p$ Einsen unter den $k$ freien Variablen zu ermitteln, wird über alle $\binom{k}{p}$ Möglichkeiten iteriert. Es wird jeweils das exklusive Oder $x$ der ausgewählten Spalten berechnet und überprüft, ob dies ein Hamming-Gewicht von $w - p$ hat. Die Berechnung von $x$ benötigt $(p - 1) b$ Bit-Operationen, und für die Überprüfung des Hamming-Gewichts müssen nochmals $b$ Bits betrachtet werden. Der Schritt erfordert also ingesamt näherungsweise $\binom{k}{p} ((p - 1) b) + b) = \binom{k}{p} p b$ Bit-Operationen.
+
+Damit ergibt sich die Bit-Komplexität einer einzelnen Iteration zu
+\begin{equation}
+  C_{LB1} = b^2 (n + 1) + \binom{k}{p} p b = b [b (n + 1) + \binom{k}{p} p]
+\end{equation}
+
+Eine Iteration ist genau dann erfolgreich, wenn durch die zufällig gewählte Permutation $p$ von den $k$ freien Variablen und $w - p$ von den $n - k$ Basisvariablen im Lösungsvektor den Wert 1 annehmen. Die Wahrscheinlichkeit, dass die $w$ Einsen im Lösungsvektor von $n$ Elementen auf diese Weise verteilt sind, wenn die Zuteilung zu freien Variablen und Basisvariablen komplett zufällig ist, liegt bei
+\begin{equation}
+  P_{LB1} = \frac{\binom{k}{p} \binom{n - k}{w - p}}{\binom{n}{w}}
+\end{equation}
+Zugegebenermaßen lässt sich diese nicht direkt mit der Wahrscheinlichkeit gleichsetzen, eine glückliche Permutation zu wählen, da bei der Berechnung der Stufenform vereinzelt Spalten ohne Pivotelement übersprungen und somit zu freien Variablen gezählt werden, obwohl noch weitere Basisvariablen folgen. Die Zuteilung zu freien Variablen und Basisvariablen ist demnach nicht komplett zufällig. Hier wird jedoch angenommen, dass dies keinen wesentlichen Einfluss auf die Erfolgswahrscheinlichkeit hat und somit wird (6) als Erfolgswahrscheinlichkeit verwendet.
+
+Mit (4), (5) und (6) ergibt sich die durchschnittliche Rechenkomplexität des Lee-Brickell-Algorithmus zu näherungsweise
+\begin{equation}
+  C_{LB} = \frac{C_{LB1}}{P_{LB1}} = \frac{\binom{n}{w} b [b (n + 1) + \binom{k}{p} p]}{\binom{k}{p} \binom{n - k}{w - p}}
+\end{equation}
+Bit-Operationen.
+
+\subsubsection{Wahl des Parameters $p$}
+
+Bei der Wahl des Parameters $p$ muss zwischen Ressourcenverbrauch und Erfolgswahrscheinlichkeit einer Iteration abgewogen werden: Bei kleinem $p$ gibt es weniger Möglichkeiten für die Positionen der $p$ Einsen unter den $k$ freien Variablen, und somit benötigt eine einzelne Iteration weniger Bit-Operationen bzw. Zeit. Andererseits kann ein größeres $p$ die Erfolgswahrscheinlichkeit einer einzelnen Iteration erhöhen.
+
+$p = 2$ scheint in diesem Anwendungsfall ein gutes Gleichgewicht zu schaffen, da für alle gegebenen Beispieleingaben die theoretische Bit-Komplexität $C_{LB}$ bei $p = 2$ minimal ist. Auch bei empirischen Messungen benötigte die Implementierung des Lee-Brickell-Algorithmus stets bei $p = 2$ durchschnittlich am wenigsten Zeit.
+
+\renewcommand{\arraystretch}{1.5}
+\begin{table}[H]
+\begin{center}
+\begin{tabular}{ |c||c|c|c|c||c|c|c|c|| }
+  \multicolumn{5}{ c|| }{} &
+  $p = 1$ &
+  $p = 2$ &
+  $p = 3$ &
+  $p = 4$ \\
+  \hline
+  \multirow{2}{*}{Eingabedatei} & \multirow{2}{*}{$n$} & \multirow{2}{*}{$w$} & \multirow{2}{*}{$b$} & \multirow{2}{*}{$k$} & $C_{LB}$ & $C_{LB}$ & $C_{LB}$ & $C_{LB}$ & & & & & & $\varnothing \text{Zeit}$ & $\varnothing \text{Zeit}$ & $\varnothing \text{Zeit}$ & $\varnothing \text{Zeit}$ \\
+  \hline
+  \hline
+  \multirow{2}{*}{\texttt{stapel3.txt}} & \multirow{2}{*}{161} & \multirow{2}{*}{11} & \multirow{2}{*}{128} & \multirow{2}{*}{33} & $1{,}18 \cdot 10^7$ & $9{,}22 \cdot 10^6$ & $2{,}02 \cdot 10^7$ & $2{,}03 \cdot 10^8$ & & & & & & $\SI{32}{\milli\second}$ & $\SI{30}{\milli\second}$ & $\SI{56}{\milli\second}$ & $\SI{254}{\milli\second}$ \\
+  \hline
+  \multirow{2}{*}{\texttt{stapel4.txt}} & \multirow{2}{*}{181} & \multirow{2}{*}{11} & \multirow{2}{*}{128} & \multirow{2}{*}{53} & $3{,}12 \cdot 10^7$ & $1{,}59 \cdot 10^7$ & $4{,}49 \cdot 10^7$ & $6{,}93 \cdot 10^8$ & & & & & & $\SI{125}{\milli\second}$ & $\SI{77}{\milli\second}$ & $\SI{88}{\milli\second}$ & $\SI{717}{\milli\second}$ \\
+  \hline
+  \multirow{2}{*}{\texttt{stapel5.txt}} & \multirow{2}{*}{200} & \multirow{2}{*}{5} & \multirow{2}{*}{64} & \multirow{2}{*}{136} & $2{,}44 \cdot 10^7$ & $1{,}32 \cdot 10^7$ & $2{,}44 \cdot 10^8$ & $1{,}01 \cdot 10^{10}$ & & & & & & $\SI{53}{\milli\second}$ & $\SI{22}{\milli\second}$ & $\SI{263}{\milli\second}$ & $\SI{12}{\second}$ \\
+  \hline
+\end{tabular}
+\end{center}
+\caption{Theoretische Bit-Komplexität und durchschnittliche Laufzeit für verschiedene $p$}
+\end{table}
+
+Die Beispieleingaben \texttt{stapel0.txt} bis \texttt{stapel2.txt} sind hier uninteressant, da sie mit nur einer freien Variable ($k = 1$) gewissermaßen trivial lösbar sind und $p$ zwangsläufig gleich $1$ ist.
+
+\subsection{Vergleich der beiden Algorithmen}
+
+Die obige Analyse der Rechenkomplexität hat ergeben, dass weder der Brute-Force-Algorithmus noch der Lee-Brickell-Algorithmus das Problem in Polynomialzeit lösen können. Dennoch lässt sich feststellen, dass der Lee-Brickell-Algorithmus wesentlich effizienter als der Brute-Force-Algorithmus arbeitet: Im Durchschnitt benötigt ersterer circa
+\begin{equation}
+  \frac{C_{BF}}{C_{LB}} = \frac{w \binom{k}{p} \binom{n - k}{w - p}}{2 [b (n + 1) + \binom{k}{p} p]}
+\end{equation}
+-mal weniger Bit-Operationen als letzterer. Dieser Quotient liegt für die Beispieleingaben \texttt{stapel0.txt} bis \texttt{stapel5.txt} mit $p = min(2, k)$ jeweils in der Größenordnung von $10^1$, $10^2$, $10^{10}$, $10^{12}$, $10^{12}$ und $10^4$.
+
+Den größten Vorteil gegenüber dem Brute-Force-Algorithmus hat der Lee-Brickell-Algorithmus bei Eingaben mit vielen Karten und vielen Bits pro Karte (wenigen freien Variablen), da bei solchen Eingaben durch die Anwendung des Gauß-Verfahrens am meisten Arbeit eingespart wird.
+
+\section{Umsetzung}
+
+Das Programm wurde in der Programmiersprache Rust geschrieben und enthält im Kern eine Implementierung des in Abschnitt 1.2 beschriebenen Lee-Brickell-Algorithmus. Zusätzlich wurden die Programmbibliotheken \textit{bitvec} \cite{rust-bitvec}, welche eine platzsparende Datenstruktur für Bit-Vektoren bereitstellt, und \textit{rand} \cite{rust-rand}, welche das Arbeiten mit Zufallszahlen erleichtert, verwendet.
+
+Der Einstiegspunkt für den eigentlichen Algorithmus ist die Funktion \texttt{solve\_task}, welche eine Aufgabe (Datentyp \texttt{Task}), bestehend aus dem Kartenstapel und der Anzahl von Zaras Öffnungskarten, erhält und die Lösung (Datentyp \texttt{Solution}), bestehend aus Zaras echten Karten, zurückgibt. Die Funktion \texttt{lee\_brickell\_iteration} implementiert eine Iteration des Lee-Brickell-Algorithmus und gibt nur mit einer bestimmten Wahrscheinlichkeit die Lösung zurück; \texttt{solve\_task} ruft \texttt{lee\_brickell\_iteration} also wiederholt auf, bis die Lösung gefunden ist.
+
+In \texttt{lee\_brickell\_iteration} wird die Matrix zusätzlich zweimal transponiert. Das hat den Vorteil, dass bei dem Gauß-Verfahren die Zeilen der Matrix zusammenhängend im Speicher liegen und so schneller miteinander XOR gerechnet (addiert) werden können. Später wird die Matrix nochmals transponiert, damit bei der Berechnung von $x$ in Schritt 5a) wieder die Spalten zusammenhängend im Speicher liegen.
+
+Ansonsten entspricht die Implementierung ziemlich direkt dem in Abschnitt 1.2 beschriebenen Lee-Brickell-Algorithmus. Weitere Details zur Implementierung sind im angehängten, ausgiebig kommentierten Quellcode zu finden.
+
+\section{Beispiele}
+
+\textit{Bei einigen Beispielen wurde die Programmausgabe am Seitenrand abgeschnitten, um pro Zeile die Bits einer Karte darstellen zu können. Die vollständigen Ausgaben sind im Order "Beispielausgaben" zu finden.}
+
+\medskip
+
+Zunächst die Beispiele von der BwInf-Webseite:
+
+\begin{verbatim}
+$ AusführbaresProgramm/bonusaufgabe-x86_64-linux-static Beispieleingaben/stapel0.txt
+Randinformationen (siehe Dokumentation):
+n = 20; w = 5; b = 32; k = 1; p = 1
+
+Echte Karten:
+00111101010111000110100110011001
+10101100111111011010100011100000
+10111000011001110000101010111110
+11010111111010111101101111110000
+11111110001011010001000000110111
+
+Laufzeit ohne I/O: 279.946µs
+
+$ AusführbaresProgramm bonusaufgabe-x86_64-linux-static Beispieleingaben/stapel1.txt
+Randinformationen (siehe Dokumentation):
+n = 20; w = 9; b = 32; k = 1; p = 1
+
+Echte Karten:
+00010001110100110001111101100100
+00100000111100111110111101111100
+00100011100111011010111011100011
+00110100001010100100001111010010
+00110110000110101101011111111010
+11000111111010110100000101110100
+11010011010110110101001101010111
+11110011101011001001000010111110
+11110111100100010100100001001110
+
+Laufzeit ohne I/O: 287.396µs
+
+$ AusführbaresProgramm/bonusaufgabe-x86_64-linux-static Beispieleingaben/stapel2.txt
+Randinformationen (siehe Dokumentation):
+n = 111; w = 11; b = 128; k = 1; p = 1
+
+Echte Karten:
+00101000011000010010111011101011011010111000100100110101111011011110111100101100001001110010100001101001110001000100010011111100
+00101011111000101011010110111100100110000000000011010011001111011001011001000010001101010110110010101110100100001011100011010001
+01101001001011000101001111111101011000001000101100111010100101011011000100000001100001100011010110101011110110100000100101001011
+01101011101000110111010001100001110000011000110101100010111011100110011011110111011100110101101111000011110111011101011111100111
+01110110011110001110011110001101101110100101000000100000101100001010001110101000000011010011000011010010110110100101111101101000
+10000000000100100110011001000110000000000101010110100100100001000111010110110101010010101000101110101100101000110010100100111011
+10101011000001101100000101111111110011000110011100101011011111011000111111101111101000111111010000001011011011111111010011011110
+10101111110010010010100111101100010011111000010101001100100001111000100010010010011010010101011111101011000001111110000000111011
+11000011000100110111000101100100101101010110011011010101101001000011110100010001001010000110010101010010001100010001101110100000
+11011110000101001101111100110000111010011011101111010111110110110111011010001001101101100111010001000011000001010111100101111111
+11101110101011100111101111000111001101111011010101011111000110100011010001100000111101000010001100100000011101100010001011101000
+
+Laufzeit ohne I/O: 10.394463ms
+
+$ AusführbaresProgramm/bonusaufgabe-x86_64-linux-static Beispieleingaben/stapel3.txt
+Randinformationen (siehe Dokumentation):
+n = 161; w = 11; b = 128; k = 33; p = 2
+
+Echte Karten:
+00100000111001110001101010001111110011110001011110100110010101100010011000100111101011001111001111111011110110011111001010100001
+01010000101101110011110001110011010011001111111000001000000100000010111100001110100001001001111101111001010011110110111110011011
+01110001111110101000010011100011111111100111101101110001010100010110001100010101000010100010100001010000010100001000101110101100
+01110110100111001000011011100100101010111111001011110000001011001101100101100111001011100000011010010011100111100101011010010111
+01111101100010101100110011101011010101001101000110011111101010110000000111000110101001111111110100100001100010011111100010110100
+10110000001001100110110101000100110011100101100110101111011111101000001110100011000001100000010101111111000000000101111010010001
+10110111010010111110110011000101011101000011111100001000001100111111111001001100011100011110011111101000111010111000011110110101
+10111000101111100010111110101010101100110001000011011001100010110110000001100001101111010100001100100010001101000110010011001100
+10111111010101001100000101101100111101000010100010100100001001111010110100100101100011101100011010100000011010101001110100010111
+11000001011001000110100111011111111011111011011010111110100010110000101111000111001010100101100000111011101011010101100111010100
+11001011010111111110111010001000100100000101100111010100111110100000100111110001110001011000000001001110110010011100000110011110
+
+Laufzeit ohne I/O: 45.019015ms
+
+$ AusführbaresProgramm/bonusaufgabe-x86_64-linux-static Beispieleingaben/stapel4.txt
+Randinformationen (siehe Dokumentation):
+n = 181; w = 11; b = 128; k = 53; p = 2
+
+Echte Karten:
+00000111011010010101101110001111101001110010100011000001000001101110101111101001000100000001111011111001101011010000100011011110
+00101100000111101111000010000001011011111110000110011111111110001111000000101111101100010010000010100001010111110110000101001010
+00101100001110001110011110000100110000000000111011011001110100010100001010000110110010000111110011000100111101001100100010010000
+00110110010111001001001111001111101010011100000100000001100010101000111001000100111000100110111111100100010010100100111011110100
+01000011001001101011001111011101111010010110111010111110110111111001000100010110101100101111110000011000100111011000001101000111
+10000001000101110011010100011000110100110100111100100010001000011011000001010111100110111011101110001011110000100100001110000101
+10001100001011001101001011000110110101001101000010000101101010101100110110111111010110011001001101100100001011110000111010000111
+10101010000011111111001111011110001000100111010000010010111101000001010001100010110011110111111010111000000011000110111110000110
+11000101110001001000001011101000100110011001111011101001011010110100111000100001000100000011000010101111001001101101010111011101
+11100010000000111101001111111001001100111011101001000111001111001111000010000101100001000011000011001011101101010000101111100001
+11110010110001100010100110001001110001111010011100100011010100101001000100111100101000001000011101010011101000111001000000001111
+
+Laufzeit ohne I/O: 63.322147ms
+
+$ AusführbaresProgramm/bonusaufgabe-x86_64-linux-static Beispieleingaben/stapel5.txt
+Randinformationen (siehe Dokumentation):
+n = 200; w = 5; b = 64; k = 136; p = 2
+
+Echte Karten:
+0101111111000111000000101111100010111010110101000100000011001000
+1000010011101010001111100100110110011011100101010100010000001001
+1010000110101100101110111001100011011110111111010111000101111110
+1010111011001100100110001100110001011101001000000011011111100100
+1101010001001101000111111110000110100010100111000100001001011011
+
+Laufzeit ohne I/O: 21.107732ms
+\end{verbatim}
+
+Bei dem Beispiel \texttt{wahre\_freunde.txt} haben Zaras Freunde keine Zufallskarten hinzugefügt:
+\begin{verbatim}
+$ AusführbaresProgramm/bonusaufgabe-x86_64-linux-static Beispieleingaben/wahre_freunde.txt 
+Randinformationen (siehe Dokumentation):
+n = 9; w = 9; b = 32; k = 1; p = 1
+
+Echte Karten:
+00010001110100110001111101100100
+00100000111100111110111101111100
+00100011100111011010111011100011
+00110100001010100100001111010010
+00110110000110101101011111111010
+11000111111010110100000101110100
+11010011010110110101001101010111
+11110011101011001001000010111110
+11110111100100010100100001001110
+
+Laufzeit ohne I/O: 97.26µs
+\end{verbatim}
+
+Das Beispiel \texttt{nur\_ein\_haus.txt} deckt den Fall ab, dass Zara nur ein Ferienhaus besitzt:
+\begin{verbatim}
+$ AusführbaresProgramm/bonusaufgabe-x86_64-linux-static Beispieleingaben/nur_ein_haus.txt
+Randinformationen (siehe Dokumentation):
+n = 20; w = 2; b = 32; k = 1; p = 1
+
+Echte Karten:
+00010001110100110001111101100100
+00010001110100110001111101100100
+
+Laufzeit ohne I/O: 259.803µs
+\end{verbatim}
+
+\section{Quellcode}
+
+Teile des Quellcodes, die nur der Ein- bzw. Ausgabe dienen, werden hier nicht abgedruckt.
+
+\begin{lstlisting}[language=rust]
+type Card = BitVec;
+
+// Typ, der eine zu lösende Aufgabe beschreibt.
+struct Task {
+    cards: Vec<Card>,
+    num_pass_cards: usize,
+}
+
+// Die Lösung enthält die von Zara stammenden echten Karten.
+struct Solution {
+    real_cards: Vec<Card>,
+    // Der Anschaulichkeit halber werden ein paar weitere Randinformationen
+    // mit ausgegeben.
+    num_cards: usize,
+    num_real_cards: usize,
+    bits_per_card: usize,
+    num_free_vars: usize,
+    p: usize,
+}
+
+// `solve_task` löst eine gegebene Aufgabe und beinhaltet den
+// eigentlichen Algorithmus.
+fn solve_task(task: &Task) -> Solution {
+    // `num_real_cards` Karten im Stapel stammen von Zara Zackig, nämlich
+    // die `num_pass_cards` Öffnungskarten plus eine Sicherungkarte.
+    let num_real_cards = task.num_pass_cards + 1;
+
+    // Der Lee-Brickell-Algorithmus erzeugt nur mit einer gewissen
+    // Wahrscheinlichkeit eine Lösung. Daher führen wir ihn wiederholt aus,
+    // bis eine Lösung gefunden wurde.
+    loop {
+        match lee_brickell_iteration(&task.cards, num_real_cards) {
+            None => continue,
+            Some(solution) => break solution,
+        }
+    }
+}
+
+// Parameter für den Lee-Brickell-Algorithmus.
+const P: usize = 2;
+
+// `lee_brickell_iteration` beinhaltet eine Iteration des
+// Lee-Brickell-Algorithmus. Die Funktion liefert nur mit einer gewissen
+// Wahrscheinlichkeit eine Lösung, und gibt anderenfalls `None` zurück.
+fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solution> {
+    let num_cards = cards.len();
+    let bits_per_card = cards[0].len();
+
+    // `permutation` ist eine zufällige Permutation der Karten, repräsentiert
+    // durch ein Array, in dem jeder Index in `cards` einmal vorkommt.
+    let mut permutation = (0..num_cards).into_iter().collect::<Vec<usize>>();
+    permutation.shuffle(&mut rand::thread_rng());
+
+    let mut permutation_pairs = permutation
+        .iter()
+        .cloned()
+        .enumerate()
+        .map(|(from, to)| (to, from))
+        .collect::<Vec<(usize, usize)>>();
+    permutation_pairs.sort();
+
+    // `inverse_permutation` ist die zu `permutation` umgekehrte Permutation.
+    let inverse_permutation = permutation_pairs
+        .into_iter()
+        .map(|(_to, from)| from)
+        .collect::<Vec<usize>>();
+
+    // `ppcm` steht für "permuted parity-check matrix". Wie in der
+    // Dokumentation beschrieben, ist die Matrix, welche die gegebenen Karten
+    // als ihre Spalten enthält, Kontrollmatrix eines linearen Codes über den
+    // endlichen Körper GF(2). Die Codewörter dieses Codes repräsentieren
+    // jeweils eine Auswahl von Karten, die XOR einander null ergeben. Die
+    // Lösung des Problems ist gegeben durch ein Codewort dieses Codes mit
+    // Hamming-Gewicht `num_real_cards`.
+    // `ppcm` ist eine solche Kontrollmatrix (repräsentiert als Iliffe-Vektor),
+    // auf dessen Spalten zusätzlich noch die Permutation `permutation`
+    // angewandt wurde.
+    let mut ppcm = transpose_and_optionally_permute_columns(cards, Some(&permutation));
+
+    // `basic_vars` und `free_vars` enthalten jeweils die Spaltenindizes der
+    // Basisvariablen bzw. freien Variablen von `ppcm`.
+    let mut basic_vars = Vec::new();
+    let mut free_vars = Vec::new();
+
+    // Zunächst wird `ppcm` mittels des Gaußschen Eliminierungsverfahrens
+    // in die reduzierte Stufenform gebracht.
+    let mut current_row = 0;
+    let mut current_col = 0;
+    while current_row < bits_per_card && current_col < num_cards {
+        // Wir suchen in der derzeitigen Spalte ein Pivotelement (eine 1).
+        let pivot_row = match (current_row..bits_per_card).find(|row| ppcm[*row][current_col]) {
+            Some(row) => row,
+            None => {
+                // Wurde kein Pivotelement gefunden, gehört diese Spalte zu
+                // einer freien Variable, und es kann zur nächsten Spalte
+                // übergegangen werden.
+                free_vars.push(current_col);
+                current_col += 1;
+                continue;
+            }
+        };
+        // Wurde ein Pivotelement gefunden, gehört die Spalte zu einer
+        // Basisvariable.
+        basic_vars.push(current_col);
+        // Die Zeile mit dem Pivotelement wird nach oben gebracht, indem sie
+        // mit der derzeitigen Zeile getauscht wird.
+        ppcm.swap(current_row, pivot_row);
+        // Alle weiter unten liegenden Einsen dieser Spalte werden eliminiert,
+        // indem die entsprechenden Zeilen mit der Zeile des Pivotelements XOR
+        // gerechnet (addiert) werden.
+        for lower_row in (current_row + 1)..bits_per_card {
+            if ppcm[lower_row][current_col] {
+                let current_row_cloned = ppcm[current_row].clone();
+                ppcm[lower_row] ^= current_row_cloned;
+            }
+        }
+        // Es kann zur nächsten Zeile und Spalte übergegangen werden.
+        current_row += 1;
+        current_col += 1;
+    }
+    // Übrig gebliebene Spalten, die nicht mehr betrachtet wurden, da die
+    // letzte Zeile der Matrix erreicht wurde, gehören zu freien Variablen.
+    free_vars.extend(current_col..num_cards);
+
+    let num_free_vars = free_vars.len();
+    let num_basic_vars = basic_vars.len();
+
+    // Sanity Check: Nach dem Rangsatz immer erfüllt
+    assert_eq!(num_basic_vars + num_free_vars, num_cards);
+
+    // Hier ist `ppcm` in Stufenform.
+
+    // Um die reduzierte Stufenform zu erreichen, wird noch einmal rückwärts
+    // über die Spalten mit Pivotelement iteriert. Die weiter oben liegenden
+    // Einsen werden eliminiert, indem die entsprechenden Zeilen mit der Zeile
+    // des Pivotelements XOR gerechnet (addiert) werden. Diese Erweiterung
+    // wird auch als Gauß-Jordan-Algorithmus bezeichnet.
+    for (pivot_row, pivot_col) in basic_vars.iter().enumerate().rev() {
+        for upper_row in 0..pivot_row {
+            if ppcm[upper_row][*pivot_col] {
+                let pivot_row_cloned = ppcm[pivot_row].clone();
+                ppcm[upper_row] ^= pivot_row_cloned;
+            }
+        }
+    }
+
+    // Im letzten Schritt wird versucht, aus der Kontrollmatrix `ppcm` ein
+    // Codewort mit Hamming-Gewicht `num_real_cards` zu extrahieren, indem
+    // angenommen wird, dass in der Lösung genau `p` der freien Variablen
+    // den Wert 1 haben. Ob diese Annahme stimmt, hängt davon ab, ob im ersten
+    // Schritt eine glückliche Permutation gewählt wurde.
+
+    // In einigen Fällen muss der Parameter `P` des Lee-Brickell-Algorithmus
+    // an die Eingabe angepasst werden, z.B. bei sehr leicht lösbaren Aufgaben
+    // mit nur einer freien Variable. Details sind in der Dokumentation,
+    // Abschnitt 1.2, Schritt 4 zu finden.
+    let p = ((P as isize).clamp(
+        -(num_cards as isize) + num_free_vars as isize + num_real_cards as isize,
+        num_real_cards.min(num_free_vars) as isize,
+    )) as usize;
+
+    // Zunächst wird die Matrix transponiert, damit die Bits der Spalten
+    // jeweils zusammenhängend im Speicher liegen und somit die Spalten
+    // schneller miteinander XOR gerechnet werden können.
+    let transposed_ppcm = transpose_and_optionally_permute_columns(&ppcm, None);
+
+    // Um die `p` freien Variablen mit dem Wert 1 zu finden, wird über alle
+    // möglichen `p`-Untermengen der freien Variablen iteriert und jeweils
+    // angenommen, dass von den freien Variablen nur die in der Untermenge den
+    // Wert 1 haben.
+    let mut subset_iter = SubsetIterator::new(num_free_vars, p);
+    while let Some(subset) = subset_iter.next() {
+        // Zunächst wird das exklusive Oder der `p` Spalten in der Untermenge
+        // errechnet. Aus der Struktur der reduzierten Stufenform folgt, dass
+        // in jeder Zeile, in der `subset_xor` den Wert 1 hat, auch die
+        // Basisvariable dieser Zeile den Wert 1 haben muss, damit die Zeile
+        // insgesamt den Wert 0 hat (es handelt sich um eine Zeile der
+        // Kontrollmatrix!)
+        let mut subset_xor = BitVec::<usize, Lsb0>::repeat(false, bits_per_card);
+        for free_var_idx in subset {
+            subset_xor ^= &transposed_ppcm[free_vars[*free_var_idx]];
+        }
+
+        // Damit insgesamt `num_real_cards` Elemente des Lösungsvektors den
+        // Wert 1 haben, müssen genau `num_real_cards - p` Basisvariablen den
+        // Wert 1 haben, da oben angenommen wurde, dass von den freien
+        // Variablen genau `p` den Wert 1 haben.
+        if subset_xor.count_ones() == num_real_cards - p {
+            // Ist dies der Fall, ist die Lösung gefunden. Die echten Karten
+            // werden in `real_cards` gesammelt. Dabei wird die
+            // Spaltenpermutation mittels `inverse_permutation` rückgängig
+            // gemacht.
+            let mut real_cards = Vec::new();
+            for free_var_idx in subset {
+                real_cards.push(cards[inverse_permutation[free_vars[*free_var_idx]]].clone());
+            }
+            for basic_var_row in subset_xor.iter_ones() {
+                real_cards.push(cards[inverse_permutation[basic_vars[basic_var_row]]].clone());
+            }
+            // Der Benutzerfreundlichkeit gegenüber Zara halber werden die
+            // echten Karten vor der Ausgabe aufsteigend sortiert.
+            real_cards.sort();
+
+            return Some(Solution {
+                real_cards,
+                num_cards,
+                num_real_cards,
+                bits_per_card,
+                num_free_vars,
+                p,
+            });
+        }
+    }
+
+    // Von den freien Variablen hatten nicht genau `p` den Wert 1. Diese
+    // Iteration ist fehlgeschlagen, und in der nächten Iteration wird eine
+    // andere Spaltenpermutation und somit auch eine andere Auswahl freier
+    // Variablen probiert.
+    None
+}
+
+// Diese Funktion transponiert eine Bit-Matrix und wendet anschließend, falls
+// gefordert, auf die transponierte Matrix die gegebene Spaltenpermutation an.
+// Durch die Vereinigung dieser beiden Operationen kann unnötiges Herumkopieren
+// von Bits vermieden werden.
+fn transpose_and_optionally_permute_columns(
+    matrix: &[BitVec],
+    permutation: Option<&[usize]>,
+) -> Vec<BitVec> {
+    let orig_num_rows = matrix.len();
+    let orig_num_cols = matrix[0].len();
+
+    let mut transposed = vec![BitVec::<usize, Lsb0>::repeat(false, orig_num_rows); orig_num_cols];
+    for orig_row_idx in 0..orig_num_rows {
+        let new_col_idx = match permutation {
+            Some(permutation) => permutation[orig_row_idx],
+            None => orig_row_idx,
+        };
+        for orig_col_idx in 0..orig_num_cols {
+            let new_row_idx = orig_col_idx;
+            transposed[new_row_idx].set(new_col_idx, matrix[orig_row_idx][orig_col_idx]);
+        }
+    }
+    transposed
+}
+
+// Iterator, der über alle "n über k" k-Untermengen einer Menge von n Elementen
+// iteriert. Die Elemente der Menge sind die natürlichen Zahlen von 0 bis n-1.
+// Die Untermengen werden durch ein aufsteigend sortiertes Array repräsentiert.
+struct SubsetIterator {
+    n: usize,
+    k: usize,
+    fresh: bool,
+    subset: Vec<usize>,
+}
+
+impl SubsetIterator {
+    fn new(n: usize, k: usize) -> Self {
+        Self {
+            n,
+            k,
+            fresh: true,
+            // Zu Anfang enthält die Untermenge die niedrigsten k Zahlen.
+            subset: (0..k).into_iter().collect(),
+        }
+    }
+
+    fn next(&mut self) -> Option<&[usize]> {
+        // Falls dies die erste Iteration ist, geben wir einfach die in "new()"
+        // (s.o.) definierte Anfangs-Untermenge zurück.
+        if self.fresh {
+            self.fresh = false;
+            Some(&self.subset)
+        } else {
+            // `last_index` ist der Index des letzten Elements der Untermenge.
+            let last_index = self.k - 1;
+            // `index_to_increase` ist der Index des Elements der Untermenge,
+            // das durch die nächstgrößere Zahl ersetzt wird.
+            // Wir durchsuchen die Untermenge von links nach rechts nach einem
+            // erhöhbaren Element, sodass immer das niedrigste Element zuerst
+            // erhöht wird.
+            let index_to_increase = self
+                .subset
+                .iter()
+                .enumerate()
+                .find(|(index, val)| {
+                    if *index == last_index {
+                        // Falls dies das letzte Element der Untermenge ist,
+                        // kann es nurnoch erhöht werden, wenn die
+                        // nächtsgrößere Zahl noch Teil der Gesamtmenge ist.
+                        self.subset[*index] != self.n - 1
+                    } else {
+                        // Ansonsten kann das Element erhöht werden, wenn die
+                        // nächstgrößere Zahl nicht schon durch ein anderes
+                        // Element in der Untermenge repräsentiert ist.
+                        self.subset[*index + 1] != **val + 1
+                    }
+                })? // das '?' gibt sofort `None` zurück, wenn kein erhöhbares
+                // Element gefunden wurde und somit schon über alle Untermengen
+                // iteriert wurde.
+                .0;
+
+            // Das im vorherigen Schritt gefundene Element wird um 1 erhöht,
+            // und alle kleineren Elemente werden analog zum "normalen Zählen"
+            // auf die kleinstmöglichen Werte gesetzt.
+            self.subset[index_to_increase] += 1;
+            for lower_idx in 0..index_to_increase {
+                self.subset[lower_idx] = lower_idx;
+            }
+
+            // Die neu errechnete Untermenge wird zurückgegeben.
+            Some(&self.subset)
+        }
+    }
+}
+
+// Einstiegspunkt für das Programm.
+fn main() {
+    let task_file_name = match env::args().nth(1) {
+        Some(x) => x,
+        None => {
+            eprintln!("Nutzung: bonusaufgabe <dateiname>");
+            process::exit(1);
+        }
+    };
+    let task_str = fs::read_to_string(task_file_name).expect("Datei kann nicht gelesen werden");
+    let task = Task::try_from(task_str.as_str()).expect("Datei enthält keine gültige Aufgabe");
+
+    let start = time::Instant::now();
+    let solution = solve_task(&task);
+    let elapsed = start.elapsed();
+
+    println!("{}", solution);
+    println!("Laufzeit ohne I/O: {:?}", elapsed);
+}
+\end{lstlisting}
+
+\section{Teilaufgabe b)}
+
+\begin{tabular}{|p{15.8cm}}
+\textit{Wie kann nun Zara mithilfe der 11 gefundenen Karten am nächsten Wochenende das nächste Haus aufsperren, ohne dafür mehr als zwei Fehlversuche zu benötigen?}
+\end{tabular}
+
+\medskip
+
+Zara sortiert die gefundenen echten Karten ähnlich wie die Öffnungskarten der Häuser aufsteigend als $r_1, r_2, \dots, r_w$. Die Öffnungskarte für Haus $k$ ist jetzt entweder $r_k$ oder $r_{k + 1}$, je nachdem, ob sie im sortierten Stapel vor oder hinter der Sicherungskarte liegt.
+
+Wenn Zara also am nächsten Wochenende Haus $k$ besucht, muss sie nur die Karten $r_k$ und $r_{k + 1}$ probieren. Mit dieser Strategie benötigt Zara höchstens einen Fehlversuch, um das Haus aufzusperren.
+
+\printbibliography
+
+\end{document}