4 std. Vorlesung + 2 std. Übungen
Viele praxisrelevante Fragestellungen in Wirtschaft, Technik und in anderen Wissenschaften können als Optimierungsprobleme in Graphen modelliert werden. Beispiele, die in der Vorlesung angesprochen werden, kommen aus den Bereichen Telekommunikation, Produktions- und Verkehrsplanung, Informatik, Biologie und Physik.
In dieser Vorlesung werden grundlegende Algorithmen zur Lösung von Problemen in Graphen behandelt. Unter anderem werden Algorithmen vorgestellt und analysiert, die folgende Fragen beantworten: Wie komme ich möglichst schnell von A nach B, wie pumpe ich möglichst viel Wasser durch ein bestehendes Leitungssystem, wie löse ich das Heiratsproblem?
Es werden dabei relevante Teile der Graphentheorie eingeführt sowie wichtige algorithmische Suchtechniken und Grundprinzipien wie Greedy- oder Augmentierungsverfahren. Mit diesen Methoden können die oben genannten Probleme effizient gelöst werden.
Es gibt (natürlich) auch Graphenprobleme, für die noch keine effektiven Lösungsverfahren bekannt sind. Beispiele hierfür sind das Travelling- Salesman und das Stabile-Mengen-Problem. Aber auch die Aufgabe, ein ausfallsicheres Kommunikationsnetzwerk zu entwerfen, gehört dazu. In der Vorlesung wird gezeigt, wie man mit sogenannten primalen und dualen Heuristiken "gute" Lösungen für derartige Probleme finden kann.
VORAUSSETZUNGEN: keine
Geplante Fortsetzung: Diese Vorlesung ist die Einführungsveranstaltung und Grundvorlesung für den Schwerpunkt "Algorithmische Diskrete Mathematik" in den Studiengängen Mathematik und Techno- und Wirtschaftsmathematik. Im nächsten Semester wird die Reihe durch die Vorlesung "Lineare Optimierung" fortgesetzt.