Proseminar Sommersemester 2024 - Themenvorschläge

Definitionen und erste Resultate. Sie führen grundlegende Begriffe ein und zeigen erste Konstruktionen (greedy, probabilistisch) und untere Schranken. Wir bekommen ein erstes Gefühl, was mit fehlerkorrigierenden Codes möglich ist. Hat Dominik Scheder am 9. April 2024 besprochen.

Grundlagen endlicher Körper. Wir zeigen, wie das Rechnen modulo einer Primzahl $p$ zu einem Körper führt, also zu einer Struktur, die auch Division erlaubt. Dies erweitern wir für Primzahlpotenzen $p^k$. Grundlegende Eigenschaften wie das Prinzip, dass Polynome vom Grad $d$ höchstens $d$ Wurzeln haben, und das Schwartz-Zippel-Lemma. Dieser Teil wird von Dominik Scheder vorgetragen.

Lineare Codes. Wir definieren lineare Codes als Spezialfall von allgemeinen Codes und erläutern Konzepte wie die Parity-Check-Matrix und die Generator-Matrix. Wir zeigen die Existenz linearer Codes mit zufriedenstellenden Parametern (Rate und Abstand). Dieses Thema wird von Dominik Scheder vorgetragen.

Algebraische Konstruktionen und konkatenierte Codes. Sie erklären den (binären) Walsh-Hadamard-Code und den (nicht-binären) Reed-Solomon-Code und analysieren Rate, Abstand und Blocklänge. Sie erklären, wie man zwei Codes verkettet (äußerer und innerer Code) und welchen Abstand und Rate man daraus erhält. Den Walsh-Hadamard-Code finden Sie in Kapitel 1 von Venkatesan Guruswamis Vorlesungsskript erklärt; Reed-Solomon-Codes sind in Kapitel 6.

Wenn Sie Zeit haben, erklären Sie, wie man den inneren Code (bislang der verschwenderische Walsh-Hadamard-Code) durch einen sparsameren ersetzt, um schließlich einen Code von guter Rate und gutem Abstand zu erhalten.

Codes decodieren. Sei $\mathbf{z} = z_1 \dots z_m = C(\x)$ das korrekte Codewort und $\mathbf{y} = y_1 \dots y_m$ das korrumpierte, was beim Empfänger ankommt. In der Praxis wollen wir nicht nur effizient erkennen, ob $\mathbf{y}$ korrumpiert ist, sondern, falls die Anzahl korrumpierter Stellen klein genug ist, auch das ursprüngliche Wort $\mathbf{x}$ wiederherstellen. Wir wollen also decodieren. In diesem Vortrag erklären Sie, wie man Reed-Solomon-Codes decodiert und wie man konkatenierte Codes decodiert. Dies ist in Kapitel 7, Abschnitt 3-5 erklärt.

Obere Schranken. Hier diskutieren Sie obere Schranken dafür, wie groß ein Code von bestimmten Minimalabstand werden kann. Stichwörter sind Johnson bound, Plotkin bound, Elias-Bassalygo bound. Literatur: Kapitel 4 aus Venkatesan Guruswamis Vorlesungsskript.

Dieses Thema kann auch in zwei Vorträge aufgespalten werden.

