"Krone"-Serie

Wenn Computer an ihre Grenzen stoßen

(Bild: Betsy Garcia, Martin A. Jöchl)

Welche Probleme kann man mithilfe eines Computers lösen, welche nicht? Noch bevor ein realer Computer überhaupt entwickelt wurde, zog diese Frage viel Aufmerksamkeit auf sich. In den 1930er-Jahren beschäftigte sich eine ganze Reihe von Wissenschaftlern damit, die Grenzen der Berechenbarkeit zu bestimmen, unter anderem Kurt Gödel in Wien, Alan Turing in Cambridge (England) und Alonzo Church in Princeton (USA).

Die Frage ist auch heute noch besonders aktuell, wenn man bedenkt, dass die Technologie sich ständig weiterentwickelt und Computer immer mächtiger werden. Das heißt: was wir gestern noch nicht berechnen konnten, wird ein heutiger Computer problemlos lösen. Deshalb ist ein robustes Verständnis des Berechenbaren und Unberechenbaren, unabhängig von Speichergröße und Arbeitszeit des Computers, besonders wichtig, bevor man ein Problem für prinzipiell unberechenbar erklärt.

Am Institut für Diskrete Mathematik und Geometrie der TU Wien forscht Dr. Ekaterina Fokina über die Berechenbarkeit strukturierter Daten. In der heutigen Zeit, in der Milliarden Menschen täglich Suchmaschinen und soziale Netzwerke nutzen, werden enorme Mengen an Daten erzeugt, die so groß sind, dass sie aus der Sicht eines Computers praktisch "unendlich" erscheinen.

Eine weitere wichtige Charakteristik moderner Daten ist, dass sie selten als einfache Mengen vorkommen, sondern vielmehr als komplexe Strukturen, in denen Daten vielschichtig miteinander zusammengesetzt werden. Diese Beziehungen werden durch vielfach verzweigte mathematische Strukturen dargestellt, wie baumartige Bilder oder andere Formen geometrischer Skizzen, sogenannte Graphen (von griechisch zeichnen, schreiben).

Fokina beschäftigt sich mit der Frage, ob und wie die Eigenschaften solcher Strukturen berechnet werden können, wenn zum Beispiel zwei unendliche "Bäume" von einem Computer erzeugt werden: Kann man mithilfe eines Computers erkennen, ob diese "Bäume" die gleichen strukturellen Merkmale besitzen? Oder wenn die Daten, die ein Computer ausgibt, als unendlicher Graph dargestellt werden können, wie schwierig ist es dann, eine Verbindung von einem Knoten im Graphen zu einem anderen Knoten zu finden? Die Erkenntnisse der Mathematikerin fließen also direkt in die Entwicklung zukünftiger Generationen von Computern ein.

Zur Person:
Ekaterina Fokina ist österreichische Wissenschaftlerin mit russischen Wurzeln. Sie stammt aus Nowosibirsk, wo sie an der staatlichen Universität Nowosibirsk studierte. Während ihres Doktoratsstudiums verbrachte sie ein Jahr an der University of Notre Dame in South Bend (USA). Nach ihrer Promotion kam sie nach Wien und arbeitete zuerst am Kurt Gödel Research Center for Mathematical Logic der Universität Wien, wo sie 2013 habilitierte. Seit September 2015 arbeitet sie als Postdoc-Universitätsassistentin an der TU Wien und baut eine Gruppe in berechenbarer Strukturtheorie auf. Fokinas Arbeiten werden unter anderem durch mehrere Projekte des Fonds zur Förderung der wissenschaftlichen Forschung (FWF) unterstützt.

In der Serie "Krone der Wissenschaft" stellen wir Projekte von Spitzenforschern und -forscherinnen in Österreich vor. Ausgewählt werden sie von Prof. Dr. Georg Wick, dem Leiter des Labors für Autoimmunität an der Medizinischen Universität Innsbruck.