Proseminar Algorithmen

Inhalt

Dieses Proseminar vertieft und erweitert die Vorlesung Algorithmen. Sie beschäftigen sich zu einem bestimmten Themengebiet mit Rechenverfahren und Prinzipien. Durch eine theoretische Analyse verinnerlichen Sie die Idee und das Konzept der von Ihnen behandelnden Algorithmen.

Themen

Es stehen folgende Themen zur Auswahl.

  1. Least Common Ancestor mit Range Minimum Query (Simple-LCA).
  2. SAT Solving mit Message Passing (Survey Propagation).
  3. Kürzeste Pfade für alle Knotenpaare (Floyd-Warshall, Johnsons).
  4. Maximaler Fluss (Push/Relabel)
  5. Konnektivität von Graphen und Spannbäume (DFS/BFS und Prim)
  6. Planaritätstest von Graphen (Demoucron-Malgrange-Pertuiset)
  7. Lokale Suche mit Hamming-Kugeln (Schöning, Moser-Scheder)
  8. SAT-basierte Mengenzugehörigkeitsfilter (Weaver et. al.)

Zeitplan

Das Proseminar ist als Blockveranstaltung angelegt. Bitte nehmen sie insbesondere den Termin für die Vorbesprechung zur Kenntnis.

 

ZeitplanKalenderwoche     Vorfügbare Wochen (Gesamt)Arbeitsschritt

Montag, 5. Oktober 2015

Vorbesprechung, 16:00 Uhr s.t., o27/531 (TheoInf)

41-422 (2)

Vergabe der Themen und des Materials (bei der Vorbesprechung). Literaturrecherche, Einarbeitung in Latex,  Erstellung einer detaillierten Gliederung der Arbeit (mit Latex).

  • geplante Kapitel und Unterkapitel müssen aufgeführt werden
  • detailierte Stichpunkte zu jedem Kapitel / Unterkapitel inklusive Referenzen
  • Literaturangabe (korrete Zitierweise beachten!)
Aus der detailierten Gliederung muss ersichtlich sein, dass das Thema und die Zusammenhänge verstanden wurden!
Sonntag, 18. Oktober 2015

Abgabe der Gliederung (als PDF per Email)
431 (3)Besprechung der Gliederung (individueller Termin), einarbeiten der Korrekturen
Sonntag, 25. Oktober 2015

Abgabe der korrigierten Gliederung
44-474 (7)Besprechung der korrigierten Gliederung (individueller Termin), Erstellung der Ausarbeitung
Sonntag, 22. November 2015

Abgabe der Ausarbeitung
48-492 (9)Besprechung der Ausarbeitung (individueller Termin), einarbeiten der Korrekturen
Sonntag, 6. Dezember 2015

Abgabe der korrigierten Ausarbeitung
50 1 (10)Besprechung der korrigierten Ausarbeitung, finale korrekturen einbringen, umgehend mit der Vorbereitung der Präsentation beginnen
Sonntag, 13. Dezember 2015

Abgabe der finalen Ausarbeitung
511 (11)

Präsentation vorbereiten (nur 4 Tage Zeit!)

Donnerstag, 17. Dezember 2015

Präsentation der Ergebnisse

Die im obigen Zeitplan angegebenen Termine können bis auf die Praesentation alle vorgezogen werden.

Die Ausarbeitung soll 12. Seiten umfassen und sich an das Format in der unten angegeben Formatvorlage halten.

Die Präsentation soll ca 20. Minuten dauern.

Voraussetzungen

Es bestehen keine Voraussetzungen für diese Veranstaltung, allerdings ist es sinnvoll die Vorlesung Algorithmen parallel zu hören (oder schon gehört zu haben).

Downloads

Eine Latex-Formatvorlage für die Ausarbeitung gibt es hier.

Ein Merkblatt zur Veranstaltung mit Zusatzinformationen gibt es hier.

Verantwortung

Betreuer: Oliver Gableske

Verantwortlich: Prof. Dr. Jacobo Toran