Stochastische Analyse von Algorithmen

Themenreihe: Naturwissenschaft und Technik Referent: Prof. Dr. Ralph Neininger, Institut für Mathematik, Goethe-Universität Frankfurt Bei der stochastischen Analyse von Algorithmen und Datenstrukturen geht es darum, das typische Verhalten grundlegender Algorithmen zu verstehen. Dies geht über eine Analyse der Komplexität im schlechtesten Fall ("worst case analysis") oder im Mittel ("average case analysis") hinaus. Man stellt sich die Eingabe des Algorithmus zufällig vor. Soll z.B. eine Liste von Zahlen sortiert werden, so nimmt man jede der möglichen Permutationen der Zahlen als gleichwahrscheinlich an. Die resultierende Komplexität ist dann zufällig. Dies erlaubt viele Eigenschaften zu quantifizieren, etwa Ereignisse von unerwünscht großer Komplexität, deren Wahrscheinlichkeit man als exponentiell klein nachweisen möchte, um Garantien für die Zuverlässigkeit des Algorithmus zu erhalten. Im Vortrag werden einige grundlegende Algorithmen und Datenstrukturen im Rahmen einer stochastischen Analyse diskutiert. Für räumliche Daten spielen Fragmentierungen, die an Piet Mondrians Gemälde erinnern, eine Rolle. Verbindungen zu Fragmentierungsproblemen aus der physikalischen Literatur, in der Phasenübergänge vorhergesagt wurden, werden hergestellt.. #PhysikalischerVerein #Mathematik #StochastischeAnalyse