| Lerninhalte |
Das Modul beschreibt Graphen- und Hypergraphenmodelle in einigen ausgew
ählten Gebieten der Informatik wie Datenbanken, Künstliche Intelligenz,
Computergraphik und Bioinformatik. Dazu werden grundlegende
Eigenschaften und Methoden wie Baumstruktur von Graphen und Hypergraphen,
Dekompositionsmethoden und Durchschnittsgraphen wie z.B.
Intervallgraphen behandelt. Für grundlegende Probleme in den Modellen
werden effiziente Algorithmen angegeben bzw. gezeigt, dass diese schwierig
sind und approximativ gelöst werden.
Inhalte
• Relationale Datenbankschemata und ihre Bezüge zu Hypergraphen
• Azyklische Hypergraphen und zugehörige Graphen
• join tree bei azyklischen Hypergraphen und clique tree bei chordalen Graphen
• das Constraint Satisfaction Problem und das Model Checking Problem
• Logikprobleme der KI und das Transversal Problem für Hypergraphen
• Cliquenseparatoren und hinge trees
• Intervallgraphen und ihre Verwendung in der Bioinformatik
• Phylogenetische Bäume und damit zusammenhängende Graphenprobleme
• planare Graphen und Graph Drawing |
