Proseminar Algorithmen

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.

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

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 *)
      Allgemein
      Minimum Cost Flow
      Planare Flows

7. Matchings (mehrere Themen; evtl. *)
      Allgemeine Graphen
      (Gewichtete Graphen)
      Gefärbte Graphen
8. Euler- und Hamiltontouren
9. Kantenfärbung
10. Knotenfärbung
11. Graphen transitiv machen (FPT)
12. FPT Methodiken (mehrere Themen):
          Distanz von Trivialität
          Datenreduktionen
          Tiefenbeschränkter Suchbaum
          (Iterative Kompression)
          Dynamische Programmierung
13. Wahlsysteme/probleme: Kontrolle (FPT)

Weitere Themen nach Absprache.

Latex - Vorlagen:

1. für die Ausarbeitung
2. für die Folien
3. für die Folien (UTF8)

LaTeX Programme:

1. Distribution für Windows (Miktex)
2. LaTeX-Editor für Windows (TeXnicCenter)
3. Distribution für Linux (Tex Live)
4. LaTeX-Editor für Linux (Kile)