Graphenalgorithmen und lineare Algebra Hand in Hand - Detailseite

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.

Vorausgesetzt werden gute Grundkenntnisse der Linearen Algebra und der Algorithmik, wie sie im Bachelorstudium gelehrt werden.

In der zweiten Semesterhälfte wird die Vorlesung in Englisch stattfinden.

In the second half of the term, the lecture will be held in English.