Graphenalgorithmen WS 07/08

	Dr. Sigrid Knust, Christian Viergutz
	Graphenalgorithmen WS 07/08

Inhalt:

Graphen gehören zu den wichtigsten Modellen der Informatik die zahlreiche praktische Anwendungen haben (z.B. im Verkehrs- und Telekommunikationsbereich, der Produktionsplanung oder allgemein bei vielen kombinatorischen Optimierungsproblemen).

Nach einer Einführung in die Grundbegriffe der Graphentheorie sollen Suchverfahren, Zusammenhangs-Probleme, Bäume, Kürzeste Wege, Matching- und Routing-Probleme, Knoten- und Kantenfärbungen behandelt werden. Dabei steht die Entwicklung von effizienten Lösungsverfahren im Vordergrund. In den Übungen sollen einige Algorithmen auch praktisch implementiert werden.

Termine:

Vorlesung:

Tag Zeit Raum

Mo 10:15-11:45 31/E05

Mi 12:15-13:45 31/E05
Übung:

Tag Zeit Raum

Di 10:15-11:45 69/E18

Mi 14:15-15:45 69/E18

Material zur Vorlesung :

Literatur :

R.K. Ahuja, T.L. Magnanti, J.B. Orlin: Network Flows, Prentice Hall, 1993
J.M. Aldous, R.J. Wilson: Graphs and applications, Springer, 2003
R. Diestel: Graphentheorie, Springer, 2000
J. Gross, J. Yellen: Graph theory and its applications, CRC Press, 1999
J. Gross, J. Yellen: Handbook of graph theory, CRC Press, 2004
D. Jungnickel: Graphen, Netzwerke und Algorithmen, BI-Verlag, 1987
R. Sedgewick: Algorithms, Addison Wesley, 1988
V. Turau: Algorithmische Graphentheorie, Oldenbourg, 2004

Teilnahme :

Teilnehmen können alle interessierten Studierende aus den Studiengängen Mathematik/Informatik, Angewandte Systemwissenschaft, Cognitive Science.

Schein :

Voraussetzung für den Erwerb eines Scheins zur Veranstaltung ist die regelmäßige Teilnahme an den Übungen, die erfolgreiche Bearbeitung der Übungsaufgaben (jeweils 50% der Maximalpunkte in theoretischen und 50 % der Maximalpunkte in praktischen Aufgaben) und die erfolgreiche Absolvierung einer Klausur am Ende des Semesters. Prüfungsrelevant sind alle Kapitel der Vorlesung sowie die Themen aus den Übungen.

Weblinks :

Last update: 14.01.2008 (SK/CV)