Diese Veranstaltung ist die begleitende Übung zur Vorlesung Effiziente Algorithmen aus dem SS 2011.

Die Vorlesung zur Veranstaltung entspricht auch der auslaufenden Vorlesung “Effiziente Algorithmen und Komplexitätstheorie” im Diplomstudiengang Informatik / Angewandte Informatik als Wahlpflichtveranstaltung sowie dem Modul MD V im Master Datenwissenschaften.

• Vorlesung: Di 10:15-11:45 Uhr + Do 12:15-13:45 Uhr, OH14 E23
• Beginn der Vorlesungen: Di, 05.04.
• Übungen:
  • jede 2. Woche, dafür 4-stündig
    • Die Übungen finden demnach in der 16., 18., 20., 22., 24., 26. und 28. Kalenderwoche statt
  • Montag, 14.00-17.00 Uhr, OH16 U08
  • Dienstag, 14.00-17.00 Uhr, OH16 U08
  • Mittwoch, 14.05-17.05 Uhr, OH16 U08
  • Donnerstag, 14.00-17.00 Uhr, OH16 U08
• Beginn der Übungen: 18.04.

Übungen, welche aufgrund von Feiertagen (oder anderen Terminen) blockiert werden, finden eine Woche später statt. Das betrifft:

• Die, 03.05. –> Die, 10.05. (FVV - Fachschaftsvollversammlung)
• Do, 02.06. –> Do, 09.06. (Christi Himmelfahrt)
• Mo, 13.06. –> Mo, 20.06. (Pfingsten)

Die Einteilung der Übungsgruppen ist nun verfügbar, siehe Übungsgruppen-Einteilung

• 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
• Analysetechniken, wie z.B. Amortisierte Analyse von Algorithmen, Analyse randomisierter Algorithmen
• Optimierungstechniken, wie z.B. Lineare Programmierung, Approximationsschemata
• Hashing Verfahren, String Matching, Hidden-Markov-Modelle