الخطوط العريضة للقسم

  • عام

    طي الكل توسيع الكل
    Umfang: 5 ECTS, 2+2 SWS
    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 (Lageplan))
    (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.) 
    • Wahl der Übungsgruppen hier in WueCampus. (Weiter unten können Sie Präferenzen für die einzelnen Gruppen vergeben.)
    • Die Anmeldung zur Klausur erfolgt über WueStudy (siehe auch das pdf zu allgemeinen Informationen weiter unten).
    Dozent: Alexander Wolff
    Übungen: Antonio Lauerbach
    Tutoren: Duy-Khang Tran, Christopher Brandt, Felix Bartunek
    Klausuren:

    1. Klausur: TBD
    2. Klausur: TBD
    Als Hilfsmittel ist nur ein einseitig handbeschriebenes Blatt (A4) zulässig.

    • Nachrichtenforum منتدى
    • Diskussionsforum منتدى

      • Übungsgruppen

        • Sie können hier bis Mittwoch, den 15.04., Präferenzen für die verschiedenen Übungsgruppen angeben. Die Zuteilung erfolgt dann am Donnerstagmorgen.

          Bitte besuchen Sie die Gruppe, die Ihnen zugeteilt wurde.

        • Übungsgruppenwahl Fair Allocation
          مفتوح: الأحد، 1 مارس 2026، 12:00 AM
          يُغلق: الأربعاء، 15 أبريل 2026، 11:59 PM

        • Nach der Zuteilung der Übungsgruppen können Sie hier (im Rahmen der freien Plätze) Ihre zugewiesene Gruppe ändern.

        • Wechsel der Übungsgruppe اختيار مجموعة
          Opens: الخميس، 16 أبريل 2026، 12:00 PM
          Closes: الجمعة، 17 يوليو 2026، 12:00 AM

  • 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 Visualisierung von Graphen (jedes SS)
    • Vorlesung Exakte Algorithmen (jedes SS)
    • Vorlesung Einführung in die Optimierung (jedes WS)
    • Vorlesung Operations Research (jedes SS)
    • Seminar Algorithmik (o.ä., jedes Semester)

    Siehe auch unsere Veranstaltungsübersicht

    • Allgemeine Informationen zur Vorlesung und Übung ملف

  • 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 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 
    (+ Kurzversion)    		 Thema (+ Langversion) Videos (alt!) Literatur

  • Übung

    Es wird 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 14:00 Uhr.