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

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.

• Turnus: wöchentlich
• Dauer: 2-stündig (2×45 Minuten)
• Beginn: KW17 (22.-25.4.) Ostermontag ist Feiertag (s.u.)
• Termine:
  • Montag 10-12 Uhr / OH12 3.031 MSW16 E31 Raumänderung ab dem 23.06.
  • Dienstag 12-14 / OH14 E02
  • Freitag 10-12 / OH16 205
    • Solange der Raum 205 renoviert wird, findet die Übung im Hörsaal OH14 E23 statt.
    • Ab KW 27 findet die Übung wieder im OH16 Raum 205 statt.

Die Teilnehmer der betroffenen Übungen haben die Möglichkeit eine der anderen Übungen in der gleichen Woche zu besuchen.

Falls ein Übungsschein benötigt wird, sollten die folgenden Dinge beachtet werden:

• Kann keine der anderen Übungen besucht werden, so gilt eine schriftliche Abgabe ebenfalls als aktive Teilnahme.
• Wird eine andere Übung besucht, so muss auf der Teilnehmerliste eingetragen werden, welcher Übungsgruppe man im Regelfall angehört.

• Die Übungsgruppeneinteilung erfolgt über das AsSESS-System. (Anmeldung aktuell noch nicht freigeschaltet!)
• Die Anmeldefrist ist der 15.04.2013 (23:59 Uhr). Nachmeldungen können nur noch nach Absprache per E-Mail (Till Schäfer) erfolgen.

Die Materialien zu der Übung (inkl. der Übungsblätter) finden Sie im EWS-Arbeitsraum.

• 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

Wer Diplom Informatik studiert und den Übungsschein erhalten möchte (nicht notwendig für die Zulassung zur Prüfung), muss folgende Kriterien erfüllen:

• 4 Abgaben mit insgesamt mind. 50% der Punkte
• aktive Teilnahme: mind. 50% der Aufgaben auf der Anwesenheitsliste als bearbeitet markiert.

Wenn Sie Fragen haben, dann wenden Sie sich bitte an Till Schäfer.