Approximationsalgorithmen (WS 2017/2018)

Vorlesung

Dr. Annamaria Kovacs

Mittwoch 12:00–14:00 in Magnus Hörsaal (R-M-S 11–15)
Donnerstag 12:00–14:00 in SR 11 (R-M-S 11–15)

Übungsbetrieb

Hung Tran, Donnerstag 14:00–16:00 in SR 11 (R-M-S 11–15)

Dipl-Math. Mahyar Behdju, Donnerstag 16:00–18:00 in SR 11 (R-M-S 11–15)

Übungsblätter werden i.d.R. 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.

Sprache

Die Vorlesung wird in deutscher Sprache gehalten.

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

Leistungsnachweise

Klausurtermin: Montag, 26.02.2018, 10.00 Uhr (s.t.), in H I (Hörsaalgebäude)
Zweitklausurtermin: Dienstag, 10.04.2018, 14.00 Uhr (s.t.), in H IV (Hörsaalgebäude)

Materialien

Folien

Beachten Sie, dass die Folien nicht den gesamten Vorlesungsinhalt abdecken. Insbesondere werden Beweise an der Tafel ausgearbeitet. Das Mitschreiben der Tafelbilder wird empfohlen.

Approximationsalgorithmen 1

Approximationsalgorithmen 2

Skript

Approximationsalgorithmen 1

Approximationsalgorithmen 2

Übungen

Approximationsalgorithmen 1

Approximationsalgorithmen 2

Klausurmaterialien

Weitere Materialien

  • Es steht das Skript von Herrn Prof. Dr. Georg Schnitger zum Download bereit, an dem sich diese Veranstaltung orientiert.