Sprungmarken

Servicenavigation

Fakultät für Mathematik

Hauptnavigation



Sie sind hier:

Bereichsnavigation



Hauptinhalt

Vorlesung "Kombinatorische Optimierung auf Graphen"

Aktuelles

  • Die Vorlesung beginnt am 19. Oktober 2016.
  • Die erste Übung findet in der zweiten Vorlesungswoche statt.
  • Achtung: Die Vorlesung am 25.1.2017 entfällt!

Allgemeine Informationen

Zeit und Ort:
  • Vorlesung:  Mi, 12.15-13.45 Uhr, Raum M/E25
  • Übung: Mi, 14:15-15:45, Raum M/E28, ab dem 26. Oktober 2016, alle zwei Wochen

Dozent / Übungen:
Dr-Ing. Moritz Mühlenthaler

Sprechstunde
nach Vereinbarung (per Email).

Prüfungsanmeldung
bei Sabine Willrich, M517

Gegenstand der Veranstaltung
In dieser Veranstaltung werden strukturelle Resultate und mathematische Methoden zur Lösung kombinatorischer Optimierungsprobleme auf Graphen behandelt, welche den in der Vorlesung Diskrete Optimierung vermittelten Stoff inhaltlich weiterführen und ergänzen. Die Veranstaltung ist so konzipiert, dass Diskrete Optimierung auch parallel gehört werden kann.

Folgende Themen werden behandelt:
  • kürzeste Wege
  • Flüsse in Netzwerken
  • globale minimale Schnitte
  • Matchings

Voraussetzungen
Die Vorlesung richtet sich vorrangig an Studierende der Diplom- und Masterstudiengänge Mathematik und Wirtschaftsmathematik. Voraussetzung für die Teilnahme an dieser Veranstaltung ist die erfolgreiche Absolvierung der Vorlesung Optimierung. Kenntnisse aus der Vorlesung Diskrete Optimierung sind erwünscht.

Übungsblätter

  • Blatt 1: Bäume, Grad, Zusammenhang, Adjazenzmatrizen (aktualisiert: 20.10.16)
  • Blatt 2: Kürzeste Wege, der Algorithmus von Ford, Inzidenzmatrizen
  • Blatt 3: Kürzeste Wege, Schnitte
  • Blatt 4: Flüsse
  • Blatt 5: Schnitte
  • Blatt 6: Schnitte und Matchings

Tutorial zu Python und Sage

Auf allgemeinen Wunsch wird es am 14.12. in dem Übungszeitslot von 12:15-13:45 Uhr eine Einführung in Python und Sage geben. Sage ist eine auf der Sprache Python basierende Mathematik-Software, die frei verfügbar ist, und viele einzelne freie Open-Source Mathematik-Bibliotheken unter einem gemeinsamen Dach vereint. Inhaltlich werden wir uns mit Python-Grundlagen und mit Algorithmen für kürzeste Wege beschäftigen.

  • Sie können Sage hier herunterladen (Vorsicht: das Paket ist etwa 1GB groß!)
  • Die Dokumentation zum Arbeiten mit Graphen in Sage finden Sie hier
  • Single-source shortest path (SSSP) Instanzen aus der DIMACs challenge finden Sie hier
  • Das Sage Notebook-Worksheet zum Tutorial finden Sie hier. Um es zu laden, müssen Sie das Sage Notebook starten (notebook() in sage aufrufen). Das entsprechende pdf ist hier.

Empfohlene Literatur zur Vorlesung

  • W Cook, W Cunningham, W Pulleyblank, A Schrijver. "Combinatorial Optimization". Wiley and Sons, 1998.
  • A Schrijver. "Combinatorial Optimization: Polyhedra and Efficiency", Volumes A, B, Springer, 2003.
  • R Ahuja, T Magnanti, and J Orlin. "Network Flows: Theory, Algorithms, and Applications". Prentice Hall, 1993.
  • D Williamson. "Lecture Notes on Network Flow Algorithms". Technical Report 1460, Cornell University, 2004
  • R Diestel. "Graph Theory". Springer, 2016, (siehe free preview)


Links

Fakultät für Mathematik
TU Dortmund