Die Veranstaltung entspricht auch der auslaufenden Vorlesung “Effiziente Algorithmen und Komplexitätstheorie” im Diplomstudiengang Informatik / Angewandte Informatik als Wahlpflichtveranstaltung sowie dem Modul MD V “Effiziente Algorithmen” im Master Datenwissenschaften.
Vorlesung:
Dienstag, 10:15-11:45 Uhr, OH14 E23
Donnerstag 12:15-13:45 Uhr, OH14 E23
Beginn der Vorlesungen: Di, 05.04.
Übungen: jede 2. Woche, dafür 3-stündig
Termine: Montag, Dienstag, Mittwoch, Donnerstag, jeweils 14.00-17.00 Uhr
Beginn der Übungen: 18.04.
Informationen zu den Übungen finden Sie
hier
Lehramt
mündliche Prüfung, 20 oder 45 Minuten, je nach Prüfungsordnung und Prüfungsanmeldung
Stoff der Vorlesung und der Übungen
Die in DAP 2 eingeführten Basistechniken werden vertieft und auf komplexere Probleme angewendet, hinzu kommen ausgewählte Probleme mit großen Anwendungsbereichen, weitergehende Aspekte wie Approximation und weitergehende Entwurfsmethoden wie primal-duale Ansätze. Themen, u.a.:
Graphenalgorithmen, wie z.B. starker Zusammenhang in Graphen, Maximale Matchings, Netzwerkflussprobleme, Schnittprobleme (Min Cut vs. Max Cut), Travelling Salesman Problem, Vertex Cover
Analysetechniken, wie z.B. Amortisierte Analyse von Algorithmen, Analyse randomisierter Algorithmen
Optimierungstechniken, wie z.B. Lineare Programmierung, Approximationsschemata, parametrisierte Komplexität
Hashing Verfahren, String Matching
Weitere Informationen: s. Modulbeschreibung.
Die Vorlesungsfolien und begleitende Materialien sind im EWS Arbeitsraum zu finden.
