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] [Notizen]

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]
• Übung 5: Branch-and-Cut [pdf]
• Übung 6: Modellierung, Cutting Planes [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]
• Blatt 5, Abgabe 22.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, ein Lineal (oder Geodreieck) und der Studierendenausweis. Eigenes Papier, Unterlagen oder andere Hilfsmittel sind nicht erlaubt.

Die Ergebnisse der Klausur sind da. Die Note kann TU-Connect entnommen werden. Dem [pdf] können Statistiken, sowie die Punktzahlen der eigenen Klausur entnommen werden. Zusammen mit der letzten Ziffer der Matrikelnummer plus die Note ist die Punktzahl (fast) eindeutig.

Die Einsicht soll am 20.03. um 13 Uhr im Raum IZ 313 stattfinden. Bitte gebt kurz eine Rückmeldung, ob ihr eure Klausur einsehen möchtet.