Proseminar Sommersemester 2024 - Themenvorschläge
Ich hoffe, zu Semesterbeginn zu jedem Thema Literaturangaben gegeben zu haben. Ganz generell gehören die meisten Themen hier bereits zum "Kanon". Das heißt, Sie müssen nicht unbedingt auf das ursprüngliche Paper zurückgreifen. Vielfach gibt es Vorlesungsskripte, Webseiten oder sogar Buchkapitel, die das Thema zugänglicher behandeln. Vielfach ist Wikipedia ein guter Startpunkt. Welche Quellen Sie auch immer Ihrem Vortrag und Ihrer Ausarbeitung zugrunde legen: Geben Sie die dann bitte im Literaturverzeichnis an.
1. Error correcting codes. In diesem Themenblock will ich mit Ihnen die Begriffe der fehlerkorrigierenden Codes durchnehmen und erarbeiten, wie man solche konstruiert und was für Raten erreichbar sind.
LiteraturEs gibt zahlreiche Bücher zu diesem Thema. Sie können mal im Internet suchen, mich fragen, oder hier starten:
- Venkatesan Guruswamis Kurs Introduction to Coding Theory
- Kapitel 17.5, Constructions of Error Correcting Codes im Buch Computational Complexity: A Modern Approach von Sanjeev Arora und Boaz Barak (draft pdf).
1.1 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.
1.2 Grundlagen endlicher Körper.
Wir zeigen, wie das Rechnen modulo einer Primzahl
1.3 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.
1.4 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.
1.5 Codes decodieren.
Sei
1.6 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.
1.7 Zusätzliche Eigenschaften: lokal decodierbare Codes,
list-decodierbare Codes.
Szenario: Sie
haben eine Datenbank fehlerkorrigierend auf einem Medium abgespeichert. Wenn Ihre Datenbank
List-Decodieren heißt, dass es zu dem korrumpierten Codewort
1.8 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.
2. Flussnetzwerke. Ein Flussnetzwerk modelliert ein Netzwerk aus Verbindungen, die verschiedene Kapazitäten haben. Denken Sie an Daten-, Bahn- oder Pipelinenetzwerke. Ziel ist es, möglichst viele "Güter" von einem Start- zu einem Zielknoten zu transportieren, die Kapazitäten also optimal auszunutzen.
Ich werde einen kurzen Anstoßvortrag geben, in welchem ich Grundbegriffe einführe und Beispiele zeige.
Literatur
- Kapitel 26 in CLRS (Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms
- Der Übersichtsartikel Network Flow Algorithms von Andrew V. Goldberg, Éva Tardos und R. Tarjan (pdf)
- Das Buch Network Flow Algorithms von David P. Williamson (pdf).
2.1 Augmentierende Pfade, die Ford-Fulkerson-Methode und das Min-Cut-Max-Flow-Theorem.
2.2 Dinic-Algorithmus. Eine clevere Verbesserung der Ford-Fulkerson-Methode.
2.3 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.
2.4 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).
2.5 Maximum Weight Matching. Wir haben
2.6 Global Minimum Cut: Kargers Algorithmus und der Stoer-Wagner-Algorithmus.
Wenn wir in einem Flussnetzwerk einen minimalen
Dieses Thema würde sich auch für zwei Vorträge eignen.
3. Diskrete Mathematik
3.1 Partialordnungen, Ketten und Antiketten. Partialordnungen sind eine
Verallgemeinerung der allseits bekannten klein-gleich-Relation
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.
3.2 Die Partialordnung
Sie stellen diese Partialordnung vor und zeigen fundamentale Eigenschaften, insbesondere die größte Antikette (Satz von Sperner).
- Extremal Combinatorics von Stasys Jukna
3.3 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
wobei die Kantenmenge
3.4 Bäume mit
- Kapitel 8 in Invitation to Discrete Mathematics von Jiří Matoušek und Jaroslav Nešetřil.
3.5 Kirchhoffs Theorem. Wenn wir einen Graphen
- Kapitel 8.5 in Invitation to Discrete Mathematics von Jiří Matoušek und Jaroslav Nešetřil.
4. Dijkstras Algorithmus
4.1 Fibonacci-Heaps
4.2 Fibonacci-Heaps