idw – Informationsdienst Wissenschaft

Nachrichten, Termine, Experten

Grafik: idw-Logo
Science Video Project
idw-Abo

idw-News App:

AppStore

Google Play Store



Instance:
Share on: 
09/05/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


    Images

    Criteria of this press release:
    Journalists
    Information technology
    transregional, national
    Personnel announcements
    German


     

    Help

    Search / advanced search of the idw archives
    Combination of search terms

    You can combine search terms with and, or and/or not, e.g. Philo not logy.

    Brackets

    You can use brackets to separate combinations from each other, e.g. (Philo not logy) or (Psycho and logy).

    Phrases

    Coherent groups of words will be located as complete phrases if you put them into quotation marks, e.g. “Federal Republic of Germany”.

    Selection criteria

    You can also use the advanced search without entering search terms. It will then follow the criteria you have selected (e.g. country or subject area).

    If you have not selected any criteria in a given category, the entire category will be searched (e.g. all subject areas or all countries).