Kursthemen
-
Vorlesung Algorithmische Graphentheorie
Umfang: 5 ECTS, 2+2 SWS [T:2,P:0] Vorlesung: dienstags, 08:30–10:00 Uhr, HS 2 (Nat.wiss. HS-Bau)
Ausnahme: die erste Vorlesung am 30.04. findet von 8:15–9:45 Uhr statt
Übungen:
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 IVoraussetzung: 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: Johannes Zink
Diana Sieper (Übungsgruppe 1)
Vasil Alistarov (Übungsgruppe 2)
Michael Kreuzer (Übungsgruppe 3)
Lukas Schreiner (Übungsgruppe 4)-
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 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
-
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).
-
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 in der Regel dienstags um 8:30 Uhr.
-
Bitte laden Sie den Quelltext zu Aufgabe 1 hier in WueCampus hoch und vermerken Sie den Namen und die s-Nummer dessen, der sie hochlädt, auf Ihrer Übungsblattabgabe. Die Übungsblattabgabe mit Ihren Lösungen zu den übrigen Aufgaben werfen Sie bitte wie üblich in unseren Briefkasten.
-
Bitte laden Sie den Quelltext zu Aufgabe 2 a) hier in WueCampus hoch und vermerken Sie den Namen und die s-Nummer dessen, der sie hochlädt, auf Ihrer Übungsblattabgabe. Die Übungsblattabgabe mit Ihren Lösungen zu den übrigen Aufgaben werfen Sie bitte wie üblich in unseren Briefkasten.
-
Die Modalitäten für die Klausur unterscheiden sich, je nachdem nach welcher Prüfungsordnung Sie studieren. Für Studenten im Bachelor Informatik gelten die folgenden Bestimmungen. Studenten in anderen Studiengängen finden in ihren fachspezifischen Bestimmungen jeweils die Version der Informatik-Prüfungsordnung, aus der das Modul entnommen ist. Die hier angegebenen Bestimmungen gelten dann entsprechend.
- Prüfungsordnung 2015-WS: Algorithmische Graphentheorie (10-I-AGT) ist für Sie eine Pflichtvorlesung im Unterbereich Mathematik. Sie müssen nicht an den Übungen teilnehmen. Wenn Sie 50% der Übungspunkte erreichen, können Sie sich allerdings einen Bonus für die Note der Klausur erarbeiten. Dieser Bonus gilt nur für die Klausur im SS 2019. Auch das Modul 10-GE-AGT für Games Engineering lässt einen Bonus zu.
- Prüfungsordnung 2014-SS: Algorithmische Graphentheorie (10-I-AGT) ist für Sie eine Pflichtvorlesung im Unterbereich Mathematik. Sie müssen nicht an den Übungen teilnehmen. Sie können ohne Voraussetzungen an der Klausur teilnehmen.
Unabhängig davon, ob ihre Prüfungsordnung einen Bonus durch erfolgreiche Übungsteilnahme zulässt, empfehlen wir Ihnen dringend Übungblätter abzugeben und die Übungen zu besuchen, da dies erfahrungsgemäß die Klausurergebnisse deutlich verbessert.
Sie können sich zwischen 16.04.2019 und 15.07.2019 über SB@Home zur Klausur an- bzw. wieder abmelden. Diese Frist ist vom Prüfungsamt vorgegeben. Ohne fristgerechte Anmeldung können Sie nicht an der Klausur teilnehmen.
Die Klausur wird voraussichtlich 90 Minuten dauern. Als Hilfsmittel ist ein von Ihnen selbst handschriftlich einseitig beschriebenes DIN A4-Blatt erlaubt.
- Prüfungsordnung 2015-WS: Algorithmische Graphentheorie (10-I-AGT) ist für Sie eine Pflichtvorlesung im Unterbereich Mathematik. Sie müssen nicht an den Übungen teilnehmen. Wenn Sie 50% der Übungspunkte erreichen, können Sie sich allerdings einen Bonus für die Note der Klausur erarbeiten. Dieser Bonus gilt nur für die Klausur im SS 2019. Auch das Modul 10-GE-AGT für Games Engineering lässt einen Bonus zu.