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

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.

• Eine Selbsteinschreibung in Moodle ist nicht mehr möglich. Bitte schicken Sie eine Email an Andre Droschinsky, falls Moodle-Zugang zu diesem Kurs benötigt wird.

• Turnus: wöchentlich
• Dauer: 2-stündig (2×45 Minuten, Beginn c.t.)
• Beginn: 25.-27.04.2016, KW 17
• Termine (Tag, Zeit, Raum, Betreuer):
  • Montag 10-12 Uhr / OH14 E02 / Andre Droschinsky
  • Montag 14-16 Uhr / OH14 304 / Andre Droschinsky und SRG 1, R. 3.012 / Jens Zentgraf
  • Dienstag 14-16 Uhr / OH14 E02 / Jens Zentgraf und OH12, R. 3.030 / Andre Droschinsky
  • Mittwoch 14-16 Uhr / OH14 E02 / Ole Bergenholtz
  • Mittwoch 16-18 Uhr / OH14 E02 / Ole Bergenholtz

• Die Zuteilung zu den sieben Übungsgruppen ist im AsSESS einzusehen.

• Das erste Übungsblatt wurde vom 25.4. bis 27.4. besprochen.
• Das zweite Übungsblatt wurde vom 2.5. bis 4.5. besprochen.
• Das dritte Übungsblatt wurde vom 9.5. bis 11.5. besprochen.
• Das vierte Übungsblatt wurde vom 17.5. bis 18.5. besprochen.
• Das fünfte Übungsblatt wurde vom 23.5. bis 25.5. besprochen.
• Das sechste Übungsblatt wurde vom 30.5. bis 2.6. besprochen.
• Das siebte Übungsblatt wurde vom 6.6. bis 8.6. besprochen.
• Das achte Übungsblatt wurde vom 13.6. bis 15.6. besprochen.
• Das neunte Übungsblatt wurde vom 20.6. bis 22.6. besprochen.
• Das zehnte Übungsblatt wurde vom 27.6. bis 29.6. besprochen.
• Das elfte Übungsblatt wurde vom 04.07. bis 06.07. besprochen.
• Das zwölfte Übungsblatt wurde vom 11.07. bis 13.07. besprochen.
• Das dreizehnte Übungsblatt mit Besprechung vom 18.07. bis 20.07. ist jetzt in Moodle verfügbar.
• Ein “vierzehntes Übungsblatt”, eine Aufgabensammlung zum Thema String-Matching ist jetzt in Moodle verfügbar. Diese Aufgaben werden nicht in den Übungsgruppen besprochen. Bei Fragen wenden Sie sich an einen der Tutoren.

• 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 Andre Droschinsky.