Analyse von Datenstrukturen und baumartigen Strukturen

In diesem Projekt werden zwei wesentliche Ziele verfolgt: Einerseits wollen wir mathematisch fundierte Average-case Analysen für bestimmte, in der Informatik relevante Datenstrukturen geben, deren Verhalten bis dato noch wenig studiert wurde. Im Gegensatz zur Worst-case Analyse, wo der ungünstigste Fall untersucht wird, möchte man hierbei das für die Praxis oft bedeutendere durchschnittliche Verhalten relevanter Kenngrößen (Laufzeit, Speicherplatzbedarf, etc.) untersuchen. Andererseits wollen wir uns dem Studium wichtiger Parameter von baumartigen Strukturen widmen, welche zwar nicht als Datenstrukturen angesehen werden können, sondern aber als Modelle in verschiedensten Anwendungsgebieten benützt werden (z. B. bei der Beschreibung der Ausbreitung von Epidemien, bei Modellen für das Wachstum des Internets, für Modelle von Pyramidenspielen, etc.). Insbesondere werden die folgenden Themen behandelt: Prioritätswarteschlangen: sind wichtig bei vielen Problemen, wo Zeitpläne für Ereignisse, Aufgaben, etc. erstellt werden müssen. Typische Anwendungen findet man bei Betriebssystemen (Zeitpläne für die Abarbeitung verschiedenster Aufgaben, Ressourcenverwaltung, etc.) und in Simulationsmodellen diskreter Ereignisse. Skip lists: sind eine sehr flexible Datenstruktur, welche eine probabilistische Alternative zu Suchbäumen darstellt. Monoton markierte Bäume: sind eine natürliche Verallgemeinerung von Baummodellen, die in verschiedenen Anwendungen der Informatik (Traversierungsalgorithmen, Syntaxbäume, Auswertung logischer Ausdrücke) vorkommen. Increasing tree families: sind ein sehr allgemeines Baummodell, welches eine Reihe wichtiger Baumstrukturen, die beispielsweise zur Modellierung der Ausbreitung von Infektionen, von Pyramidenspielen, dem Wachstum des Internets und als Basis von Sortierverfahren verwendet werden, beinhaltet. Baumtraversierungsalgorithmen, Vorgänger und Nachfolger von Knoten: Probleme wie die Analyse des Speicherplatzbedarfes während einer Baumtraversierung und von Suchkosten in Datenstrukturen werden hier behandelt. Verallgemeinerte Plya-Eggenberger Urnenmodelle: haben eine Reihe von Anwendungen, z. B. werden sie zur Modellierung des Speicherplatzbedarfes bestimmter Datenstrukturen, der Ausbreitung von Infektionskrankheiten und für die Konstruktion von Abstammungsbäumen in den Sprachwissenschaften verwendet. Weitere Baumstatistiken: in der Literatur treten eine ganze Reihe interessanter Baumparameter für verschiedene Modelle auf, wo eine detaillierte Analyse von Interesse sein dürfte.