Kurs: SS15:Algorithmische Graphentheorie

Allgemeines

Vorlesung Algorithmische Graphentheorie

Umfang:

5 ECTS, 2+2 SWS [T:2,P:0]

Zeit & Ort:

Vorlesung:	dienstags, 10–12, HS 2
Übung:	freitags, 8:30–10:00, 10–12, SE III

Voraussetzung:

Vorlesung

Algorithmen und Datenstrukturen

Zielgruppe:

Bachelor Informatik ab 2. Semester

Dozent:

Alexander Wolff

Übung:

Philipp Kindermann (E12) sowie Hiwis Matthias Mayer und Julian Behringer

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.

Voraussetzungen

Vorlesung Algorithmen und Datenstrukturen

Weiterführende Veranstaltungen

Vorlesung Algorithmische Geometrie (jedes WS)
Vorlesung Approximationsalgorithmen (jedes ungerade SS außer SS'15)
Vorlesung Exakte Algorithmen (jedes gerade SS)
Vorlesung Visualisierung von Graphen (jedes SS)
Seminar Visualisierung von Graphen (jedes WS)
siehe auch unsere Veranstaltungsübersicht

Klausur

Studierende in der neuen Studienordnung Informatik / Mathematik benötigen keine Klausurzulassung. Studierende in der alten Studienordnung erhalten die Zulassung, wenn sie mindestens 50% der Übungspunkte erreichen.

Klausurtermine:

Di, 14.07.2015, 10:00-12:00, HS 2
Di, 06.10.2015, 10:00-12:00, Turing-HS

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 hier kapitelweise herunterladen kann, wenn man lokal an der Uni Würzburg eingeloggt ist. Eventuell muss man über den Katalog der UB auf die Verlagsseiten zugreifen.

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 sind maximal zwei Bearbeiter pro Abgabe erlaubt.

Bitte geben Sie Ihre Lösungen zu Beginn der Vorlesung oder via WueCampus ab. Der Abgabetermin ist jeweils dienstags um 10:15 Uhr.