Graphen gehören zu den wichtigsten abstrakten Datenstrukturen in der Informatik. Sie haben sich als mächtiges Werkzeug zur Modellierung komplexer Probleme erwiesen. Daher sind Graphen nicht nur ein Kerngebiet der theoretischen Informatik, sondern auch allgegenwärtig in täglichen Anwendungen. Die zunehmende Komplexität von Graphen und Netzwerken in realen Anwendungen hat neue Herausforderungen bei der Implementierung von Graphenalgorithmen zur Folge. In dieser Veranstaltung werden diese Herausforderungen angegangen, indem man die Dualität zwischen Graphen und Matrizen ausnutzt. Es wird gezeigt, wie man Graphenalgorithmen durch Operationen der linearen Algebra ausdrückt und algebraische Algorithmen implementiert. Weiterhin lernen die Teilnehmer, lineare Algebra als Analyse-Hilfsmittel für Graphenalgorithmen einzusetzen.
Lernziele: Die Studierenden sollen den Zusammenhang zwischen Graphen und Matrizen und damit auch zwischen Algorithmen auf Graphen und Matrizen erkennen. Dies geht damit einher, dass die Studierenden auftretende Fragestellungen aus der Graphentheorie auf ihren algorithmischen Kern reduzieren und dann mittels Techniken der linearen Algebra analysieren und/oder lösen. Bei der praktischen Lösung der behandelten Probleme lernen die Studierenden den Einsatz von geeigneten Softwareumgebungen. Weiterhin können die Studierenden die vorgestellten Methoden autonom auf verwandte Fragestellungen anwenden. |