Esquema per temes

  • General

    Vorlesung Algorithmische Graphentheorie

    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
    2) freitags, 10:15–11:45 Uhr, SE II
    3) freitags, 12:15–13:45 Uhr, SE I

    Bis auf weiteres finden zu den obengenannten Zeiten Online-Sprechstunden auf ifiChat statt. Zur Teilnahme muss man sich ggf. erst bei der Benutzerverwaltung der IT des Instituts ein Benutzerkonto einrichten ("New account" klicken) und dann auf ifiChat den beiden Kanälen agt-vorlesung und agt-uebung beitreten ("join"). Dazu brauchen Sie das Passwort V-E+F=2.
    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 unten).
    Dozent: Alexander Wolff
    Übungsleiter: Diana Sieper, Vasil Alistarov, Lukas Schreiner, Annika Förster
    Klausuren:

    Mo, 27.07.2020, 11–14 Uhr, Z6: AOK-HS, 0.001 und 0.002
    Do, 22.10.2020, 9–12 Uhr, Turing & Zuse
    Als Hilfsmittel ist nur ein einseitig handbeschriebenes Blatt (A4) zulässig.


    • Icona Fòrum
      Diskussionsforum Fòrum
  • 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 Exakte Algorithmen (unregelmäßig)
    • Vorlesung Visualisierung von Graphen (jedes SS)
    • Seminar Visualisierung von Graphen (o.ä., jedes WS und dieses SS)

    Siehe auch unsere Veranstaltungsübersicht

  • 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).

    Die Vorlesungsvideos sind nur sichtbar, wenn Sie in WueCampus eingeloggt sind.

    • Icona Fitxer
      01. Vorlesung (22.04.2020): Video (Einführung) Fitxer
    • Icona Fitxer
      01. Vorlesung (22.04.2020): Video (Eulerkreise) Fitxer
    • Icona Fitxer
      01. Vorlesung (22.04.2020): Video (Hamilton) Fitxer
    • Icona Pàgina
      02. Vorlesung (29.04.2020): Video (TSP Teil I – Exakte Algorithmen) Pàgina
    • Icona Fitxer
      02. Vorlesung (29.04.2020): Video (TSP Teil II – Komplexität) [mit Inhaltsverzeichnis – danke für den Tipp, RH!] Fitxer
    • Icona Pàgina
      03. Vorlesung (06.05.2020): Video [>100 MB, daher leider ohne Inhaltsverzeichnis] Pàgina
    • Icona Fitxer
      04. Vorlesung (13.05.2019): Video (Teil I – 22 Min.) Fitxer
    • Icona Fitxer
      04. Vorlesung (13.05.2019): Video (Teil II – 15 Min.) Fitxer
    • Icona Fitxer
      04. Vorlesung (13.05.2019): Video (Teil III – Beweis der Laufzeit von Edmonds-Karp, 22 Min.) Fitxer
    • Icona Fitxer
      05. Vorlesung (20.05.2020): Video (Teil I – Satz von Menger und größte Matchings in bipartiten Graphen, 18 Min.) Fitxer
    • Icona Fitxer
      05. Vorlesung (20.05.2020): Video (Teil II – Heiratssatz, 8 Min.) Fitxer
    • Icona Fitxer
      06. Vorlesung (27.05.2020): Video (Teil I – Größte Matchings in bipartiten Graphen, 8 Min.) Fitxer
    • Icona Fitxer
      06. Vorlesung (27.05.2020): Video (Teil II – Algorithmus von Christofides, 13 Min.) Fitxer
    • Icona Fitxer
      06. Vorlesung (27.05.2020): Video (Teil III – Kostenminimale perfekte Matchings in bipartiten Graphen, 13 Min.) Fitxer
    • Icona Fitxer
      07. Vorlesung (03.06.2020): Video (Teil I – Edmonds' Algorithmus, 18 Min.) Fitxer
    • Icona Fitxer
      07. Vorlesung (03.06.2020): Video (Teil II – Laufzeit und Korrektheit von Edmonds' Algorithmus, 12 Min.) Fitxer
    • Icona Pàgina
      08. Vorlesung (10.06.2020): Video (45 Min.) Pàgina
    • Der Stoer-Wagner-Algorithmus, ein einfacher deterministischer Algorithmus für MinCut
    • Icona Pàgina
      09. Vorlesung (17.06.2020): Video Pàgina
    • Icona Pàgina
      10. Vorlesung (24.06.2020): Video (42 Min.) Pàgina
    • Icona Pàgina
      11. Vorlesung (01.07.2020): Video (Teil 1, 35 Min.) Pàgina
    • Icona Fitxer
      11. Vorlesung (01.07.2020): Video (Teil 3, 21 Min.) Fitxer
    • Icona Fitxer
      12. Vorlesung (08.07.2020): Video (Teil I – Färben planarer Graphen, 18 Min.) Fitxer
    • Icona Fitxer
      12. Vorlesung (08.07.2020): Video (Teil II – Planaritätstest, 26 Min.) Fitxer
    • Icona Fitxer
      13. Vorlesung (15.07.2020): Video (11 Min.) Fitxer
  • Übung

    Es wird ca. 11 Ü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 Mitarbeiter an. Sie sollten Ihre Lösung während der Übung vorliegen haben.

    Pro Gruppe ist das Übungsblatt von einem Gruppenmitglied auf WueCampus hochzuladen (bevorzugt mit Latex erstellt, bitte vermeiden Sie Fotographien von Abgaben). Der Abgabetermin ist dienstags um 12:00 Uhr.