Graphenalgorithmen und lineare Algebra Hand in Hand

Modulnummer: Q09-03
Englischer Titel: Graph Algorithms and Linear Algebra Hand in Hand
Leistungspunkte: 9
Lehrperson: Meyerhenke

Empfohlene Vorkenntnisse

- Gute Kenntnisse in Algorithmik, insbesondere Graphenalgorithmen
- Kenntnisse in linearer Algebra

Zwingende Voraussetzungen

keine

Inhalt

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.

Erforderliche Arbeitsleistungen für LP-Vergabe und Prüfungszulassung

keine

Lehrveranstaltungen

Vorlesung: 4 SWS
Übung: 2 SWS

Zugeordneter Vertiefungsschwerpunkt

Algorithmen und Modelle: ja
Modellbasierte Systementwicklung: nein
Daten- und Wissensmanagement: nein
Ohne Vertiefungsschwerpunkt: nein

Sprache im Modul

Deutsch: ja
Englisch: ja

Angeboten für Studiengänge

M. Sc.: ja
M. Ed.: ja
Wirtschaftsmaster: ja

Angeboten im

Wintersemester: nein
Sommersemester: nein

Turnus

Jedes Jahr