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. Die begleitende Übung ist für das Verständnis des Stoffes sehr wichtig.

• Vorlesung:
  • Dienstag, 10:15-11:45 Uhr, OH14 E23
  • Donnerstag 12:15-13:45 Uhr, OH14 E23
• Beginn der Vorlesungen: Dienstag, 03.04.
• Übungen: siehe begleitende Übungen

• Achtung: Für alle Prüfungen gilt: rechtzeitige Anmeldung bei Ihren Prüfungsämtern notwendig

• Bachelor Informatik / Angewandte Informatik
  • Klausur, 90 Minuten, keine Hilfsmittel
  • Klausurtermin: Donnerstag 19.07.2012 von 12:00 – 14:00 Uhr in OH14, E23
  • Wiederholungstermin: Montag 01.10.2012 von 12:00 – 14:00 Uhr in OH14, E23
  • Stoff der Vorlesung und der Übungen

• Diplom Informatik / Angewandte Informatik
  • mündliche Prüfung, 20 Minuten
  • Stoff der Vorlesung und der Übungen

• Master Datenwissenschaften
  • mündliche Prüfung, 20 Minuten
  • Stoff der Vorlesung und der Übungen

• Lehramt
  • mündliche Prüfung oder Klausur, 20 oder 45 Minuten, je nach Prüfungsordnung und Prüfungsanmeldung
  • Stoff der Vorlesung und der Übungen

• Sonstige Studiengänge / Nebenfächer auf Anfrage

• 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 finden Sie im EWS-Arbeitsraum.