Mathematische Algorithmen
Informationen
Das Modul ist ein Pflichtmodul für den Master "Information Systems Engineering".
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
Die Referate nehmen einen wichtigen Stellenwert ein. Sie werden als ein Bestandteil des Praktikums gewertet, d.h. für jeden Teilnehmenden ist ein Referat Pflicht. Dabei soll nicht nur die Fachvermittlung sondern auch die Vortragstechnik geschult werden. Daher gibt es nach den einzelnen Referaten Feedback zu den Vorträgen. Zum Vortrag gehört eine Ausarbeitung (ca. 5 bis 15 Seiten).
Die Referate werden über das Semester verteilt. Die Einteilung wird in der ersten Veranstaltung besprochen.
Die Referate werden benotet; die Note bildet 20% der Gesamtnote des Moduls. 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%) für das Modul gesammelt werden.
Prüfung
Eine abschließende Prüfung wird in schriftlicher Form durchgeführt und bildet 70% der Gesamtnote des Moduls.
Termine
Die Veranstaltung findet im Sommersemester 2024 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, 05.04.. Dort wird die weitere Organisation und die Verteilung der Referate besprochen; ferner ist dann auch die Anmeldung zum Praktikum möglich.
Unterlagen
Hier gibt es die Unterlagen und Aufzeichnungen zur Veranstaltung:
- 05.04.:
- 12.04.: Lineare Optimierung
- Skript
- Einführende Beispiele
- Übungsblatt 1: Aufgaben, Lösungen
- Aufzeichnungen:
- 19.04.:
- Ganzzahlige lineare Optimierung:
- Aufzeichnung
- Übungsblatt 2: Aufgaben, Lösungen
- Branch&Bound
- Bemerkung zum Praktikum und zu den Referaten
- Minimal spannende Bäume - Algorithmen von Prim und Kruskal:
- Ausarbeitung
- Folien: Prim, Kruskal
- Aufzeichnung
- Ganzzahlige lineare Optimierung:
- 26.04.:
- Bäume und Schnitte:
- Optimalitätskriterien für MST:
- Ausarbeitung (auch mit den Algorithmen von Prim und Kruskal)
- Folien: Kreiskriterium, Schnittkriterium
- Aufzeichnung: Kreiskriterium, Schnittkriterium
- Übungsblatt
- 03.05:
- Übungsaufgaben zum MST und Nachtrag
- hamiltonsche Graphen: Aufzeichnung und Folien
- TSP:
- Weitere Erläuterungen
- 17.05.:
- Weiteres zu TSP:
- Gerichtete Graphen:
- 24.05.:
- Nachtrag zu TSP
- Kürzeste Wege
- Folien Teil 1, Teil 2 (aktualisiert), Teil 3
- Ausarbeitung (alle Teile)
- Übungsblatt
- Aufzeichnung: Teil1 zum Ersten, Teil1 zum Zweiten, Dijkstra-Alg., Moore-Bellman-Ford-Alg.
- 31.05.:
- Übungen zu kürzesten Wegen
- Maximale Flüsse:
- 07.06.:
- weitere Übungen zu kürzesten Wegen
- Übungen zu maximalen Flüsse
- Maximale Flüsse:
- 14.06.:
- Nachträge zu maximalen Flüssen
- Kostenminimale Flüsse:
- Folien Teil 1, Teil 2, Teil 3
- Ausarbeitung Teil 1, Teil 2, Teil 3
- Aufzeichnung: Teil 1, Teil 2 (CCA), Teil 3 (SSP)
- 21.06.:
- Planarität:
- Folien Teil 1, Teil 2, Teil 3
- Ausarbeitung zu Teil 1 und Ausarbeitung zu Teil 1, 2 und 3
- Aufzeichnung: Teil 1 (leider vergessen, den Startknopf zu drücken), Teil 2, Teil 3
- Planarität:
- 28.06.:
- Matchings:
- Folien
- Übungsblatt
- Ausarbeitung
- Aufzeichnung: Teil 1, Teil 2, Teil 3
- Matchings:
- 05.07:
- Übungen zu Matchings
- Färbung:
- Folien
- Ausarbeitung
- Aufzeichnung: Teil 1, Teil 2
- Probeklausur und Lösung