Mathematische Methoden der Algorithmik

Vorlesung: Dienstag, 9:45 - 11:15, IZ 305.

Übung: Mittwoch, 15:00 - 16:30, IZ 305.

Studienleistung: Erreichen von mindestens 50 Prozent der Hausaufgabenpunkte.

Prüfungsleistung: Mündliche Prüfung oder Klausur.

Das Modul behandelt die lineare und ganzzahlige Optimierung. Die Studierenden erlernen, gegebene Probleme als lineare Programme zu formulieren und zu lösen, sowie die theoretischen Aspekte dahinter:

1. Lineare Optimierung
2. Simplexalgorithmus
3. Dualität
4. Ganzzahlige Optimierung

Die Hauptreferenz für diesen Kurs ist Linear Programming: Foundations and Extensions von Robert J. Vanderbei (SpringerLink). Es gibt aber noch deutlich mehr Literatur zu den Themen dieses Kurses.

1. Matousek and Gärtner: Understanding and Using Linear Programming (Springer).
2. A. Schrijver: Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, 1998 (s-tlip-98, BibTeX)
3. V. Chvátal: Linear Programming, Series of Books in the Mathematical Sciences, W.H. Freeman, 1983 (c-lp-83, BibTeX)
4. Einführung in die Mathematische Optimierung - Burkard und Zimmermann Freier Zugang im Uni-Netzwerk.

Mailingliste

Bei Interesse meldet Euch bitte auf jeden Fall auf der Mailingliste an!

Material

Hier werden die Vorlesungsmaterialien veröffentlicht (in der Regel spätestestens einen Tag nach der Vorlesung).

Vorlesung 00: Intro [pdf]

Vorlesung 01: Simplex-Algorithmus [pdf]

Vorlesung 02: Fundamentalsatz [pdf]

Vorlesung 03: Dualität I [pdf] [Notizen]

Vorlesung 04: Dualität II [pdf]

Vorlesung 05: Matrix Notation [pdf] [Beispiel]

Vorlesung 06: Implementationen [pdf]

Vorlesung 07: Allgemeine LPs[pdf]

Vorlesung 08: Integer Programming [pdf]

Vorlesung 09: Graphenprobleme [pdf]

Vorlesung 10: Matching Polytop [pdf]

Vorlesung 11: Traveling Salesman Problem [pdf]

Vorlesung 12: Zusammenfassung [pdf]

Tutorials

• Übung 1: Lineare Algebra, Modellierung [pdf]
• Übung 2: Dualität, Komplementärer Schlupf [pdf]
• Übung 3: Phase 1, Bipartite Matchings [pdf]
• Übung 4: Allgemeine LPs, Recap [pdf]

Hausaufgaben

Hier werden die Hausaufgabenblätter veröffentlicht.

• Blatt 1, Abgabe 13.11.24, 15 Uhr: [pdf]
• Blatt 2, Abgabe 27.11.24, 15 Uhr: [pdf]
• Blatt 3, Abgabe 11.12.24, 15 Uhr: [pdf]
• Blatt 4, Abgabe 08.01.25, 15 Uhr: [pdf]

Klausur

Die Klausur findet am 14.03.25 von 13-15 Uhr im Raum PK 11.2 statt. Bitte seid 15 Minuten vorher anwesend. Benötigt wird ein dokumentenechter Stift und der Studierendenausweis. Eigenes Papier oder Unterlagen sind nicht erlaubt.