Course: SS22: Algorithmische Graphentheorie

Topic outline

General

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, 10:15–11:45 Uhr, SE II (Informatikgebäude) (4) freitags, 12:15–13:45 Uhr, SE I (Informatikgebäude) Sowohl die Vorlesung als auch die Übung finden wieder in Präsenzform statt. Darüber hinaus stehen für Ankündigungen und Diskussionen das Forum auf WueCampus und Kanäle im Chat der Uni Würzburg zur Verfügung. (Die entsprechenden Links finden Sie im pdf zu allgemeinen Informationen weiter unten.)
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:	Johannes Zink
Tutoren:	(1) Thanh Mai Pham, (2) Samuel Wolf, (3) Antonio Lauerbach, (4) Martin Hesse
Klausuren:	Mo, 01.08., 12:00–14:00 (Turing, Zuse) [Anmeldung auf WueStudy bis 15.07.] ??, ??.10., ??:00–??:00 (??) Als Hilfsmittel ist nur ein einseitig handbeschriebenes Blatt (A4) zulässig.

Forum: 1

Nachrichtenforum
Diskussionsforum
Restricted Not available unless: Your Email address is not empty

Kursbeschreibung
Kursbeschreibung
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 Algorithmen für geographische Informationssysteme (jedes SS)
- Vorlesung Exakte Algorithmen (jedes SS)
- Seminar Visualisierung von Graphen (o.ä., jedes WS)
- Seminar Algorithmen für Programmierwettbewerbe (derzeit jedes WS und SS)
Siehe auch unsere Veranstaltungsübersicht
View Activities and Resources
Kursbeschreibung
- Allgemeine Informationen zur Vorlesung und Übung (Stand 02.05.2022) File
  Restricted Not available unless: Your Email address is not empty
Materialien zur Vorlesung
Materialien zur Vorlesung

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).
View Activities and Resources
Files: 26URL: 1
Materialien zur Vorlesung
- 01. Vorlesung (27.04.2022): Einführung File
- 01. Vorlesung (27.04.2022): Druckversion (Einführung) File
- 01. Vorlesung (27.04.2022): Video (Einführung) File
  Restricted Not available unless: Your Email address is not empty
- 01. Vorlesung (27.04.2022): Rundreiseprobleme I: Eulerkreise File
- 01. Vorlesung (27.04.2022): Druckversion (Eulerkreise) File
- 01. Vorlesung (27.04.2022): Video (Eulerkreise) File
  Restricted Not available unless: Your Email address is not empty
- 01. Vorlesung (27.04.2022): Rundreiseprobleme II: Hamiltonkreise File
- 01. Vorlesung (27.04.2022): Druckversion (Hamiltonkreise) File
- 01. Vorlesung (27.04.2022): Video (Hamiltonkreise) File
  Restricted Not available unless: Your Email address is not empty
- 02. Vorlesung (04.05.2022): Lineare Programmierung File
- 02. Vorlesung (04.05.2022): Druckversion File
- 02. Vorlesung (04.05.2022): Video Page
  Restricted Not available unless: Your Email address is not empty
- 02. Vorlesung (04.05.2022): Bonustrack – ILP-Formulierungen von Rucksack- und Graphfärbeproblem File
- 03. Vorlesung (18.05.2022): Problem des Handlungsreisenden (TSP) [30.5.: Minimum bei TSP-DP geklärt] File
- 03. Vorlesung (18.05.2022): Druckversion File
- 03. Vorlesung (18.05.2022): Video (TSP Teil I – Exakte Algorithmen) Page
  Restricted Not available unless: Your Email address is not empty
- 03. Vorlesung (18.05.2022): Video (TSP Teil II – Komplexität und Approximation) File
  Restricted Not available unless: Your Email address is not empty
