TU Berlin

Stabsstelle Kommunikation, Events und AlumniMedieninformation Nr. 77/2015

Inhalt des Dokuments

zur Navigation

Informatiker Stephan Kreutzer bekommt renommierten ERC Consolidator Grant der EU

Freitag, 17. April 2015

Medieninformation Nr. 77/2015

Forschungen sollen zu einem grundlegenden Verständnis gerichteter Graphen führen

Prof. Dr. Stephan Kreutzer
Bekommt 1, 9 Millionen Euro für den Aufbau einer Forschergruppe: Prof. Dr. Stephan Kreutzer
Lupe

20 Jahre kamen die Forschungen zur Struktur gerichteter Graphen nicht voran, weil ein zentraler Baustein fehlte. Doch 2014 gelang Dr. Stephan Kreutzer, Professor an der TU Berlin, und seinem japanischen Kollegen Prof. Dr. Ken-ichi Kawarabayashi vom National Institute of Informatics in Tokio der Durchbruch: Die beiden Wissenschaftler konnten die Existenz gitterartiger Strukturen in gerichteten Graphen nachweisen. Damit hatten sie dieses seit zwei Jahrzehnten offene Problem gelöst.

Die bahnbrechende Arbeit ermöglichte es Prof. Dr. Stephan Kreutzer, sein Forschungsprojekt „Structure Theory for Directed Graphs“ (DISTRUCT) bei der EU zu beantragen, das nun bewilligt wurde und wofür er den hoch angesehenen ERC Consolidator Grant bekommt. 1,9 Millionen Euro stehen ihm für seine Grundlagenforschung in den nächsten fünf Jahren zur Verfügung. Der ERC Consolidator Grant wird von der EU an exzellente Nachwuchswissenschaftlerinnen und -wissenschaftler vergeben und fördert deren innovative vielversprechende Forschung. „Das Geld soll helfen, an der TU Berlin eine Forschergruppe zu dem Thema Strukturtheorie gerichteter Graphen aufzubauen“, sagt Kreutzer, der seit vier Jahren an der TU Berlin lehrt und zuvor mehrere Jahre in Oxford und Cambridge arbeitete.

In den kommenden fünf Jahren wollen Kreutzer und seine Kolleginnen und Kollegen beim Verständnis über die Struktur gerichteter Graphen ein ganzes Stück vorankommen. „Im Moment“, so der Informatiker, „ist das Wissen über deren Struktur sehr rudimentär. Wir verstehen nicht so recht, wie sie funktionieren ganz im Gegensatz zu ungerichteten Graphen, die sehr gut erforscht sind.“

Ziel des Projektes ist es daher, Aussehen und grundlegende Eigenschaften gerichteter Graphen zu untersuchen und diese Erkenntnisse zur Entwicklung effizienter Algorithmen, also schneller Lösungsverfahren für viele schwierige Probleme in der Informatik zu nutzen. Solche Probleme entstehen zum Beispiel im Zusammenhang mit Sicherheitsfragen von Softwareprogrammen oder bei der Verifikation von Steuerungen in Flugzeugen oder Kernkraftwerken. Um auszuschließen, dass die Schaltkreise, die zum Beispiel Kühlkreisläufe in Atomkraftwerken oder Teile von Flugzeugen kontrollieren, fehlerhaft sind, müssen sie verifiziert werden. Das heißt, es muss bewiesen werden, dass sie fehlerlos gebaut sind. „Und das ist letztendlich ein Problem gerichteter Graphen“, erklärt Prof. Dr. Stephan Kreutzer.

Graphen sind ein mathematisches Modell und bestehen aus einer Menge von Objekten (auch Knoten genannt) und einer Menge von Linien (auch Kanten genannt), die jeweils zwei Knoten miteinander verbinden, sie also in Relation zueinander setzen. Die Wissenschaft unterscheidet zwischen gerichteten und ungerichteten Graphen. Das Flugnetz einer Airline, das Organigramm eines Unternehmens, Routennetze beim Gütertransport sowie jedes Computer-Netzwerk wie das Internet – sie sind als Graphen darstellbar. Gerichtete Graphen können daher für die Lösung der verschiedensten Arten von algorithmischen Problemen, bei denen es um Fragen der Optimierung geht, angewendet werden. Zur Lösung hochkomplexer Transportprobleme oder bei Problemen der Konstruktion des World Wide Web werden gerichtete Graphen genutzt. Aber auch bei der Analyse metabolischer Netzwerke in der Biologie kommen sie zum Einsatz.

Ihre wegweisende Arbeit „The Directed Grid Theorem“ werden Ken-ichi Kawarabayashi und Stephan Kreutzer übrigens auf der renommierten internationalen Fachtagung STOC 2015, dem 47. ACM Symposium on Theory of Computing, in Portland (USA) im Juni dieses Jahres vorstellen:
http://arxiv.org/abs/1411.5681

sn

Weitere Informationen erteilt Ihnen gern:

Prof. Dr. Stephan Kreutzer
TU Berlin
Fachgebiet Logik und Semantik
Tel.: 030/314-29088

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe