|
|
|
|
Beschreibung |
KursbeschreibungGraphen sind ein aufgrund ihrer Allgemeinheit sehr häufig verwendetes Modell, das sich zur Modellierung vieler Aufgaben in der Informatik eignet. Häufig sind dabei grundlegende Algorithmen wie z.B. zur Bestimmung kürzester Wege in Graphen gefragt. Die Effizienz dieser Algorithmen hängt sehr stark von ihrer Laufzeit ab.
In diesem Kurstext werden grundlegende algorithmische Probleme auf Graphen betrachtet. Es werden jeweils Polynomialzeitlösungen vorgestellt, soweit sie existieren, und dazu werden schwierigere allgemeinere Probleme angegeben, die vielfach NP-vollständig sind. Einige typische und wichtige Beispiele dafür werden ausführlich behandelt: Eulerkreise und Hamiltonkreise, Durchsuchen von Graphen (Tiefensuche und Breitensuche) sowie Anwendungen, Minimalgerüste, Greedy-Algorithmus und Matroide, Kürzeste Wege, Maximalflußproblem, Unabhängige Knoten- und Kantenmengen sowie Färbungsprobleme.
Der Schwerpunkt liegt dabei auf der ausführlichen Behandlung der Grapheneigenschaften, die zur effizienten Lösbarkeit von Problemen bzw. zur NP-Vollständigkeit von Problemen führen. Die bei effizienten Algorithmen vielfach verwendeten Datenstrukturen werden meistens nur erwähnt.
Der Kurs baut auf Kenntnissen des Kurses 01654 (Einführung in die Theoretische Informatik B) auf. Es existieren Berührungspunkte mit den Kursen Datenstrukturen sowie Komplexitätstheorie, deren Kenntnis wird jedoch nicht vorausgesetzt.
Für folgende Informatik-Studiengänge vorgesehen: B (über Katalog M), D, L, M, MC, Z. |
|
|
