Computer haben zwei wichtige Fähigkeiten: Sie können mit riesengroßen Datenmengen umgehen – etwa wenn es darum geht, die Lohnverrechnung einer großen Firma durchzuführen, und sie können in kurzer Zeit sehr komplizierte Algorithmen abarbeiten – zum Beispiel um den besten Zug beim Schachspielen herauszufinden.

So richtig kompliziert wird es, wenn sie beides gleichzeitig tun müssen, wenn also schwierige, komplexe Berechnungen auf eine sehr große Datenmenge anzuwenden sind. Stefan Woltran vom Institut für Informationssysteme der TU Wien beschäftigt sich mit der Frage, wie man solche Aufgaben vereinfachen kann, indem man die natürliche Struktur der Daten nutzt. Für sein Projekt „Decodyn: Treating Hard Problems with Decomposition and Dynamic Programming“ erhielt er nun  einen START-Preis.

Unberechenbare Facebook-Freundschaften?
Ein typisches Beispiel für unübersehbar große, komplizierte Datensammlungen sind soziale Netzwerke wie Facebook. Die einzelnen Facebook-User stehen in Freundschafts-Beziehungen zueinander und bilden ein riesiges Datennetz. Eine schwierige Rechenaufgabe, die man hier stellen könnte ist: Wie viele Facebook-User muss man mindestens auswählen, sodass über sie alle Personen im Netzwerk über eine Freunschafts-Verbindung erreichbar sind?

Will man alle Möglichkeiten durchprobieren, stößt man schnell an die Grenzen des Machbaren. Auch mit den schnellsten Computern würden solche Berechnungen unvorstellbar lange dauern. Man muss also nach schlauen Abkürzungen suchen.

Datensammlungen wie soziale Netzwerkstrukturen sind niemals völlig zufällig. Es gibt Gruppen von Personen, die alle miteinander befreundet sind, mit anderen weit entfernten Gruppen aber gar keine sozialen Verknüpfungen haben. Wenn man Methoden entwickelt, diese Strukturen zu erkennen, zu quantifizieren und zu nutzen, lässt sich das Rechenproblem ganz dramatisch vereinfachen – und somit wird es für den Computer lösbar.

Wichtig sind solche Struktur-Überlegungen in vielen Bereichen, etwa im medizinischen Bereich, oder in der Bio-Informatik, wo es komplexe Moleküle oder Gene zu analysieren gilt. Die bestehenden Ideen aus der theoretischen Informatik sollen nun praktisch umgesetzt werden. „Zu diesem Zweck wollen wir die Konzepte der Decomposition, wo Probleme bzgl. ihrer Struktureigenschaften zerlegt werden, und des Dynamic Programmings, das sind spezielle Algorithmen die ein Problem entlang einer solchen Zerlegung abarbeiten, einsetzen“, erklärt Stefan Woltran.

START-Preis für Stefan Woltran
Mit dem START-Preis gibt der österreichische Wissenschaftsfonds FWF jungen Forscherinnen und Forschern die Chance, bis zu sechs Jahre lang finanziell abgesichert ihre Forschungsarbeiten eigenständig planen zu können. Das Geld des START-Preises ermöglicht den Aufbau eines eigenen Forschungsteams und bereitet die PreisträgerInnen damit optimal auf Führungspositionen in der Wissenschaft vor.

Rückfragehinweis:
Dr. Stefan Woltran
Institut für Informationssysteme
Technische Universität Wien
Favoritenstraße 9-11, 1040 Wien
T: +43-1-58801-18429
<link>stefan.woltran@tuwien.ac.at