Abschnittsübersicht
-
Umfang: 5 ECTS, 2+2 SWS [T:2,P:0] Vorlesung: mittwochs, 10:15–11:45 Uhr, HS 2 (Nat.wiss. HS-Bau) Übungen: (1) freitags, 08:30–10:00 Uhr, SE I (Informatikgebäude)
(2) freitags, 10:15–11:45 Uhr, SE 8 (Physikgebäude)
(3) freitags, 12:15–13:45 Uhr, SE I (Informatikgebäude)Voraussetzung: Vorlesung Algorithmen und Datenstrukturen (dringend empfohlen) Zielgruppe: Bachelor Informatik ab 2. Semester Anmeldung: - Einschreibung hier in diesen Wuecampus-Kurs. (Klicken Sie dazu im Kursraum ganz oben links auf das Feld mit den weißen Zahnrädern auf blauem Grund und wählen Sie dann "Mich in diesem Kurs einschreiben" aus.)
- Die Anmeldung zur Klausur erfolgt über WueStudy (siehe auch das pdf zu allgemeinen Informationen weiter unten).
Dozent: Alexander Wolff Übungen: Samuel Wolf Tutoren: Thanh Mai Pham, Duy-Khang Tran, Antonio Lauerbach Klausuren: 1. Klausur: 30.07.2025, 10-12 Uhr im Turing Hörsaal und im Zuse Hörsaal
2. Klausur: voraussichtlich am 02.10.2025
Als Hilfsmittel ist nur ein einseitig handbeschriebenes Blatt (A4) zulässig.-
Diskussionsforum
-
Inhalt
Wir werden uns grob mit den folgenden Themengebieten der algorithmischen Graphentheorie auseinandersetzen:
- kürzeste Wege,
- Minimale Spannbäume,
- Rundreiseprobleme (Euler- und Hamiltonkreise),
- Flüsse,
- Modellierung mittels (ganzzahliger) linearer Programmierung,
- Matchings,
- planare Graphen,
- Färbbarkeit,
- Approximation und Fest-Parameter-Berechenbarkeit.
Lernziele
Am Ende dieses Kurses sind HörerInnen in der Lage typische Probleme der Informatik als Graphenprobleme zu modellieren. Außerdem können TeilnehmerInnen entscheiden, welche Werkzeuge aus der Vorlesung dabei helfen ein gegebenes Graphenproblem algorithmisch zu lösen. Studierende lernen in diesem Kurs vertieft die Laufzeit von gegebenen Graphalgorithmen abzuschätzen.
Weiterführende Veranstaltungen
- Vorlesung Algorithmische Geometrie (jedes WS)
- Vorlesung Approximationsalgorithmen (jedes WS)
- Vorlesung Advanced Algorithms (jedes WS)
- Vorlesung Visualisierung von Graphen (jedes SS)
- Vorlesung Exakte Algorithmen (jedes SS)
- Seminar Visualisierung von Graphen (o.ä., jedes WS)
Siehe auch unsere Veranstaltungsübersicht
-
Allgemeine Informationen zur Vorlesung und Übung Datei
-
Die Vorlesung basiert auf dem Buch Graphentheoretische Konzepte und Algorithmen von Sven Oliver Krumke and Hartmut Noltemeier (Vieweg+Teubner, 2. Auflage, 2009), das man sich aus dem Hochschulnetz hier kapitelweise herunterladen kann.
Außerdem setzt die Vorlesung einige Kapitel des Buchs Introduction to Algorithms (Algorithmen – eine Einführung) von Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein (MIT Press und McGraw-Hill, 3. Auflage, 2009 bzw. De Gruyter Oldenbourg, 4. Auflage, 2013) voraus (BFS, DFS, Algorithmus von Dijkstra, minimale Spannbäume).
Sehr intuitiv geschrieben ist Algorithmic Graph Theory von Alan Gibbons (Cambridge University Press, 1985).
In der folgenden Tabelle liefert ein Klick aufs jeweilige Datum die Kurz-/Druckversion der Folien; ein Klick aufs Thema die Langversion.
Datum Thema Videos (alt!) Literatur 23.04.2025 Organisation und Einführung Einführung (12') 23.04.2025 Rundreiseprobleme: Euler und Hamilton Euler (13'), Hamilton (14') 30.04.2025 Lineare Programmierung und Fluss LP und Fluss (30') 07.05.2025 Rundreiseprobleme III (TSP) Exakte Berechnung (28'), Komplexität und Approximation (12') 21.05.2025 Max-Flow-Min-Cut-Theorem und Flussalgorithmen Schnitte, Residualgraphen, augmentierende Wege (22'), Algorithmus von Ford & Fulkerson (15'), Algorithmus von Edmonds & Karp (22') 28.05.2025 Matchings I Satz von Menger, bipartites Matching (18'), Heiratssatz (8') 04.06.2025 Matchings II Größte Matchings in bipartiten Graphen (8'), Chistofides' Algorithmus (13'), kostenminimales perfektes bipartites Matching (13'), Bonus: Beispiel dafür (pdf) -
Es wird voraussichtlich 12 Übungsblätter geben. Auf den bewerteten Blättern können jeweils bis zu 20 Punkte erreicht werden. Sie dürfen maximal in 2er-Gruppen abgeben. Bitte geben Sie die Namen aller an, die das Blatt mit Ihnen bearbeitet haben. Sie sollten Ihre Lösung während der Übung vorliegen haben.
Pro Gruppe ist das Übungsblatt von einem Gruppenmitglied auf WueCampus hochzuladen. Bevorzugt werden Abgaben, die mit Latex erstellt wurden. Sie können hierfür gerne die Vorlage nutzen. Bitte vermeiden Sie Fotografien von Abgaben. Der Abgabetermin ist dienstags um 13:00 Uhr.
Impressum | Datenschutzerklärung - WueCampus | Erklärung zur Barrierefreiheit | Kontakt | Bildnachweise
Navigationsleiste - Rechenzentrum: Data center icons created by Eucalyp - Flaticon
Navigationsleiste - Website Support: Consultant icons created by Vitaly Gorbachev - Flaticon
Navigationsleiste - Häufige Fragen: Files and folders icons created by Freepik - Flaticon
Navigationsleiste - Lehre Digital: Training icons created by vectorspoint - Flaticon
Navigationsleiste - Forschung Digital: Research icons created by Eucalyp - Flaticon
Navigationsleiste - Lecture: Video icons created by Freepik - Flaticon
Navigationsleiste - Toolbox: Toolbox icons created by Freepik - Flaticon
Werbefeld 2 - WueLogin: Login icons created by Freepik - Flaticon
Werbefeld 3 - Upgrade WueCampus 4.4: Update icons created by Freepik - Flaticon