idw – Informationsdienst Wissenschaft

Nachrichten, Termine, Experten

Grafik: idw-Logo
Grafik: idw-Logo

idw - Informationsdienst
Wissenschaft

Science Video Project
idw-Abo

idw-News App:

AppStore

Google Play Store



Instanz:
Teilen: 
05.09.2019 15:40

Die Suche nach den Grenzen der Suchgeschwindigkeit - Karl Bringmann erhält bedeutenden Forschungspreis

Bertram Somieski Presse- und Öffentlichkeitsarbeit
Max-Planck-Institut für Informatik

    Karl Bringmann, Senior Researcher am MPI für Informatik, ist vom European Research Council mit einem ERC Grant ausgezeichnet worden, dem europäischen Forschungspreis mit dem höchsten Prestige. Innerhalb der nächsten fünf Jahre stehen ihm jetzt aus seinem ERC Starting Grant 1,5 Millionen Euro zu Forschungsarbeiten über fein-granulare Komplexität / lineare Programmierung zur Verfügung.

    Der Begriff fein-granulare Komplexität / lineare Programmierung erscheint beim ersten Lesen beliebig weit vom täglichen Leben entfernt. Die Gutachter bei der europäischen Forschungsagentur sahen das allerdings anders. Das Forschungsthema beschäftigt sich im weiteren Sinne damit, wie schnell ein Computeralgorithmus bei schwierigen Problemen die beste aller möglichen Lösungen finden kann.
    Die computergestützte Zusammenstellung von Schicht- oder Stundenplänen ist mittlerweile alltäglich. Hier, wie auch bei anderen Optimierungsaufgaben, kommen Algorithmen zum Einsatz, die dafür sorgen, dass üblicherweise sehr gute Lösungen gefunden werden können, ggf. sogar optimale Ergebnisse. Ähnliches passiert bei der Suche nach Wörtern oder Fragmenten in Texten. Der Entwicklung von schnelleren Suchalgorithmen wurde deshalb seit dem Beginn der Computerzeit große Aufmerksamkeit geschenkt. Die Kenntnis über Grenzen der theoretisch überhaupt möglichen Effizienz solcher Algorithmen vermeidet dann unnötige Bemühungen.
    Hier beginnt das Gebiet der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik: Welcher Ressourcenverbrauch (Rechenzeit, Speicherplatzbedarf, ggf. Parallelisierbarkeit) ist mindestens nötig, um ein gegebenes Problem zu lösen.
    „Was die Komplexitätstheorie für mich interessant macht, ist die Möglichkeit, bestimmte Grenzen zu finden, die garantiert nicht überwunden werden können. Die Schwierigkeiten des Erkenntnisgewinns sind sehr hoch, die Befriedigung nach einem Resultat aber auch“, umreißt Karl Bringmann seine Motivation: „Selbst wenn es manchmal sehr lange dauert, bis eine bestimmte Hypothese entschieden wird, die Chance diese eine Tür für immer zu öffnen oder zu schließen ist verführerisch.“
    Dank des Förderpreises kann Karl Bringmann nun für fünf Jahre mit begabten jungen Mitarbeitern das Thema weiter bearbeiten. Er hofft auf Forschungsergebnisse, die beweisbar, d.h. mathematisch sicher, zeigen, dass es bei bestimmten Problemen keine schnelleren Lösungen geben kann, also ein weiteres Suchen danach von vornherein zum Scheitern verurteilt ist.
    Parallel zu Karl Bringmann wurden zwei weitere junge Wissenschaftler mit dem begehrten Preis bedacht, die noch vor kurzem an den Max-Planck-Instituten am Standort Saarbrücken geforscht haben: Zeynep Akata (bis 2017 Postdoc am MPI für Informatik, aktuell Univ. Amsterdam) und Ori Lahav (bis 2017 Postdoc am MPI für Softwaresysteme, aktuell Univ. Tel Aviv).

    Weitere Informationen:
    Webseite Karl Bringmann
    http://people.mpi-inf.mpg.de/~kbringma/

    Kontakt:
    Karl Bringmann
    Max-Planck-Institut für Informatik; Algorithms & Complexity
    Tel +49.681.9325-1005
    kbringma@mpi-inf.mpg.de


    Bilder

    Merkmale dieser Pressemitteilung:
    Journalisten
    Informationstechnik
    überregional
    Personalia
    Deutsch


     

    Hilfe

    Die Suche / Erweiterte Suche im idw-Archiv
    Verknüpfungen

    Sie können Suchbegriffe mit und, oder und / oder nicht verknüpfen, z. B. Philo nicht logie.

    Klammern

    Verknüpfungen können Sie mit Klammern voneinander trennen, z. B. (Philo nicht logie) oder (Psycho und logie).

    Wortgruppen

    Zusammenhängende Worte werden als Wortgruppe gesucht, wenn Sie sie in Anführungsstriche setzen, z. B. „Bundesrepublik Deutschland“.

    Auswahlkriterien

    Die Erweiterte Suche können Sie auch nutzen, ohne Suchbegriffe einzugeben. Sie orientiert sich dann an den Kriterien, die Sie ausgewählt haben (z. B. nach dem Land oder dem Sachgebiet).

    Haben Sie in einer Kategorie kein Kriterium ausgewählt, wird die gesamte Kategorie durchsucht (z.B. alle Sachgebiete oder alle Länder).