Mathematical Analysis of Sorting and Searching Algorithms

Das Problem der Entwicklung effizienter Algorithmen und Datenstrukturen zum Sortieren und Suchen von Datensätzen kann als eines der informatischen Grundprobleme angesehen werden. Um die Leistungsfähigkeit und folglich die praktische Verwendbarkeit dieser Algorithmen zu beurteilen, ohne sich auf rein experimentelle Größen stützen zu müssen, ist man auf exakte mathematische Analysen angewiesen. Seit Donald Knuths epochalem Werk "The art of computer programming" 1968ff, der den Grundstein für diesen mittlerweile bedeutenden Zweig der angewandten Mathematik und theoretischen Informatik legt, hat man eine ganze Reihe von Methoden aus den verschiedensten Teilen der Mathematik erfolgreich in diesem Gebiet einsetzen können. Von besonderer Bedeutung sind hier die erzeugenden Funktionen. Einerseits spiegelt sich eine Menge von kombinatorischen Konstruktionen direkt wider in den Operationen mit erzeugenden Funktionen, andererseits kann mit funktionentheoretischen Methoden, wie Singularitätenanalyse oder Sattelpunktmethode, oftmals das asymptotische Verhalten der Koeffizienten bestimmt werden. In den letzten Jahren gab es auch mit probabilistischen Methoden, wie beispielsweise der Anwendung von Grenzverteilungssätzen, erhebliche Fortschritte in dieser Richtung. Besonders erwähnt werden muß auch der Einsatz von modernen Computeralgebraprogrammen wie MAPLE, und dafür entwickelten Programmpaketen, die die beträchtlichen Fortschritte in der Analyse von Algorithmen erst ermöglichten. Gerade in den letzten Jahren gab es eine Reihe von Arbeiten zu bestimmten Sortier- und Suchalgorithmen bzw. von Datenstrukturen, die die heute zur Verfügung stehenden Methoden verwendet, es sind aber eine Reihe von Fragen unbeantwortet, die einer eingehenden mathematische Analyse von Sortier- und Suchalgorithmen betreffend. Die wichtigsten Fragen die sich dabei ergaben, seien hier als die wesentlichen Punkte des Projektes zusammengefaßt: 1. Analyse von p-trees, einer Datenstruktur für Prioritätswarteschlangen. 2. Analyse von Multiple Quickselect, einem Algorithmus zur Gewinnung von Reihenfolgenstatistiken. 3. Hoares Find Algorithmus mit asymmetrischer Auswahl des Partitionierungselementes. 4. Zusammenhänge darstellen zum Problem der Oszillation eines Stacks beim Abarbeiten eines Algorithmus. 5. Entwickeln eines Software-Tools für MAPLE, das bei der Manipulation mit Harmonischen Zahlen unterstützt. 6. Publikation der erzielten Ergebnisse in wissenschaftlichen Fachzeitschriften.

Dieses Projekt ist der Analyse von Computeralgorithmen zum Sortieren und Suchen von Daten gewidmet. Bei dieser mathematisch fundierten Analyse wird versucht, das durchschnittliche Laufzeitverhalten der untersuchten Algorithmen zu beschreiben. Es werden dabei zeitaufwendige Operationen studiert, die die sogenannten "Kosten" (Zeit ist Geld) des Algorithmus ausmachen. Als Beispiele für solche zeitaufwendigen Operationen seien Kenngrößen wie "Anzahl der Vergleiche", "Anzahl von Rotationen" und "Anzahl rekursiver Aufrufe" genannt. Solch eine Analyse liefert nun einerseits dem Anwender eine wissenschaftlich fundierte Entscheidungshilfe, die nicht auf rein empirischen Untersuchungen beruht, um den für seine Problemstellung optimalen Algorithmus zu verwenden. Auf der anderen Seite geben diese Analysen dem Forscher tiefere Einblicke in die Arbeitsweise eines Algorithmus, und somit können diese Untersuchungen dazu dienen, die Effizienz bestehender Algorithmen zu verbessern. In diesem Projekt wurden nun eine Reihe konkreter Algorithmen und Datenstrukturen mit Hilfe von Methoden aus verschiedenen Zweigen der Mathematik wie Kombinatorik, Algebra, Wahrscheinlichkeitstheorie und Analysis untersucht. Diesen Analysen entstammen eine Reihe von Arbeiten, die in wissenschaftlichen Journalen der Mathematischen Computerwissenschaften und Kombinatorik publiziert wurden. Auch wurden im Rahmen dieses Projektes zwei internationale Kooperationen mit französischen bzw. spanischen Forschern gebildet, die zu gemeinsamen Publikationen führten. Es erfolgt nun eine kurze Beschreibung von Resultaten dieses Projektes: In statistischen Auswertungen ist es oftmals nötig, Reihenfolgenstatistiken mehrerer Elemente für Datenfelder beliebiger Größe zu ermitteln. Ein Algorithmus, der dafür geeignet ist, heißt Multiple Quickselect und beruht auf den weit verbreiteten Sortieralgorithmus "Quicksort". Wichtige Kenngrößen wurden hier detailliert analysiert. Priority trees sind eine Datenstruktur um Prioritätswarteschlangen zu verwalten. Prioritäts-warte-schlangen besitzen z. B. Anwendungen in Betriebssystemen bei der Prozeßabarbeitung oder dem Management von Ressourcen. Es wurden hier eine Reihe von Parametern eingehend untersucht. Varianten der binären Suchbäume zählen zu den wichtigsten Datenstrukturen der Informatik. Die Leistungsfähigkeit verschiedener wichtiger Algorithmen steht in Zusammenhang mit der Anzahl der Vorgänger bzw. Nachkommen eines Elementes in einem Suchbaum. Diese Kenngrößen wurden hier studiert. Eine Möglichkeit, um die Geschwindigkeit des Wiederauffindens von Daten, die in den Knoten eines binären Suchbaumes gespeichert wurden, zu erhöhen ist das "lokale Balanzieren". Die dabei notwendigen "Rotationen" von Elementen bestimmen die Konstruktionskosten und wurden analysiert. In vielen Anwendungen wie beispielsweise bei Geographischen Informationssystemen, in Datenbanken, in der Computergraphik und bei der statistischen Datenanalyse müssen häufig mehrdimensionale Datensätze verarbeitet werden. Hier wurden Datenstrukturen (sogenannte Multidimensionale Suchbäume) analysiert, die sich hiefür eignen.