direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preise und Auszeichnungen 2015

23. April 2015

Stephan Kreutzer bekommt renommierten ERC Consolidator Grant der EU

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

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

Quelle: <a href="http://www.eecs.tu-berlin.de/zielgruppen/presse/medieninformationen/2015/april/medieninformation_nr_772015/">TU Medieninformation Nr. 77/2015</a>

Weitere Informationen:

Prof. Dr. Stephan Kreutzer
Fachgebiet Logik und Semantik

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe

Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.