Aktuelles

Die erste Vorlesung findet am Donnerstag, 07. April, 8:30 Uhr in Seminarraum 25.22.U1.72 statt.

Materialien

Vorlesungs- und Übungsmaterialien werden im ILIAS zur Verfügung gestellt.

Dozierende

Prof. Dr. Melanie Schmidt

Studiengang

Master-Studiengang Informatik

Leistungspunkte

5 LP ab PO 2015, alte PO's 7,5 LP für Vorlesung und Übung

Lehrveranstaltungen

• Vorlesungen
  • Do 8:30 Uhr - 10:00 Uhr in 25.22.U1.72
• Übungen
  • Do 10:30 Uhr - 12:00 Uhr in 25.12.02.33
  • Do 12:30 Uhr - 14:00 Uhr in 25.22.U1.72

Inhalte

Dieses Modul befasst sich mit den folgenden schweren Optimierungsproblemen, für die es vermutlich keine effizienten Algorithmen gibt, und stellt verschiedene Ansätze zum Finden von Näherungslösungen für diese Probleme vor.

• Grundlagen
• Metric Traveling Salesman
• Job Scheduling
• Knapsack
• Bin Packing
• Steiner Tree
• Weighted Vertex Cover

Lernergebnisse/Kompetenzen

Studierende sollen nach Absolvierung der Lehrveranstaltungen in der Lage sein,

• die besprochenen schweren Optimierungsprobleme zu erläutern und formal zu definieren
• die behandelten Approximationsalgorithmen zu verstehen und auf konkrete Eingaben anzuwenden
• die Optimierungsprobleme bekannten Komplexitätsklassen zuzuordnen
• Beweise für die Approximationsgüte von Approximationsalgorithmen zu durchschauen

Literatur

• G. Ausiello, P. Crescenzi, G. Gambosi, et al.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer Verlag, 1999.
• K. Jansen, M. Margraf: Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter Verlag, 2008.
• V. Vazirani: Approximation Algorithms, Springer Verlag, 2003.
• R. Wanka: Approximationsalgorithmen, Teubner Verlag, 2006.

Verwendbarkeit des Moduls

• Wahlpflichtbereich Theoretische Informatik
• Schwerpunktbereich
• Individuelle Ergänzung
• Anwendungsfach für den Ergänzungsbereich im Master-Studiengang Mathematik

Teilnahmevoraussetzungen

Bachelor-Studierende müssen folgende Module erfolgreich abgeschlosseGraphn haben:

• „Programmierung”
• „Rechnerarchitektur“
• „Algorithmen und Datenstrukturen”
• „Theoretische Informatik”

Voraussetzungen für die Vergabe von Leistungspunkten

• Aktive Mitarbeit in den Übungen, Abgabe der Übungsaufgaben, Bestehen der Prüfung zum Ende des Semesters