Netzwerkalgorithmen

1. Aufspannende Bäume
2. Kürzeste Wege
3. Maximale Flüsse
4. Kostenminimale Flüsse
5. Kardinalitätsmaximales Matching

Aktuelles

• Die Vorlesung startet in der zweiten Semesterwoche, also am 13. April; die erste große Übung findet das erste Mal in der vierten Semesterwoche, also am 24. April statt.
• Das erste Hausaufgabenblatt ist draußen. Abgegeben werden kann das Blatt bis zum 02. Mai 2017 um 13:15 Uhr im Hausaufgabenabgabeschrank der Algorithmik.
• Aufgrund der geringen Teilnehmerzahl kann der Slot am Mittwoch für die kleine Übung nicht mehr angeboten werden. Alle davon betroffenen bitte ich sich in eine der beiden anderen Übungen am Donnerstag zu setzen.
• Die erste kleine Übung findet am 11.05.2017 statt.
• Der Algorithmus von Kruskal zur Bearbeitung von Aufgabe 5 auf Hausaufgabenblatt 1 wird in der Vorlesung am 27.4. besprochen und analysiert. Falls ihr mit der Bearbeitung der Aufgabe nicht so lange warten wollt, findet ihr den Algorithmus hier als Bild.
• Die Hausaufgaben müssen von jedem Teilnehmer und jeder Teilnehmerin einzeln abgegeben werden. Gruppenabgaben werden mit null Punkten bewertet.
• Es gab eine kleine Verwirrung wegen des Raumes der kleinen Übung am Donnerstag um 16:45 Uhr. Diese findet NICHT im IZ358 sondern im IZ305 statt. Bitte entschuldigt, die Räume haben sich zwischenzeitlich geändert.
• Am Montag, den 22.05.2017 findet die zweite kleine Übung im Slot der großen Übung um 11:30 Uhr in PK4.1 statt. Die kleine Übung und die Vorlesung am 25.05.2017 fallen aufgrund von Christi Himmelfahrt aus. Am 29.05.2017 findet die große Übung statt.
• Die Vorlesung vom 29.06. wird auf den Slot der großen Übung am 26.06. vorverlegt! Die Vorlesung findet deshalb auch in PK4.1 statt!
• Aufgrund des TDSE kann die letzte kleine Übung am 13.07. nicht stattfinden und wird deswegen auf den Slot der großen Übung am 10.07. vorverlegt. Die Übung findet dann im PK4.1 statt. Ob und wann noch eine Fragestunde stattfindet, klären wir in der letzten großen Übung am 03. Juli. Diese wird dann voraussichtlich in der vorlesungsfreien Zeit stattfinden und so organisiert sein, dass vorher Fragen per Mail gestellt und dort dann beantwortet werden.
• In der Übung am 19.06. wird für das kommende Aufgabenblatt relevanter Vorlesungsstoff über das Thema Matching vorgezogen!
• Algorithmus 5.15 (Maximales Matching in bipartiten Graphen) wird für Aufgabe 1 auf Hausaufgabenblatt 5 gebraucht. Da der Algorithmus vermutlich erst in der Vorlesung am 06.07.17 vorgestellt wird, findet ihr diesen vorab zur Bearbeitung der Hausaufgaben hier (Aufgrund eines Fehlers im Algorithmus entfernt!).
• Die erste Aufgabe von Aufgabenblatt 5 (Maximales Matching in bipartiten Graphen) wird aus der Gesamtwertung genommen; es gibt also nur noch 290 Punkte maximal zu erreichen. Falls ihr die Aufgabe dennoch bearbeitet, bekommt ihr die erreichten Punkte dafür zusätzlich gutgeschrieben.
• Die Liste mit den Matrikelnummern derjenigen, die die Studienleistung bestanden haben, findet ihr hier (ohne Gewähr!). Wir leiten die Liste in den nächsten Tagen an die jeweiligen Prüfungsämter weiter.
• Informationen zur Klausur findet ihr weiter unten im Abschnitt Klausur.
• Hier noch einmal die korrigierte Version vom Algorithmus 5.15 (Maximales Matching in bipartiten Graphen). Dies ist auch die Version, die in der letzten Vorlesung am 13.07. vorgestellt und durchgerechnet wurde.
• Die nicht abgeholten Hausaufgaben liegen im Büro IZ314 zur Abholung bereit. Hausaufgaben die bis zum 04. August 2017 nicht abgeholt wurden, werden eingelagert und irgendwann vernichtet.
• In den Folien zur dritten Übung waren zwei Kanten im Graphen für den Moore-Bellman-Ford Algorithmus vertauscht. Die Folien sind aktualisiert! Besten Dank an Thorsten für den Hinweis!
• Die Klausurergebnisse findet ihr unten im Klausurbereich!
• Informationen zur Wiederholungsprüfung im Wintersemester 2017/2018 findet ihr weiter unten!

Große Übung

• Tutorial 1 vom 24.04.2017. (Rückblick und Ausblick.)
• Tutorial 2 vom 08.05.2017. (MST und andere Baumprobleme.)
• Tutorial 3 vom 29.05.2017 (aktualisiert am 25.07.17). (Kürzeste Wege, Hamiltonkreis, TSP, Hamiltonpfad.)
• Tutorial 4 vom 19.06.2017. (Matching und MetricTSP.)
• Tutorial 5 vom 03.07.2017. (MaxFlow, Briefträgerproblem, Gomory-Hu, Circulation-Problem.)

Hausaufgaben

• Hausaufgabenblatt 1; Abgabe bis Dienstag, den 02. Mai 2017 um 13:15 Uhr.
• Hausaufgabenblatt 2; Abgabe bis Montag, den 15. Mai 2017 um 13:15 Uhr.
• Hausaufgabenblatt 3; Abgabe bis Montag, den 29. Mai 2017 um 13:15 Uhr.
• Hausaufgabenblatt 4; Abgabe bis Montag, den 19. Juni 2017 um 13:15 Uhr.
• Hausaufgabenblatt 5; Abgabe bis Montag, den 03. Juli 2017 um 13:15 Uhr. (A1 wird gestrichen! Siehe "Aktuelles".)

Prüfung im Wintersemester 2017/2018

Klausur

Die Klausureinsicht wird am 10.08.2017 von 13:00 bis 14:00 Uhr im Raum IZ313 (Besprechungsraum der Algorithmik) stattfinden. Bitte bringt euren Studierendenausweis und einen Personalausweis mit.

Klausurergebnisse (ohne Gewähr) (Stand 10.08.17)

Mailingliste

Es wird eine Mailingliste zu dieser Vorlesung geben. Bitte meldet euch da an, denn wir werden sie nutzen, um kurzfristig Informationen zu verteilen. Bei technischen Schwierigkeiten wendet euch bitte an Christian Rieck.