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.
- Least Common Ancestor mit Range Minimum Query (Simple-LCA).
- SAT Solving mit Message Passing (Survey Propagation).
- Kürzeste Pfade für alle Knotenpaare (Floyd-Warshall, Johnsons).
- Maximaler Fluss (Push/Relabel)
- Konnektivität von Graphen und Spannbäume (DFS/BFS und Prim)
- Planaritätstest von Graphen (Demoucron-Malgrange-Pertuiset)
- Lokale Suche mit Hamming-Kugeln (Schöning, Moser-Scheder)
- 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-42 | 2 (2) | Vergabe der Themen und des Materials (bei der Vorbesprechung). Literaturrecherche, Einarbeitung in Latex, Erstellung einer detaillierten Gliederung der Arbeit (mit Latex).
|
| Sonntag, 18. Oktober 2015 | Abgabe der Gliederung (als PDF per Email) | |
| 43 | 1 (3) | Besprechung der Gliederung (individueller Termin), einarbeiten der Korrekturen |
| Sonntag, 25. Oktober 2015 | Abgabe der korrigierten Gliederung | |
| 44-47 | 4 (7) | Besprechung der korrigierten Gliederung (individueller Termin), Erstellung der Ausarbeitung |
| Sonntag, 22. November 2015 | Abgabe der Ausarbeitung | |
| 48-49 | 2 (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 | |
| 51 | 1 (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.