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.