- 03. Vorlesung (18.05.2022): Dynamische Programmierung und das Rucksackproblem File
- 03. Vorlesung (18.05.2022): Druckversion File
- 03. Vorlesung (18.05.2022): spannendes Video von Thomas van Dijk zu praktischen Aspekten von Algorithmen für das Rucksackproblem (33') URL
- 04. Vorlesung (25.05.2022): Max-Flow-Min-Cut-Theorem und Flussalgorithmen File
- 04. Vorlesung (25.05.2022): Druckversion File
- 04. Vorlesung (25.05.2022): Video (Teil I – 22 Min.) File
  Restricted Not available unless: Your Email address is not empty
- 04. Vorlesung (25.05.2022): Video (Teil II – 15 Min.) File
  Restricted Not available unless: Your Email address is not empty
- 04. Vorlesung (25.05.2022): Video (Teil III – 22 Min.) File
  Restricted Not available unless: Your Email address is not empty
- 05. Vorlesung (01.06.2022): Paarungen (Matchings) File
- 05. Vorlesung (01.06.2022): Druckversion File
- 05. Vorlesung (01.06.2022): Video (Teil I – Satz von Menger und größte Matchings in bipartiten Graphen, 18 Min.) File
  Restricted Not available unless: Your Email address is not empty
- 05. Vorlesung (01.06.2022): Video (Teil II – Heiratssatz, 8 Min.) File
  Restricted Not available unless: Your Email address is not empty
- 06. Vorlesung (08.06.2022): Matchings II: kombinatorischer Algorithmus, Christofides' Algorithmus, LP-Runden File
- 06. Vorlesung (08.06.2022): Druckversion File
- 06. Vorlesung (08.06.2022): Video (Teil I – Größte Matchings in bipartiten Graphen, 8 Min.) File
  Restricted Not available unless: Your Email address is not empty
- 06. Vorlesung (08.06.2022): Video (Teil II – Algorithmus von Christofides, 13 Min.) File
  Restricted Not available unless: Your Email address is not empty
- 06. Vorlesung (08.06.2022): Video (Teil III – Kostenminimale perfekte Matchings in bipartiten Graphen, 13 Min.) File
  Restricted Not available unless: Your Email address is not empty
- 06. Vorlesung (08.06.2022): Bonustrack – Beispiel für LP-Runden (kostenminimales perfektes Matching) File
- 07. Vorlesung (15.06.2022): Minimale Wurzelspannbäume File
- 07. Vorlesung (15.06.2022): Druckversion File
- 07. Vorlesung (15.06.2022): Video (Teil I – Edmonds' Algorithmus, 18 Min.) File
  Restricted Not available unless: Your Email address is not empty
- 07. Vorlesung (15.06.2022): Video (Teil II – Laufzeit und Korrektheit von Edmonds' Algorithmus, 12 Min.) File
  Restricted Not available unless: Your Email address is not empty
- 07. Vorlesung (15.06.2022): Bonustrack – Beispiel für Edmonds' Algorithmus File
- 08. Vorlesung (21.06.2022): Randomisierte Algorithmen für MinCut [22.06., 12:00: kleine Änderungen] File
- 08. Vorlesung (21.06.2022): Druckversion File
- 08. Vorlesung (21.06.2022): Video (45 Min.) Page
  Restricted Not available unless: Your Email address is not empty
- Der Stoer-Wagner-Algorithmus, ein einfacher deterministischer Algorithmus für MinCut
- 08. Vorlesung (21.06.2022): Bonustrack – Min-Cut-Algorithmus von Stoer und Wagner mit Beispiel File
Übung
Übung

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.
View Activities and Resources
Files: 7Assignments: 9
Übung
- LaTeX-Vorlage für Übungsabgaben File
- Wiederholung wichtiger Graphalgorithmen aus der ADS (wird in der Übung am 29.04.2022 diskutiert) File
- Wiederholung wichtiger Graphalgorithmen aus der ADS – Druckversion File
- Wiederholung wichtiger Graphalgorithmen aus der ADS – Video Page
  Restricted Not available unless: Your Email address is not empty
- 1. Übungsblatt (Abgabe bis 03.05.2022, 13:00) Assignment
  [PDF-Download]
- Einführung in OPL, Teil 1 (IDE im CIP-Pool) File
- Einführung in OPL, Teil 1 (Kommandozeile über ssh) File
- 2. Übungsblatt (Abgabe bis 17.05.2022, 13:00) Assignment
  [PDF-Download]
  Bitte laden Sie hier zusätzlich zu der pdf-Abgabe den Quelltext zu Aufgabe 1 hoch.
- 3. Übungsblatt (Abgabe bis 24.05.2022, 13:00) Assignment
  [PDF-Download]
- 4. Übungsblatt (Abgabe bis 31.05.2022, 13:00) Assignment
  [PDF-Download]
- 5. Übungsblatt (Abgabe bis 08.06.2022, 10:00) Assignment
  [PDF-Download]
- Einführung in OPL, Teil 2 (IDE im CIP-Pool) File
- Einführung in OPL, Teil 2 (Kommandozeile über ssh) File
- 6. Übungsblatt (Abgabe bis 14.06.2022, 13:00) Assignment
  [PDF-Download]
- 7. Übungsblatt (Abgabe bis 21.06.2022, 13:00) Assignment
  [PDF-Download]
- 8. Übungsblatt (Abgabe bis 28.06.2022, 13:00) Assignment
  [PDF-Download]
- 9. Übungsblatt (Abgabe bis 05.07.2022, 13:00) Assignment
  [PDF-Download]

SS22: Algorithmische Graphentheorie

Topic outline

General

Kursbeschreibung

Inhalt

Lernziele

Weiterführende Veranstaltungen

Materialien zur Vorlesung

Übung