\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, num_pass_cards: usize, } // Die Lösung enthält die von Zara stammenden echten Karten. struct Solution { real_cards: Vec, // 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 { 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::>(); permutation.shuffle(&mut rand::thread_rng()); let mut permutation_pairs = permutation .iter() .cloned() .enumerate() .map(|(from, to)| (to, from)) .collect::>(); permutation_pairs.sort(); // `inverse_permutation` ist die zu `permutation` umgekehrte Permutation. let inverse_permutation = permutation_pairs .into_iter() .map(|(_to, from)| from) .collect::>(); // `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::::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 { let orig_num_rows = matrix.len(); let orig_num_cols = matrix[0].len(); let mut transposed = vec![BitVec::::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, } 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 "); 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}