Freitag, 03.11.2023

Lehre

Von der Geometrie von Problemen

Antrittsvorlesung von Prof. Dr. Kim-Manuel Klein am 30. Januar (17 Uhr, Hörsaal AM 4)

In der Algorithmik geht es darum, möglichst effiziente Algorithmen für konkrete Problemstellungen zu entwickeln. Meistens konzentriert man sich dabei auf einfach zu beschreibende Probleme, die dennoch schwierig zu lösen sind.

Trotzdem gibt es tausende Probleme und Problemvarianten, die wissenschaftlich in der Algorithmik untersucht werden. Es stellt sich die Frage: Gibt es denn nicht einen allgemeineren Ansatz, um nicht für jede einzelne Problemstellung und jede Variante davon einen neuen Algorithmus entwickeln zu müssen? Ein Ansatz, um dieser Vielzahl von Problemen Herr zu werden, besteht darin, Probleme in einer mathematischen Form zu beschreiben.

Auf dieser Basis können sogenannte Meta-Algorithmen entwickelt werden, die das Problem nur anhand dieser Beschreibung lösen. Eine Beschreibungsmöglichkeit bieten hierbei sogenannte ganzzahlige Programme, wobei hier Probleme durch eine Menge von Ungleichungen beschrieben werden. Die meisten klassischen algorithmischen Problemstellungen lassen sich dadurch sehr einfach beschreiben.

Durch die Formulierung des Problems als ganzzahliges Programm eröffnet sich aber auch eine interessante und überraschend tiefe geometrische Interpretation. Innerhalb dieser Geometrie lassen sich algorithmische Probleme aus einer ganz anderen Perspektive betrachten und es ergeben sich neue strukturelle Ansätze. Darauf basierend lassen sich nicht nur allgemeinere Algorithmen entwickeln, sondern auch effizientere.

• Prof. Dr. rer. nat. Kim-Manuel Klein ist seit Oktober 2023 Professor am Institut für Theoretische Informatik der Universität zu Lübeck.