Vorlesung: Approximationsalgorithmen (B-ApA, M-ApA) (WS 2018/2019)

Vorlesung über 3 SWS aus dem Bachelorstudiengang und dem Masterstudiengang 2008 mit Übungen über 2 SWS (8 Credits).

Vorlesung: Approximationsalgorithmen 1 (ApA1) (WS 2018/2019)

Vorlesung: Approximationsalgorithmen 2 (ApA2) (WS 2018/2019)

Vorlesungen über je 2 SWS aus dem Masterstudiengang 2015 mit Übungen über je 1 SWS (je 5 Credits).

Approximationsalgorithmen 1 findet in der ersten Hälfte der Vorlesungszeit statt (ca. 8 Wochen), die optionale Fortsetzungsveranstaltung Approximationsalgorithmen 2 in der zweiten Hälfte (ca. 7 Wochen).

Vorlesung

Dr. Annamaria Kovacs (Raum 305)

Mittwoch 12:00–14:00 in SR 9 (R-M-S 11–15)
Donnerstag 12:00–14:00 in SR 11 (R-M-S 11–15)

Übungsbetrieb

Mahyar Behdju (Raum 311)

Gruppe 1 Dienstag 12:00 - 14:00, SR 307 (R-M-S 11–15)
Gruppe 2 Dienstag 14:00 - 16:00, SR 11 (R-M-S 11–15)

Übungsblätter werden in der Regel wöchentlich mittwochs ausgegeben.
Die Abgabe erfolgt in der darauffolgenden Woche vor der Vorlesung.
Alternativ steht der Briefkasten vor Raum 312 für eine vorzeitige Abgabe zur Verfügung.
Einreichungen per E-Mail werden nur als ordentlich-formatiertes PDF-Dokument (z.B. mittels Latex) akzeptiert.

Die Teilnahme am Übungsbetrieb wird dringend empfohlen, ist jedoch nicht verpflichtend.
Durch die Aufgaben wird Bekanntes vertieft und weiterführende Inhalte vermittelt.
Des Weiteren kann durch das Lösen der Aufgaben eine Bonifikation von bis zu einem Notenschritt für die Prüfung erworben werden.
Eine Voraussetzung dafür ist das Vorrechnen mindestens einer Übungsaufgabe im Tutorium.
Die Bonifikation wird erst angerechnet, wenn die Klausur selbstständig bestanden wurde.

Die Bearbeitung der Aufgaben in Gruppen wird begrüßt, jedoch muss von jedem Teilnehmer eine individuelle Ausarbeitung eingereicht werden.
Blätter, auf denen plagiierte oder kopierte Lösungen gefunden werden, werden für jeden Betroffenen nicht bewertet.
Im Wiederholungsfall kann es zur Aberkennung sämtlicher Bonifikation kommen.

Inhalt

Die Veranstaltung befasst sich mit verschiedenen Algorithmenklassen und deren Analyse. Hierzu gehören:

• Greedy-Algorithmen und Heuristiken
• Dynamische Programmierung
• Lokale Suche
• Branch & Bound
• Lineare Programmierung

Dabei werden Approximationsalgorithmen für fundamentale Probleme, wie etwa Bin Packing, Scheduling-, Clustering- und Graph-Probleme, untersucht.

Literaturhinweise

• Vijay V. Vazirani: Approximation Algorithms, Springer, 2001
• David P. Williamson, David B. Shmoys: The Design of Approximation Algorithms, Cambridge University Press, 2011
• Dimitris Bertsimas, John N. Tsitsiklis: Introduction to Linear Optimization, Athena Scientific, 1997
• Christopher Moore, Stephan Mertens: The Nature of Computation, Oxford University Press, 2013, Kapitel 9, S. 351–449
• Klaus Jansen, Marian Margraf: Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter, 2008
• Rolf Wanka: Approximationsalgorithmen – Eine Einführung, Teubner, 2006

Leistungsnachweise

Die Erstklausur findet am 08.03.2019 statt (Raum und Uhrzeit werden noch bekannt gegeben).

Ressourcen

Materialien für Studierende befinden sich hier.