Zielsetzung

Informatik: Schnellerer Fortschritt bei Berechnungen durch neue Algorithmen

In den letzten Jahrzehnten stellte die Entwicklung immer schnellerer Rechner einen Meilenstein beim Fortschritt in der Computertechnologie dar. Allerdings wird die dadurch erzielte Beschleunigung der Berechnungen von der Zunahme an Geschwindigkeit, Leistung und Robustheit in den Schatten gestellt, die durch neue Algorithmen erzielt werden. Um ein typisches Beispiel zu nennen: Der Stand der Hardware und Algorithmen im Jahr 1970 ermöglichte die Berechnung einer optimalen Reiseroute für einen Handelsreisenden (ein klassisches Optimierungsproblem und anerkannter Benchmark für die Rechenleistung) durch 120 Städte. Die Erhöhung der Anzahl an Städten von n auf n+1 führt zu einem multiplikativen Anstieg der Anzahl an möglichen Routen um einen Faktor n. Legen wir nun also die durch die heutige Technologie höhere Hardware-Geschwindigkeit und die Algorithmen von 1970 zugrunde, so könnten wir lediglich optimale Routen zwischen 135 Städten ermitteln. Es ist der Fortschritt bei den Algorithmen, der es heute ermöglicht, optimale Routen zwischen Tausenden von Städten zu finden. Würden wir uns hier nur auf den Fortschritt bei der Hardware verlassen, wäre eine solche Leistung in Hunderten von Jahren nicht möglich.

Das Max-Planck-Institut für Informatik widmet sich der Forschung in diesem Bereich und legt dabei einen besonderen Schwerpunkt auf Algorithmen und ihre Anwendungen im weitesten Sinn. Das Interesse reicht von der Grundlagenforschung (Algorithmen und Komplexität, Logik der Programmierung) bis zu einer Reihe von Anwendungsbereichen (Computergraphik, Geometric Computation, Constraint Solving, Programmverifikation, Datenbanken und Informationssysteme, Bioinformatik).

  • Bei der Grundlagenforschung beinhaltet dies Top-Forschung bezüglich neuer Algorithmen.
  • Die Entwicklung von Algorithmen für Anwendungen umfasst die Integration neuer Algorithmen in ausgereifte Systeme und konkrete Anwendungsszenarios mit hohem praktischem Nutzen. Das beinhaltet auch die Implementierung umfassender Softwareplattformen und deren experimentelle Bewertung in konkreten Anwendungen.
  • Die Schaffung eines stimulierenden Klimas für Nachwuchsforscher.

Ziel des Instituts ist es, gleichermaßen durch wissenschaftliche Publikationen, Softwaresysteme und Ausbildung des akademischen Nachwuchses Wirkung zu erzielen.

Wir betrachten die Informatik als einen Bereich, der danach strebt, den Einsatz von Rechnern auf ein tiefgehendes Verständnis der zugrunde liegenden Prinzipien der Berechnungsmethoden zu fundieren. Das umfasst die mathematische und/oder formale Untersuchung von Algorithmen, wo immer dies möglich ist. Folglich ist die Grundlagenforschung in diesem Bereich teilweise stark mathematisch geprägt. Ein Teil dieser Forschung gehört zu den etablierten Feldern der theoretischen Informatik (Algorithmen und Komplexität, Logik der Programmierung). In konkreten Anwendungsbereichen sind viele rechentechnische Probleme so komplex, dass eine tiefgehende formale Behandlung nicht durchführbar ist. Deshalb ist unsere Analyse der beteiligten Algorithmen in diesen Fällen eher experimentell. Diese stützt sich in der Regel auf eine systematische Bewertung auf der Grundlage von sorgfältig von Hand gepflegten Anwendungsdaten und speziell entwickelten statistischen Modellen und nicht zuletzt auf den Einsatz praktischer Systeme im Anwendungsgebiet. Tatsächlich sind viele Probleme in komplexen Anwendungsgebieten zunächst unscharf oder nur teilweise spezifiziert, so dass die Modellierung, d.h. die formale Definition eines Problems, ein wichtiger Aspekt der Forschung ist.

Die Tragfähigkeit neuer Ideen wird getestet, durch die Integration neuer Algorithmen in Systeme und die Bewertung ihrer Anwendbarkeit unter realistischen Bedingungen. Kurzfristig ist diese Erfahrung nützlich für die Verfeinerung der Entwürfe. Langfristig ist sie unschätzbar für den Fortschritt des Wissens. Die meisten bedeutsamen Forschungsfortschritte im Bereich der Informatik und der Algorithmen entstanden durch diese Verbindung von neuen theoretischen Erkenntnissen und experimenteller Bewertung.

Ein weiteres wichtiges Ziel des Instituts ist die Schaffung eines stimulierenden Klimas für Nachwuchsforscher, damit diese die Möglichkeit haben, ihre eigenen Forschungsprogramme und -gruppen zu entwickeln und aufzubauen. Das Max-Planck-Institut für Informatik betreibt ein aktives Förderprogramm für Doktoranden und Postdoktoranden. Seit Gründung des Instituts gingen zahlreiche Forscher vom Saarbrücker Max- Planck-Institut zu anderen Forschungseinrichtungen und viele von ihnen nahmen eine Professur an.

Wir sind ebenso sehr darum bemüht, unsere Forschungsresultate zu verbreiten. Indem wir unsere Ideen den verschiedensten Forschungs- und Entwicklungsgemeinschaften vorstellen und durch sie testen lassen, gelangen wir zu einem besseren Verständnis. Wir versuchen verstärkt, unsere Resultate und Ergebnisse in einschlägigen Zeitschriften und auf Konferenzen zu veröffentlichen, und wir nutzen unsere Internet-Seiten, um sie so weit wie möglich für die Gemeinschaft verfügbar zu machen. Wir suchen nach Benutzern unserer Prototyp- Systeme unter denjenigen, die gemeinsame Interessen mit uns haben, und wir fördern die Zusammenarbeit mit Forschern sowohl aus akademischen als auch aus industriellen Bereichen. Wir ermutigen unsere Nachwuchsforscher, ihre eigenen Forschungsprogramme aufzubauen und zu anderen Einrichtungen zu wechseln.