Strategien zur zielgerichteten Verbesserung regionentreuer Algorithmen

Strategien zur zielgerichteten Verbesserung regionentreuer Algorithmen

Bachelor- oder Masterarbeit je nach Schwierigkeit/Funktionsumfang

Themengebiet

Zuverlässigkeit, Fehlertoleranz, Regionentreue, verteilte Systeme, verteilte Algorithmen

Hintergrund

Regionentreue ist die Eigenschaft eines Algorithmus bzw. des den Algorithmus implementierenden Systems, auch nach dem Auftreten von Fehlern noch die Nutzfunktion des Algorithmus/Systems zu erbringen, wenn auch ggf. nur mit einer gewissen, reduzierten Güte. So könnte ein Sortierarlgorithmus beispielsweise eine Zahlenfolge nach dem Auftreten eines Fehlers immerhin noch mit einer Güte von 90% sortieren, nach zwei Fehlen mit 85% etc.  - im Gegensatz zu einem nicht regionentreuen Algorithmus/System, das nach einem Fehler komplett versagt, somit eine "Sortiergüte" von im schlimmsten Fall 0% an den Tag legt. Regionentreue ist somit ein Konzept der Zuverlässigkeit und Fehlertoleranz.
Regionentreue Algorithmen können unterschiedlich "regionentreu" sein: so erlaubt z.B. ein spezieller regionentreuer Algorithmus das Auftreten von a>0 Fehlern, ein anderer jedoch b>a Fehler. Oder ein spezieller Algorithmus reduziert seine Güte nach dem ersten Fehler um 10%, ein anderer nur um 5%. In beiden Fällen ist der jeweils zweite Algorithmus ggf. vorteilhafter.

Aufgabenbeschreibung

Gegenstand der Arbeit ist es, zu untersuchen, wie ein regionentreuer Algorithmus zielgerichtet und systematisch verbessert werden kann, z.B. indem er anschließend in der Lage ist, mehr Fehler auszuhalten oder bei Fehlern weniger Güte einbüßt oder gar beides. Dabei könnten z.B. Entwurfs- oder Transformationsvorschriften gefunden werden, die einen gegebenen regionentreuen Algorithmus mit skizzierten Effekten systematisch verändern. Neben dem Finden der Strategie an sich, muss diese als korrekt nachgewiesen werden. Zudem sollten die Verbesserungsstrategie exemplarisch an Beispielalgorithmen durchgeführt und ihr Effekt dokumentiert werden.

Ansprechpartner:

Prof. Dr.-Ing. Oliver Theel
Carl von Ossietzky Universität Oldenburg
Department für Informatik
Systemsoftware und verteilte Systeme

(Stand: 09.06.2021)