Servicenavigation

Detailseite

Zurück

Projekt Druckansicht

Geometrische Algorithmen mit beschränktem Arbeitsspeicher

Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2013 bis 2021
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 242753045
 
Erstellungsjahr 2020

Zusammenfassung der Projektergebnisse

In den letzten Jahren können wir in der Informatik zwei entgegengesetzte Trends beobachten: Auf der einen Seite werden die zur Verfügung stehenden Hardware-Ressourcen immer umfangreicher. Dies führt oft zu aufgeblasener Software, welche ohne Rücksicht auf Ressourcen und Effizienz entwickelt wird. Auf der anderen Seite sehen wir aber auch eine weite Verbreitung von kleinen Geräten, die nur über geringe Mengen an Speicher und Akkuvolumen verfügen. Software, die nicht in Hinblick auf den verfügbaren Speicherplatz entwickelt wurde, ist für ein solches Umfeld nicht geeignet. Und selbst wenn diese kleinen Geräte über größere Speicherkapazitäten verfügen sollten, kann es dennoch von Vorteil sein, die Anzahl der Schreiboperationen in der Software zu beschränken. Angesichts dieser Lage ist es sinnvoll, sich auf Algorithmen zu konzentrieren, die nur eine geringe Menge von Arbeitsspeicher mit Lese- und Schreibzugriff benötigen, während die Eingabe in einem Speicherbereich liegt, der nur gelesen werden kann. Das Ziel des vorliegenden Projektes ist es, Algorithmen für geometrische Probleme zu untersuchen, für die nur wenig Arbeitsspeicher benötigt wird. Das zugrundeliegende Modell ähnelt der üblichen reellen Registermaschine. Diese erlaubt es, wahlfrei auf die einzelnen Speicherzellen zuzugreifen, wobei jede Speicherzelle ein einzelnes Datenwort enthält. In unserem Modell unterscheiden wir aber zwischen zwei verschiedenen Arten von Speicherzellen: (i) Eingabezellen, auf welche nur lesend zugegriffen werden darf; und (ii) Arbeitszellen, die sowohl gelesen aus auch beschrieben werden können. Die Ausgabe muss sequentiell bereitgestellt werden und darf im Anschluss weder gelesen noch verändert werden. Die Speichereffizienz eines Algorithmus wird gemessen durch die Anzahl der Arbeitszellen, die der Algorithmus benötigt. Dabei gibt es zwei Extreme: Algorithmen, die nur eine konstante Anzahl von Arbeitszellen benötigen, und solche, bei denen die Anzahl der Arbeitszellen proportional mit der Eingabegröße wächst. Dazwischen besteht ein ganzes Spektrum von Möglichkeiten, welche wir als Zeit-Platz-Trade-Off bezeichnen. Im Rahmen des Projektes haben wir für zahlreiche klassische Probleme der algorithmischen Geometrie Methoden entwickelt, die einen Trade-Off zwischen Zeit und Platzbedarf ermöglichen. Insbesondere haben wir uns mit k-Sichtbarkeitsregionen in einfachen Polygonen, mit Voronoi Diagrammen und mit kürzesten aufspannenden Bäumen in der euklidischen Metrik beschäftigt. Für jedes dieser Probleme haben wir Methoden entwickelt, welche zwischen den besten bekannten Algorithmen für das Szenario von konstantem Arbeitsspeicher und für das Szenario von linearem Arbeitsspeicher interpolieren. Um diese Ergebnisse zu erhalten, haben wir tief in die Trickkiste der algorithmischen Geometrie gegriffen und einige bekannte Techniken an die neue Umgebung angepasst. Wir mussten aber auch neue Methoden entwickeln, die es so vorher noch nicht gegeben hat. Ein weiterer Aspekt des Projekts bestand in der experimentellen Evaluation unserer neuen Algorithmen. Wir haben einige unserer Algorithmen implementiert und in der Praxis getestet. Dabei stellte sich heraus, dass der beschränkte Speicherplatz zwar Einbußen in der Laufzeit mit sich bringt, die neuen Methoden aber durchaus für den praktischen Einsatz geeignet sind.

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

© 2024 DFG Kontakt / Impressum / Datenschutz

Textvergrößerung und Kontrastanpassung