Topic outline

  • 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 8 (Physikgebäude)
    3) freitags, 10:15–11:45 Uhr, SE II
    4) freitags, 12:15–13:45 Uhr, SE I
      Voraussetzung: Vorlesung Algorithmen und Datenstrukturen  (dringend empfohlen)
      Zielgruppe: Bachelor Informatik ab 2. Semester
      Anmeldung: Einschreibung hier in den Wuecampus-Kurs.
      Die Anmeldung zur Klausur erfolgt über WueStudy (siehe unten).
      Dozent: Alexander Wolff
      Übung:

      Diana Sieper
      Vasil Alistarov
      N.N.
      N.N.


      • Diskussionsforum
        Restricted Not available unless: Your Email address is not empty
    1. 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).

        • Übung

          Es wird insgesamt 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 Namen und Übungsgruppen aller Mitarbeiter an. Idealerweise sollten Sie mit ihrem Partner in der selben Übungsgruppe abgeben. Falls das nicht möglich ist, geben Sie bitte auf dem Blatt an, in welcher Gruppe es zurückgegeben werden soll. Sie müssen sich dann selbst darum kümmern es an Ihre Übungspartner weiterzugeben. Sie sollten Ihre Lösung in der Übung vorliegen haben.

          Bitte geben Sie Ihre Lösungen zu Beginn der Vorlesung oder im Briefkasten im Informatikgebäude (unterster Briefkasten in der ersten Spalte) ab. Der Abgabetermin ist mittwochs um 10:10 Uhr.