Mathematische Algorithmen und Programmierung
Informationen
Das Modul ist ein Pflichtmodul für den Informatik-Master.
Vorlesungsinhalte
Die Vorlesung will verschiedene Ansätze zur mathematisch-algorithmischen Behandlung von Anwendungsproblemen vermitteln. Der Schwerpunkt liegt dabei auf Graphenalgorithmen, wobei aber auch andere Optimierungsverfahren angesprochen werden.
Insbesondere der graphenalgorithmische Teil soll seminaristisch durchgeführt werden, d.h. die Studierenden erarbeiten sich selbst ein Thema und stellen das dann vor. Grundlage dazu ist das Buch "Graphen- und Netzwerkoptimierung" von Christina Büsing, Spektrum-Verlag. Das Buch ist unter der Signatur 21 TVI 24 in der Bibliothek verfügbar.
Die vorgestellten Graphenalgorithmen sollen im Rahmen des Praktikums softwaretechnisch umgesetzt werden.
Referat
Optional gibt es die Möglichkeit, ein Referat zu halten und sich damit 20% der Gesamtnote schon während der Vorlesungszeit zu erarbeiten. Dabei soll nicht nur die Fachvermittlung sondern auch die Vortragstechnik geschult werden. Daher gibt es nach den einzelnen Referaten Feedback zu den Vorträgen.
Die Referate werden über das Semester verteilt. Die Einteilung wird in der ersten Veranstaltung besprochen.
Die genauen Modalitäten (und einen Zeitplan zur Vorbereitung) können Sie den Hinweisen entnehmen.
Mdl. Argumentieren
Ein Lernziel des Moduls ist, Argumente präzise formulieren und geäußerte Argumente analysieren zu können. Damit können Bonuspunkte (bis zu 10% der nicht durch Enthaltung erreichbaren Punkte) für das Modul gesammelt werden.
Prüfung
Eine abschließende Prüfung wird in schriftlicher Form durchgeführt.
Termine
Die Veranstaltung findet im Sommersemester 2026 freitags ab 8:15 Uhr im Raum E113 (in Präsenz) statt.
Zeiten zur Abnahme der Programmierpraktika sind jeweils im Anschluss oder nach Vereinbarung.
Die erste Veranstaltung ist am Freitag, 10.04.. Dort wird die weitere Organisation und die Verteilung der Referate besprochen; ferner ist dann auch die Anmeldung zum Praktikum. Eine explizite Anmeldung zur Vorlesung ist nicht nötig; kommen Sie einfach zur ersten Veranstaltung.
Unterlagen
Hier gibt es die Unterlagen und Aufzeichnungen zur Veranstaltung:
Aufzeichnungen:
- 28.03.:
- 17.04.: Lineare Optimierung
- 24.04.:
- Ganzzahlige lineare Optimierung:
- Aufzeichnung
- Übungsblatt 2: Aufgaben, Lösungen
- Branch&Bound
- Minimal spannende Bäume - Algorithmen von Prim und Kruskal:
- Einführung und Prim-Algorithmus: Konzeptpapier, Folien und Aufzeichnung
- Kruskal-Algorithmus und Union-Find-Struktur: Konzeptpapier, Folien und Aufzeichnung
- Ganzzahlige lineare Optimierung:
- 08.05:
- Bäume und Schnitte: Konzeptpapier, Folien, Aufzeichnung
- hamiltonsche Graphen: Konzeptpapier, Folien, Aufzeichnung Teil 1, Aufzeichnung Teil 2
- TSP Einführung und Nearest-Neigbour-Alg.: Konzeptpapier, Folien, Aufzeichnung
- Doppelter-Baum-Algorithmus: Konzeptpapier, Folien, Aufzeichnung
- Branch&Bound: Aufzeichnung
- 22.05.:
- Schnitte - Übungen: Aufzeichnung
- Optimalitätskriterien für MST: Konzeptpapier, Folien, Aufzeichnung
- Ergänzungen zu MST: Aufzeichnung
- Ergänzungen zu TSP, hamiltonsch und Komplexitätsklassen: Aufzeichnung, Folien zur Komplexität
- Übungsblatt
- 29.05.:
- Übungen, Folien zu TSP als LP
- Kürzeste Wege:
- Einführung, kürzeste-Wege-Baum, Dreiecksungleichung und Optimalitätskriterium: Konzeptpapier, Folien, Aufzeichnung
- Dijkstra-Algorithmus: Konzeptpapier, Folien, Aufzeichnung
- Negative Kantenkosten: Konzeptpapier, Folien, Aufzeichnung
- Moore-Bellman-Ford-Algorithmus: Konzeptpapier, Folien, Aufzeichnung
- Übungsblatt
- 05.06:
- Übungen
- Gerichtete Graphen:
- Einführung, starker Zusammenhang: Konzeptpapier, Folien, Aufzeichnung
- Hamiltonwege und Könige in Turniergraphen: Konzeptpapier, Folien, Aufzeichnung
- Übungsblatt
- 12.06.:
- Maximale Flüsse:
- Einführung: Konzeptpapier, Folien, Aufzeichnung
- Residualgraph, Algorithmen von Ford-Fulkerson und Edmonts-Karp: Konzeptpapier, Folien zum Residualgraph, Folien zum Algorithmus von Ford-Fulkerson, Folien zum Algorithmus von Edmonds-Karp, Aufzeichnung zum Residualgraph, Aufzeichnung zum Algorithmus von Ford-Fulkerson, Aufzeichnung zum Algorithmus von Edmonds-Karp
- Max-Fluss-min-Schnitt-Satz: Konzeptpapier, Folien, Aufzeichnung
- Übungsblatt
- Maximale Flüsse:
- 19.06.:
- Maximale Flüsse:
- Einführung: Konzeptpapier, Folien, Aufzeichnung
- Negative Zykel: Konzeptpapier, Folien, Aufzeichnung
- Cycle-Canceling-Algorithmus: Konzeptpapier, Folien, Aufzeichnung
- Kostenoptimale Wege: Konzeptpapier, Folien, Aufzeichnung
- Successive-Shortest-Path-Algorithmus: Konzeptpapier, Folien, Aufzeichnung
- Übungsblatt
- Maximale Flüsse:
- Probeklausur und Lösung
Links
Hier erscheinen Links zur Vorlesung: