idw – Informationsdienst Wissenschaft

Nachrichten, Termine, Experten

Grafik: idw-Logo
Science Video Project
idw-Abo

idw-News App:

AppStore

Google Play Store



Instanz:
Teilen: 
08.03.2019 10:44

Grenzen effizienter Verfahren

Peter Kuntz Presse- und Öffentlichkeitsarbeit
Universität Trier

    Sie schreiben keine Software und sie spüren keine IT-Sicherheitslücken auf. Dennoch ist das, woran Informatiker der Universität Trier forschen, auch für die Praxis relevant. In einem neuen Projekt befasst sich eine Gruppe um Prof. Dr. Henning Fernau mit „modernen Komplexitätsaspekten formaler Sprachen“.

    Die Komplexitätstheorie untersucht, ob ein Problem überhaupt lösbar ist und mit welchem Aufwand. Damit liefert dieser Kernbereich der Theoretischen Informatik anderen Teildisziplinen innerhalb der Informatik wichtige Hinweise, wo eine Suche nach effizienten Lösungen sinnvoll ist. Die Einordnung in Problemklassen ist aber auch für praktische Anwendungen von Wert, beispielsweise für die Entwicklung von Texteditoren, von Datenkompressionslösungen oder für die Optimierung von Suchmaschinen.

    Zur Einordnung von Problemen in unterschiedliche Klassen zieht die Komplexitätstheorie verschiedene Ressourcen heran. Beispielsweise geht es um die Frage, ob sich ein Problem mit den vorhandenen Rechenkapazitäten in einer realistischen Laufzeit lösen lässt. Der Aufwand für die Lösung steigt verständlicherweise mit der Größe der Eingabe, nur ist häufig nicht bekannt, welcher Aufwand wirklich geleistet werden muss.

    Die Komplexitätstheorie hat in den vergangenen Jahren neue Ansätze und Methoden hervorgebracht. Diesen Fortschritt wollen sich die Trierer Informatiker um Professor Henning Fernau in ihrem Projekt zunutze machen und ihn auf den Bereich der formalen Sprachen anwenden. Dabei handelt es sich um ein Gebiet, das unter anderem Mathematik, Linguistik oder auch Logik mit der Informatik verbindet. Sie sind auch Grundlage von Programmiersprachen.

    „Die meisten Fragestellungen zu formalen Sprachen wurden unserem Empfinden nach weitgehend vernachlässigt, als in der letzten Dekade viele neue komplexitätstheoretische Konzepte entwickelt wurden“, erklärt Henning Fernau den Ansatz des von ihm geleiteten Forschungsvorhabens.

    In einem Kick-Off-Workshop unter Leitung von Henning Fernau haben im Februar internationale Wissenschaftler aus vier Kontinenten gemeinsam nach neuen Strategien gesucht. „Es war ein sehr kreativer Prozess, in dem wir uns aus dem Blickwinkel eines Bereiches den Problemen eines anderen Bereichs genähert haben“, fasst Fernau die Herangehensweise zusammen.

    Impulse aus dem mehrtägigen Workshop werden die Trierer Wissenschaftler in ihre Forschungsarbeit aufnehmen, in der Hoffnung, in der dreijährigen Laufzeit des von der Deutschen Forschungsgemeinschaft geförderten Projektes entweder bessere Verfahren zu finden oder nachweisen zu können, dass es diese nicht geben kann. Die auf der Basis von theoretischen Methoden gewonnenen Ergebnisse dürften auch Anwender, Programmierer und Wissenschaftler in Informatik-Nachbardisziplinen interessieren bzw. ihnen zugutekommen.


    Wissenschaftliche Ansprechpartner:

    Prof. Dr. Henning Fernau
    Theoretische Informatik
    Tel. +49 651-201 2827
    E-Mail: fernau@uni-trier.de


    Bilder

    Prof. Dr. Henning Fernau, Petra Wolf und Michail Volkov
    Prof. Dr. Henning Fernau, Petra Wolf und Michail Volkov
    Foto: Jenna Theis, Universität Trier
    None


    Merkmale dieser Pressemitteilung:
    Wissenschaftler
    Informationstechnik, Mathematik, Sprache / Literatur
    überregional
    Forschungsprojekte
    Deutsch


     

    Prof. Dr. Henning Fernau, Petra Wolf und Michail Volkov


    Zum Download

    x

    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).