General information

Course name	Vorlesung/Übung: Effiziente Graphenalgorithmen
Semester	SoSe 2024
Current number of participants	29
Home institute	Praktische Informatik (Datenstrukturen)
Courses type	Vorlesung/Übung in category Offizielle Lehrveranstaltungen
Next date	Wednesday, 15.05.2024 08:15 - 09:45, Room: Seminarraum 1.03 [VSP 1] (Informatik)
Pre-requisites	Grundkenntnisse in Algorithmen und Datenstrukturen Beherrschung einer Programmiersprache wie C++, C oder Java
Studiengänge (für)	Master Informatik Master Bioinformatik Master Interaktive Medien Master Wirtschaftsinformatik Master Mathematik
SWS	4
Miscellanea	Literaturhinweise: - R. Ahuja, T. Magnanti, J. Orlin: Network Flows, Prentice Hall, 1993. - T. Cormen, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms, MIT Press, 2nd edition, 2001. - B. Korte, J. Vygen: Combinatorial Optimization: Theory and Algorithms, Springer Verlag, 3rd ed., 2005. - A. Schrijver: Combinatorial Optimization, Springer, 2003. - R.E. Tarjan: Data Structures and Network Algorithms, SIAM, 1983.
ECTS points	5

Lehrende

Rooms and times

Hörsaal 3.31 [VSP 1] (Informatik): Tuesday: 10:15 - 11:45, weekly (14x)
Seminarraum 1.03 [VSP 1] (Informatik): Wednesday: 08:15 - 09:45, weekly (12x)

Fields of study

Naturwissenschaftliche Fakultät III - Agrarwiss., Geowiss. und Informatik > Informatik > Institut für Informatik > Fachrichtungen > Informatik
Naturwissenschaftliche Fakultät III - Agrarwiss., Geowiss. und Informatik > Informatik > Institut für Informatik > Themen > Theoretische-Informatik
Naturwissenschaftliche Fakultät II - Chemie, Physik und Mathematik > Institut für Mathematik > Hauptstudium
Naturwissenschaftliche Fakultät III - Agrarwiss., Geowiss. und Informatik > Informatik > Institut für Informatik > Fachrichtungen > Bioinformatik
Naturwissenschaftliche Fakultät III - Agrarwiss., Geowiss. und Informatik > Informatik > Institut für Informatik > Master
Naturwissenschaftliche Fakultät III - Agrarwiss., Geowiss. und Informatik > Informatik > Institut für Informatik > Themen > Lehrgebiet Theoretische Informatik und Algorithmen
Naturwissenschaftliche Fakultät III - Agrarwiss., Geowiss. und Informatik > Informatik > Institut für Informatik > Themen > Effiziente-Algorithmen

Module assignments

Comment/Description

Die Vorlesung behandelt grundlegende Algorithmen für Optimierungsprobleme auf Graphen, unter anderem für Kürzeste-Wege-Probleme, maximale bzw. kostenmimimale Flüsse in Netzwerken, Matchingprobleme, minimal aufspannende Bäume und Algorithmen für Probleme auf planaren Graphen.

Lernziele sind das Erlernen der wichtigsten Basisalgorithmen, das Kennenlernen von Verfahren zur Effizienzsteigerung und zur Analyse von Graphenalgorithmen und die Urteilsfähigkeit, welche Verfahren in der Praxis effizient sind. In den begleitenden Übungen werden einige Graphenalgorithmen implementiert und getestet.