Graphentheorie (SS 2017)

Inhalt

• Modulbeschreibung

Dozenten

• Klaus Berberich
• Wolfgang Braun

Organisation

• Vorlesungen
• Dienstag 10:00-11:30 im Raum 7106
• Donnerstag 11:45-13:15 im Raum 4302 (findet nicht statt, wenn Übung stattfindet)


• Übungen
• Mittwoch 14:15-15:45 im Raum 3202
• Donnerstag 11:45-13:15 im Raum 4302 (findet nicht statt, wenn Vorlesung stattfindet)

Neuigkeiten

• Die Klausureinsicht findet am 6. November 2017 um 13:00 in 7110 statt

Vorlesungen (geplanter Ablauf)

Datum	Thema	Folien/Handout	Literatur
18.04.2017	Kapitel 1: Grundlagen Gerichtete und ungerichtete Graphen Knoten, Kanten und Grade		Kapitel B.4 in [1] und Kapitel 22 in [1]
20.04.2017	Adjazenzlisten, Adjazenzmatrix		Kapitel B.4 in [1] und Kapitel 22 in [1]
25.04.2017	Bewerbervortrag
27.04.2017	Pfade und Zyklen		Kapitel B.4 in [1] und Kapitel 22 in [1]
02.05.2017	Erreichbarkeit und Zusammenhang Bäume		Kapitel B.4 in [1] und Kapitel 22 in [1]
09.05.2017	Kapitel 2: Suchen und Sortieren Breitensuche		Kapitel B.4 und 22.2 in [1]
11.05.2017	Tiefensuche		Kapitel B.4 und 22.3 in [1]
16.05.2017	Tiefensuche auf dem gesamten Graphen Zyklenfreiheit		Kapitel B.4 und 22.3 in [1]
18.05.2017	Topologisches Sortieren		Kapitel B.4 und 22.3 in [1]
25.05.2017	Christi Himmelfahrt
30.05.2017	Kapitel 3: Pfade Gewichtete Graphen Eigenschaften kürzester Pfade Algorithmus von Bellman und Ford		Kapitel 24.1 in [1] und Kapitel 4.9 in [2]
06.06.2017	Erkennen von Zyklen mit negativem Gewicht Wiederholung Prioritätswarteschlangen		Kapitel 24.3 in [1] und Kapitel 4.9 in [2]
13.06.2017	Algorithmus von Dijkstra		Kapitel 24.3 in [1] und Kapitel 4.9 in [2]
15.06.2017	Fronleichnam
20.06.2017	Algorithmus von Floyd und Warshall		Kapitel 25 in [1]
27.06.2017	Kapitel 4: Komponenten und Spannbäume Bestimmen von Zusammenhangskomponenten		Kapitel 21 in [1]
29.06.2017	Algorithmus von Kruskal
04.07.2017	Algorithmus von Prim		Kapitel 23 in [1]
11.07.2017	Kapitel 5: Suchbäume Binäre Suchbäume		Kapitel 12 in [1]
13.07.2017	AVL-Bäume
18.07.2017	Vorlesung entfällt
27.07.2017	Fragestunde

Übungen (geplanter Ablauf)

Datum	Titel	Übungsblatt
03.05.2017/04.05.2017	Übungsblatt 1 (Ausgabe am 25.04.2017)
23.05.2017/24.05.2017	Übungsblatt 2 (Ausgabe am 02.05.2017)
31.05.2017/01.06.2017	Übungsblatt 3 (Ausgabe am 16.05.2017)
07.06.2017/08.06.2017	Übungsblatt 4 (Ausgabe am 23.05.2017)
21.06.2017/22.06.2017	Übungsblatt 5 (Ausgabe am 06.06.2017)
05.07.2017/06.07.2017	Übungsblatt 6 (Ausgabe am 20.06.2017)
19.07.2017/20.07.2017	Übungsblatt 7 (Ausgabe am 04.07.2017)
25.07.2017/26.07.2017	Übungsblatt 8 (Ausgabe am 13.07.2017)

Klausur

• Klausur vom 31.07.2017 als [PDF]
• Klausur vom 21.02.2018 als [PDF]

Ressourcen

Literatur

• [1] T.-H. Cormen, C. E. Leiserson, R. Rivest und C. Stein: Algorithmen - Eine Einführung, Oldenbourg Verlag, 2013
• [2] H.-P. Gumm und M. Sommer: Einführung in die Informatik, Oldenbourg Verlag, 2013
• [3] R. Sedgewick und K. Wayne: Algorithmen und Datenstrukturen, Pearson Studium, 2014
• [4] G. Saake und K.-U. Sattler: Algorithmen und Datenstrukturen: Eine Einführung mit Java, dpunkt.verlag, 2013