Zusätzliche Eigenschaften: lokal decodierbare Codes, list-decodierbare Codes. Szenario: Sie haben eine Datenbank fehlerkorrigierend auf einem Medium abgespeichert. Wenn Ihre Datenbank $n$ Bits lang ist, dann haben Sie einen Code $C : \{0,1\}^n \rightarrow \{0,1\}^{n'}$ verwendet und die $n'$ Bits auf dem Datenträger gespeichert. Wenn Sie nun vielleicht 100 Bits lesen wollen, dann müssen Sie dennoch den ganzen String dekodieren. Die Idee lokal decodierbarer Codes ist, dass Sie, um 1 Bit des ursprünglichen Strings zu rekonstruieren, nur auf $k$ Bits der Codierung zugreifen müssen, wobei $k \ll n'$ gilt. Sie müssen also, wenn Sie einen kleinen Teil des ursprünglichen Strings rekonstruieren wollen, nur einen kleinen des codierten Strings lesen.

List-Decodieren heißt, dass es zu dem korrumpierten Codewort $\mathbf{y}$ eventuell nicht nur ein nahegelegenes gültiges Codewort $\mathbf{y}$, sondern mehrere. Das kann je nach Anwendung immer noch sinnvoll sein, wenn die Liste der Kandidaten nicht zu groß wird: das Ergebnis der Decodierung ist also eine (kurze) Liste von Kandidaten-Wörtern. Damit erkaufen wir uns: größeren Abstand.

Shannon's noisy channel coding theorem (NCCT). Bisher haben wir an unsere Codes die Forderung gestellt, dass sie Worst-Case-Fehler erkennen können. Die Bits werden also nicht zufällig korrumpiert, sondern gegnerisch. Im (vielleicht realistischeren) Kontext des NCCT betrachten wir einen Kanal, in dem die Fehler jede Stelle zufällig und unabhängig betreffen. Dass beispielsweise jedes Bit mit Wahrscheinlichkeit 0.1 korrumpiert wird.

Das NCCT erklärt, wie wir aus der Fehlerverteilung eine Kapazität berechnen und einen Code konstruieren können, dessen Rate fast an die Kapazität heranreicht und dessen Fehlerwahrscheinlichkeit verschwindend gering ist (zum Beispiel dass bei Paketen der Länge 4096 und Fehlerwahrscheinlichkeit 0.1 pro Bit wir jedes Paket mit Wahrscheinlichkeit 0.9999 korrekt rekonstruieren können.)

Als Material können Sie Kapitel 3 aus Venkatesan Guruswamis Vorlesungsskript zu Rate ziehen.

Augmentierende Pfade, die Ford-Fulkerson-Methode und das Min-Cut-Max-Flow-Theorem.

Dinic-Algorithmus. Eine clevere Verbesserung der Ford-Fulkerson-Methode.

Matchings in bipartiten Graphen: Halls Theorem und Kőnigs Theorem. Eine Firma hat 50 Mitarbeiter und 50 Aufgaben, die erledigt werden müssen. Jeder Mitarbeiter ist nur für gewisse Aufgabe qualifiziert und hat auch nur Zeit für eine. Dies können wir als bipartiten Graphen darstellen. Wir fragen uns nun: können die Mitarbeiter so aufteilen, dass jede Aufgabe erledigt wird? Halls Theorem und Kőnigs Theorem charakterisieren genau, wann das möglich ist oder nicht. Der einfachste Weg, diese Theorem zu beweisen, ist, das ganze als Flussnetzwerk zu modellieren.

Flüsse mit maximalem Gewinn. Hier interessiert uns nicht die Menge der Resourcen, die wir durch das Netzwerk leiten, sondern wir wollen einen Gewinn maximieren. Zu jeder Kante gibt es eine Zahl, die uns sagt, wie profitabel es ist, sie zu benutzen (oder, im Gegenteil, wieviel es kostet).

Maximum Weight Matching. Wir haben $m$ Häuser und $m$ Interessenten. Jeder Interessent $j$ hat für jedes Haus $i$ eine Valuierung $v_{i,j}$ - wieviel es ihm Wert ist. Das Maximum Weight Matching Problem fragt, wie man optimal die Häuser an die Interessenten verteilt. Dabei kommt auch raus, wie man die Preise setzen sollte.

Global Minimum Cut: Kargers Algorithmus und der Stoer-Wagner-Algorithmus. Wenn wir in einem Flussnetzwerk einen minimalen $s$-$t$-Cut berechnen wollen, so können wir einfach einen Maximum-Flow-Algorithmus anwenden und daraus den Minimum Cut berechnen. Wenn wir allerdings einen globalen Minimum Cut haben wollen (uns $s$ und $t$ also egal sind) und der Graph ungerichtet ist, dann stehen uns bessere Algorithmen zur Verfügung. Kargers Algorithmus und der Stoer-Wagner-Algorithmus sind zwei echte Perlen der Algorithmik.

Dieses Thema würde sich auch für zwei Vorträge eignen.

• Mechthild Stoer und Frank Wagner: A Simple Min-Cut Algorithm (pdf)
• D. R. Karger: Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm (pdf)

Partialordnungen, Ketten und Antiketten. Partialordnungen sind eine Verallgemeinerung der allseits bekannten klein-gleich-Relation $\leq$. Wobei allerdings die Frage Was ist kleiner: $x$ oder $y$? auch die Antwort weder noch haben kann. Die Teilbarkeitsrelation $x | y$ auf den natürlichen Zahlen ($3 | 9$ und $7 | 91$ aber $3 \nmid 8$) ähnelt in Vielem der Relation $\leq$. Allerdings gibt es unvergleichbare Paare: es gilt $3 \nmid 8$ aber auch $8 \nmid 3$. Es handelt sich also um eine Partialordnung.

Partialordnungen sind eine fundamentale Struktur der diskreten Mathematik. Sie führen anhand gut ausgewählter Beispiele Begriffe wie Kette und Antikette ein und erklären und beweisen die Theoreme von Mirsky und Dilworth. Zweck ist hier auch, dass Sie mit grundlegenden Beweistechniken vertraut werden.

• Invitation to Discrete Mathematics von Jiří Matoušek und Jaroslav Nešetřil, Kapitel 2.

Die Partialordnung $\{0,1\}^n$. Die Menge $\{0,1\}^n$ alle $n$-Bit-Strings wird Ihnen in der Theoretischen Informatik oft begegnen. Sie ist mit einer Partialordnung ausgestattet: $\mathbf{x} \preceq \mathbf{y}$, wenn $x_i \leq y_i$ für jede Koordinate gilt.

Sie stellen diese Partialordnung vor und zeigen fundamentale Eigenschaften, insbesondere die größte Antikette (Satz von Sperner).

• Extremal Combinatorics von Stasys Jukna

Edge-isoperimetric inequality and vertex-isoperimetric inequality of the Hamming cube (Harper's Theorem). Das seit der Antike bekannte isoperimetrische Problem fragt: welche geometrische Form der Fläche 1 hat minimalen Umfang? Antwort: ein Kreis! Einen rigorosen Beweis gibt es aber erst seit dem 19. Jahrhundert. Im dreidimensionalen Raum: welches Objekt von Volumen 1 hat minimale Oberfläche?

Im diskreten Fall, insbesondere für eine Menge $X \subseteq \{0,1\}^n$ messen nicht das Volumen, sondern einfach die Anzahl der ELemente: $|X|$. Als Analog zur Oberfläche definieren wir die Anzahl der Kanten (edge), die die Menge $X$ verlassen, also

\begin{align*} \Delta(X) := \{ \{u,v\} \in E\ | \ u \in X, v \in \{0,1\}^n \setminus X\} \ , \end{align*}

wobei die Kantenmenge $E$ wie folgt definiert ist: $\{u,v\} \in E$, wenn sich $u$ und $v$ in genau einem Bit unterscheiden.

Bäume mit $n$ Knoten und Cayleys Formel. Wenn wir eine Knotenmenge $\{1,2,\dots,n\}$ nehmen und uns fragen, wieviele Bäume es auf dieser Knotenmenge gibt, dann lautet die Antwort: $n^{n-2}$. Dies ist bekannt als Cayleys Formel. Das Buch An invitation to Discrete Mathematics von Matoušek und Nešetřil führt gleich vier (oder mehr?) Beweise an. Interessant sind auch hier besonders die kreativen Beweistechniken.

• Kapitel 8 in Invitation to Discrete Mathematics von Jiří Matoušek und Jaroslav Nešetřil.

Kirchhoffs Theorem. Wenn wir einen Graphen $G=(V,E)$ gegeben haben, dann scheint es sehr schwierig, die Zahl aller Spannbäume von $G$ (also Bäume $T = (V,F)$ mit $F \subseteq E$) zu berechnen. Tatsächlich gibt es hierfür einen effizienten Algorithmus, der lineare Algebra und Determinanten verwendet.

• Kapitel 8.5 in Invitation to Discrete Mathematics von Jiří Matoušek und Jaroslav Nešetřil.

Fibonacci-Heaps

Fibonacci-Heaps