Diese Veranstaltung ist die begleitende Übung zur Vorlesung Algorithmen und Datenstrukturen aus dem WS 2010/2011.

• Die Übungen finden 14-tägig, dafür aber 3-stündig statt (4 x 45 min). Die 2 Termine sind:
  • Di 16.00 Uhr - 19.00 Uhr (OH14 Raum 104)
  • Do 16.00 Uhr - 19.00 Uhr (OH14 Raum 104)
  • Beginn beider Übungsgruppen um 16.00 Uhr – nicht 16.15 Uhr!
• Beginn der Vorlesungen: Di 12.10.
• Beginn der Übungen: Di 26.10. bzw. Do 28.10.. Die Anmeldung zu den Übungen erfolgt in der 1. Vorlesungswoche.

Es gibt einen EWS-Arbeitsraum zu dieser Übung. Für den internen Bereich ist eine separate Anmeldung und Freischaltung notwendig.

Diese Vorlesung mit der begleitenden Übung gibt einerseits die Grundlagen für die meisten weiterführenden Spezialvorlesungen im Bereich Algorithmische und formale Grundlagen, zum anderen behandelt sie weiterführende und komplexere Algorithmen und Datenstrukturen. Sie kann als Weiterführung von DAP2, mit fast leerer Überschneidung zu Effiziente Algorithmen gesehen werden. Im Einzelnen werden die folgenden Themen behandelt:

• Komplexe Datenstrukturen und deren Analyse, wie z.B. Fibonacci-Heaps
• Strings, z.B. Suffix Trees, Suffix Arrays, Pattern Matching
• Lineare Programmierung: Modellierung, Dualität, Simplexalgorithmus
• Ganzzahlige Lineare Programmierung: z.B. Gomory
• Kombinatorische Optimierung, z.B. primal-duale Algorithmen, Branch-and-Cut
• Approximationsalgorithmen, z.B. Set Cover
• Graphenalgorithmen: z.B. Flussalgorithmen, Minimaler Schnitt, bipartites Matching
• Geometrische Algorithmen: z.B. konvexe Hülle
• Analysemethoden, wie z.B. amortisierte Analyse

Bei Fragen zu der Übung bitte an Bernd Zey wenden (eMail: Bernd.Zey (at) tu-dortmund.de oder einfach vorbei kommen).