zum Inhalt springen

Vorlesung und Übungen "Effiziente Algorithmen"

Dozent: Dr. Daniel Schmidt

Termine

  • Di 12-13:30 Uhr im HS II, Physikalische Institute
  • Do 12-13:30 Uhr im HS II, Physikalische Institute

Beginn: Dienstag, 02. April 2019

Inhalte

In der Vorlesung behandeln wir Algorithmen für Probleme der kombinatorischen Optimierung, die mit effizienten Algorithmen lösbar sind. Nach einer kurzen Einführung in die Dualitätstheorie werden u.a. die folgenden Themen behandelt: minimal aufspannende Bäume, kürzeste Wege, maximale Flüsse, Flüsse mit minimalen Kosten, Kardinalitätsmatchings in bipartiten und allgemeinen Graphen.

Voraussetzungen

Grundlagen der Mathematik und Informatik wie im Bachelorstudium (erfolgreiche Teilnahme am Programmierkurs, Grundzüge der Informatik I+II sowie dem Programmierpraktikum) vermittelt, insbesondere aus den Bereichen der Algorithmik, Komplexitätstheorie und -analyse, der linearen Algebra sowie der Geometrie.

ILIAS-Kurs

Das Vorlesungsmaterial wird im ILIAS-Kurs zur Vorlesung zur Verfügung gestellt. Der Beitritt erfolgt über Anfrage oder durch Anmeldung in KLIPS zur Vorlesung.

Übungen zu "Effiziente Algorithmen" (gemeinsam mit Christiane Spisla)

In den Übungen zur Vorlesung "Effiziente Algorithmen" wird der Vorlesungsstoff vertieft. Schriftliche Übungsaufgaben werden unter Anleitung eines Tutors besprochen.

Um die Zulassung zur Klausur zu erhalten müssen mindestens 50% der möglichen Übungspunkte erreicht werden.

Übungsgruppen:

  • Mo, 10-11.30 Uhr, Hörsaal XXXI/Alte Botanik
  • Mo, 14-15.30 Uhr, Hörsaal XXXI/Alte Botanik
  • Mi, 14-15.30 Uhr, Hörsaal XXXI/Alte Botanik
  • Do, 16-17.30 Uhr Hörsaal XXXI/Alte Botanik

Die ersten Übungen finden vom 23.04.2019 bis 25.04.2019 statt.

Anmeldung zu den Übungsgruppen

Ist abgeschlossen. Die Einteilung wird im ILIAS-Kurs bekannt gegeben.

Klausur (Dauer 180 Minuten):

  • Hauptklausur: 16.07.2019, 14:30 Uhr, Chemie I-III
  • Nachklausur: 10.09.2019, 13:15 Uhr, Physik I-III

Die Zulassung zur Klausur muss in den Übungen erworben werden.

Literatur

Cook, Cunningham, Pulleyblank und Schrijver: Combinatorial Optimization. Wiley 1998. E-Book im Netz der Universität erhältlich.