Proseminar Algorithmen

Ablauf

Das Proseminar wird in Form eines Blockseminars stattfinden. Während des Semesters wird das gewählte Thema erarbeitet und die Ausarbeitung verfasst, am Ende des Semesters trägt jeder seine Ergebnisse in einer ca. 20-minütigen Präsentation vor. Es gibt zwei Arten von Themen: Themen mit Implementierungsanteil (z. B. eine algorithmische Aufgabe, bei der man diesen Algorithmus einsetzen kann) und reine Theoriethemen. In der Themenliste sind Themen mit Implementierungsanteil mit einem Sternchen gekennzeichnet. Manche Themen können auch zu zweit bearbeitet werden.

Bei der ersten Vorbesprechung werden die Themen vorgestellt. Es ist keine vorherige Anmeldung erforderlich, wer Interesse hat, kann vorbeikommen. Bei der zweiten Vorbesprechung geht es um organisatorische Dinge und die endgültige Vergabe der Themen.

Zeitplan

Kalenderwoche Verfügbare Wochen Arbeitsschritt
41-43 2 Vergabe der Themen und des Materials
(41) 43-47 5 Literaturrecherche und Erstellung einer groben Gliederung der Arbeit
Sonntag, 25. November, KW 47 Abgabe der Gliederung
48-49 2 Erstellung einer feineren Gliederung der Arbeit - stichpunktartig
Sonntag, 9. Dezember, KW 49 Abgabe der feineren Gliederung
50-1 4 Erstellung der Ausarbeitung
Sonntag, 6. Janaur, KW 1 Abgabe der Ausarbeitung
2-3 2 Korrektur durch den Betreuer und individuelle Besprechung
2-4 3 Korrekturen einbringen, Präsentationen vorbereiten
Sonntag, 27. Januar, KW 4 endgültige Abgabe der Ausarbeitung
5-6 (vorauss.) 2 Vorstellung der Präsentation

Themenliste

  1. Dynamisches Programmieren auf Bäumen *
  2. Verallgemeinertes Latin Square
  3. FPT-Algorithmus für das Vertex Cover Problem
  4. Spannbäume, Branchings and Zusammenhang von Graphen *
  5. Test von Graphen auf Planarität (evtl. *)
  6. Netzwerke und Flüsse (mehrere Themen; teilweise *)
  7.       Allgemein
          Minimum Cost Flow
          Planare Flows
  8. Matchings (mehrere Themen; evtl. *)
  9.       Allgemeine Graphen
          (Gewichtete Graphen)
          Gefärbte Graphen
  10. Euler- und Hamiltontouren
  11. Kantenfärbung
  12. Knotenfärbung
  13. Graphen transitiv machen (FPT)
  14. FPT Methodiken (mehrere Themen):
          Distanz von Trivialität
          Datenreduktionen
          Tiefenbeschränkter Suchbaum
          (Iterative Kompression)
          Dynamische Programmierung
  15. Wahlsysteme/probleme: Kontrolle (FPT)

Weitere Themen nach Absprache.

Verantwortung

Simon Straub, Dominikus Krüger, Adrian Kügel, Prof. Dr. Uwe Schöning

Vorbesprechung:

1. Vorbesprechung: Donnerstag, den 11. Oktober von 16 - 17 Uhr in O27/531

2. Vorbesprechung: Montag, den 22. Oktober von 16 - 17 Uhr in O27/531