Graphalgorithmen

Modulnummer: Q10-02
Englischer Titel: Graph Algorithms
Leistungspunkte: 10
Lehrperson: Köbler

Empfohlene Vorkenntnisse

Module "Einführung in die Theoretische Informatik (A1)" und "Algorithmen und Datenstrukturen (A2)" oder vergleichbare Kenntnisse

Zwingende Voraussetzungen

keine

Inhalt

Viele praktisch relevante Problemstellungen lassen sich durch graphentheoretische Probleme modellieren. Während sich die Graphentheorie vorwiegend der Erforschung kombinatorischer Eigenschaften von Graphen widmet, steht in diesem Modul der Entwurf von effizienten Algorithmen auf Graphen im Mittelpunkt. Dabei werden wir sehen, dass sich nicht nur graphentheoretische Resultate bei der Suche nach effizienten Algorithmen gewinnbringend anwenden lassen, sondern auch umgekehrt der Algorithmenentwurf zu neuen interessanten graphentheoretischen Fragestellungen führt. Konkret werden wir uns unter anderem mit folgenden Themen befassen: kürzeste und längste Pfade, Flüsse und Schnitte, Zusammenhang, Matchingprobleme, Färbung und Planarität. Da viele algorithmische Graphprobleme NP-hart sind, gehen wir auch der Frage nach, auf welchen eingeschränkten Graphklassen eine effiziente Lösung möglich ist.

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

- schriftlich eingereichte und/oder mündlich vorgetragene Lösungen zu Aufgaben

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: ja

Turnus

Alle zwei Jahre