Analytische Kombinatorik: Ziffern, Automaten und Bäume

Datenverschlüsselung (z. B. für sichere Verbindungen im Internet) beruht auf der effizienten Berechnungen von Einweg-Funktionen, d.h. Funktionen, für die es sehr aufwändig ist, aus dem Resultat Rückschlüsse auf die Eingabe zu ziehen. Ein Beispiel ist Exponentiation in endlichen Strukturen, wo es sehr schwierig ist, aus dem Ergebnis den Exponenten zu bestimmen. Das Standardverfahren für Exponentiation beruht auf sukzessivem Quadrieren und Multiplizieren, wobei die Anzahl der Quadrierungen der Anzahl der Ziffern und die Anzahl der Multiplikationen der Anzahl der von Null verschiedenen Ziffern des Exponenten ist. Verallgemeinerte Ziffernentwicklungen (z. B. mit negativen Ziffern) führen zu effizienteren Algorithmen. Ein Ziel des Projekts ist es, präzise Abschätzungen für deren Laufzeit anzugeben, um verschiedene Verfahren vergleichen zu können. Die Analyse von Ziffernentwicklungen wird durch die Verwendung von Automaten, einem Konzept aus der theoretischen Informatik, erleichtert. Einen Automaten kann man sich als eine Black Box vorstellen, die ihre Eingabe mittels eines endlichen Speichers in eine Ausgabe umwandelt. Ein Automat kann auch durch einen Graphen dargestellt werden, dessen Knoten dem endlichen Speicher und dessen Kanten Übergänge dazwischen darstellen. Die Untersuchung von Zusammenhangseigenschaften dieses Graphen führt zu qualitativen und quantitativen Resultaten über das Wachstum der zugehörigen Folge. Es ist geplant, Resultate über Automaten so zu verallgemeinern, dass auch allgemeinere Folgentypen analysiert werden können. Bäume, also kreisfreie Graphen, treten auch als natürliche Darstellungsform verschiedener Algorithmen auf, beispielsweise bei der Datenkompression. Die Effizienz eines solchen Algorithmus kann gemessen werden, indem man Kennzahlen wie Breite oder Höhe des zugehörigen Baumes bestimmt. Einerseits ist geplant, zusätzliche Parameter von Bäumen aus passenden Klassen sowie deren Verbindungen zu verallgemeinerten Zählproblemen zu untersuchen. Andererseits sind Bäumean sichauch einlohnender Untersuchungsgegenstand. So ist etwa geplant, die größtmögliche Anzahl an Bäumen zu bestimmen, wenn die Anzahl der Nachbarn aller Knoten festgelegt ist. Andere, eng damit verbundene, Fragestellungen werden ebenfalls untersucht. Insbesondere sollen Methoden weiterentwickelt werden, um zu zeigen, dass die meisten der auftretenden Größen gegen eine Normalverteilung (Gaußsche Glockenkurve) streben. Dieses Projekt dient der Untersuchung von Fragen zu all diesen Themen vom Standpunkt der analytischen Kombinatorik aus, wobei besonderer Wert auf die Verbindungen zwischen den Gebieten gelegt wird. Teile des Projekts haben algorithmische Aspekte. Diese werden im freien mathematischen Software-System SageMath implementiert werden, um die Resultate des Projekts der Scientific Community leicht zugänglich zu machen.

Analytische Kombinatorik ist ein relativ neuer Zweig der Kombinatorik - ein mathematisches Gebiet, das sich Abzählproblemen widmet. Solche Probleme sind naturgemäß diskret; in der analytischen Kombinatorik werden jedoch Methoden aus der kontinuierlichen Mathematik verwendet. Eine der wesentlichen Methoden verwendet erzeugende Funktionen, die Folgen von Zahlen als Funktion codieren. Beispielsweise wird die Folge 2, 5, 14, 42, 132, als f(x) = 2 + 5x + 14x + 42x + 132x + codiert. Auf diese Art werden Eigenschaften der kontinuierlichen Funktion verwendet, um Eigenschaften der diskreten Folge zu bestimmen, beispielsweise das Wachstum der Folge. Reguläre Folgen waren einer der wesentlichen Untersuchungsgegenstände dieses Projekts. Dabei handelt es sich um Folgen, bei denen der n-te Term durch Bestimmen der Ziffernentwicklung der Zahl n in einer fixierten Basis berechnet wird - Zahlen werden üblicherweise in Basis 10 geschrieben, also 12 = 110 + 210; in Computern wird jedoch das Binärsystem (Basis 2) verwendet, also 1100 = 12 + 12 + 02 + 02; und analog können Zahlen in beliebigen Basen geschrieben werden. Diese Folgen treten bei der Analyse von sogenannten "Divide-and-conquer"-Algorithmen auf: diese teilen ihre Eingabe üblicherweise in zwei fast gleich große Teile auf, wiederholen diesen Prozess, bis die Daten leicht bearbeitbar sind, und fügen anschließend die Ergebnisse wieder zusammen. Im Rahmen dieses Projekts wurde das Wachstum regulärer Folgen mit sehr hoher Präzision bestimmt. Ein anderer wesentlicher Forschungsbereich des Projekts waren Gitterpfade. Ein typisches Beispiel eines Gitterpfades ist ein Graph eines Börsenkurses: der Preis eines Wertpapiers wird regelmäßig bestimmt und ein Liniensegment vom jeweils vorherigen Preis zum aktuellen Preis eingezeichnet. Mathematisch kann man verschiedene Bedingungen an Gitterpfade stellen, zum Beispiel deren Start- und Endpunkt vorgeben und den maximalen vertikalen Abstand von der Achse festlegen. Ein mächtiges Werkzeug aus der analytischen Kombinatorik zur Behandlung von Gitterpfadproblemen ist die "Kernel Method", die im Rahmen dieses Projekts zur "Vectorial Kernel Method" verallgemeinert wurde und zur Lösung einiger Probleme eingesetzt wurde. Bäume sind mathematische Strukturen, die eng mit Gitterpfaden verwandt sind. Sie werden häufig verwendet, um Informationen zu speichern oder diese zu suchen. Beispielsweise bilden Ordner und Dateien auf einem Computer einen Baum. Ein Untersuchungsgegenstand des Projekts waren Reduktionsprozesse in Bäumen, etwa das Entfernen aller Blätter (in obigem Beispiel Dateien oder leere Ordner) eines Baumes in aufeinanderfolgenden Schritten. Diese Reduktionsprozesse können verwendet werden, um Parameter von Bäumen wie ihre Höhe zu untersuchen. Im Rahmen des Projekts wurden auch Beiträge zum quelloffenen Mathematik-Software-Paket SageMath geleistet, damit dort die Objekte und Resultate des Projekts bequem verwendet werden können.