Vorlesung: Effiziente Graphenalgorithmen - Details

Allgemeine Informationen

Veranstaltungsname	Vorlesung: Effiziente Graphenalgorithmen
Semester	SS 2011
Aktuelle Anzahl der Teilnehmenden	0
Heimat-Einrichtung	Leitung des Instituts für Informatik
beteiligte Einrichtungen	Praktische Informatik (Datenstrukturen)
Veranstaltungstyp	Vorlesung in der Kategorie Offizielle Lehrveranstaltungen
Erster Termin	Donnerstag, 07.04.2011 08:15 - 09:45, Ort: (3.31)
Voraussetzungen	Grundkenntnisse in Algorithmen und Datenstrukturen Beherrschung einer Programmiersprache wie C++, C oder Java
SWS	3+1
Sonstiges	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-Punkte	5

Lehrende

• Prof. Dr. Matthias Müller-Hannemann
• Dr. Holger Blaar

Räume und Zeiten

(3.31)

Donnerstag: 08:15 - 09:45, wöchentlich (14x)

Keine Raumangabe

Freitag: 14:00 - 15:30, wöchentlich(14x)

Studienbereiche

• 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

Kommentar/Beschreibung

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.