Grundlagen arbeitseffizienter paralleler dynamischer und statischer Algorithmen mit konstant beschränkter Laufzeit

• Antragsteller: Professor Dr. Thomas Schwentick
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 523044065

Das Projekt zielt darauf ab, die Forschung im Bereich der dynamischen Komplexitätstheorie um den Aspekt der Arbeitseffizienz zu erweitern und damit eine Brücke zu dem reichhaltigen Forschungsgebiet der dynamischen Algorithmen zu schlagen. Jüngste Forschungen auf dem Gebiet der dynamischen Komplexitätstheorie haben viele algorithmische Probleme identifiziert, die durch dynamische parallele Algorithmen mit konstanter Laufzeit gelöst werden können, unabhängig von der Größe der Eingabe. Hierbei liegt das sogenannte PRAM-Modell mit parallelen Prozessoren zugrunde, die auf einen gemeinsamen Speicher zugreifen können. So wurde zum Beispiel gezeigt, dass das Erreichbarkeitsproblem für gerichtete Graphen durch solche Algorithmen unter Einfügung und Löschung von Kanten aufrechterhalten werden kann. Diese Forschungen haben sich jedoch ausschließlich auf den Aspekt der konstanten Zeit konzentriert und andere Aspekte der Effizienz außer Acht gelassen, insbesondere die Arbeit, d. h. die Gesamtzahl der Schritte, summiert über alle Prozessoren. Infolgedessen stellt der Arbeitsaufwand der in der Literatur beschriebenen Algorithmen ein ernsthaftes Hindernis für ihre praktische Anwendbarkeit dar. Das Hauptziel dieses Projekts ist der Entwurf arbeitseffizienter paralleler dynamischer Algorithmen mit konstanter Laufzeit für wichtige algorithmische Probleme und die Entwicklung vielseitiger algorithmischer Techniken. Ein eng damit verbundenes zusätzliches Ziel ist der Entwurf arbeitseffizienter paralleler statischer Algorithmen mit konstanter Zeit, insbesondere für Teilaufgaben dynamischer Algorithmen. Ergänzende Untersuchungen werden versuchen, Grenzen der Existenz und Arbeitseffizienz beider Arten von Algorithmen zu ermitteln und eine Spezifikationsprache für dynamische parallele Algorithmen mit konstanter Laufzeit zu entwerfen.

• DFG-Verfahren: Sachbeihilfen