Asymptotische Analyse extremaler diskreter Strukturen

Strukturen oder Algorithmen zu optimieren, ist in verschiedenen Bereichen der Mathematik und ihrer Anwendungen von Bedeutung. Dabei sind nicht nur die Lösungen selbst von Interesse, sondern auch ihr qualitatives und quantitatives Verhalten für große Parameterwerte, wodurch ein besseres Verständnis ihrer Eigenschaften sowie ein Vergleich mit anderen Ansätzen und Strategien ermöglicht wird. Dies erfordert jedoch eine genaue asymptotische und probabilistische Analyse diskreter Strukturen und Algorithmen. In diesem Kontext interessieren wir uns besonders für mathematische Probleme aus der Graphentheorie und aus Anwendungen in der Kryptographie. In den vergangenen Jahrzehnten wurde eine Reihe von unterschiedlichen graphentheoretischen Indices intensiv untersucht. Ein Grund hierfür ist, dass Moleküle als ungerichtete Graphen dargestellt werden können und gewisse physikochemische Eigenschaften von der Struktur dieser Graphen abhängen, was sich wiederum in den Werten ihrer graphentheoretischen Indices widerspiegelt. Es ist nur natürlich, nach den Wertebereichen dieser Indices zu fragen und jene Graphen zu bestimmen, welche die Indices über gewissen Graphenklassen (z.B. Bäume) maximieren bzw. minimieren. Somit ist es ein Ziel dieses Projekts, extremale Graphen bezüglich Indices im Zusammenhang mit dem Wiener-Index (Summe der paarweisen Distanzen), dem Merrifield-Simmons-Index (Anzahl unabhängiger Mengen) sowie dem Hosoya-Index (Anzahl der Matchings) unter verschiedenen Nebenbedingungen zu bestimmen. Solche extremale Graphen können manchmal nur durch Verwendung anderer mathematischer Konzepte beschrieben werden, beispielsweise spezieller Ziffernentwicklungen für die relevanten Parameter wie etwa die Ordnung des Graphen. Andererseits sind Ziffernentwicklungen auch ein zentrales Konzept in unseren Untersuchungen von Fragestellungen in der Kryptographie. Asymmetrische Kryptographie beruht auf der effizienten Berechnung von Einwegfunktionen, wobei wir uns hier auf die Berechnung von skalaren Vielfachen nP eines Elements P einer abelschen Gruppe konzentrieren. Klassischerweise stellt man n durch eine Ziffernentwicklung dar und führt die Skalarmultiplikation mittels Horner-Schemas durch, was zum sogenannten "double-and-add"-Verfahren führt. Neben der multiplikativen Gruppe eines endlichen Körpers ist auch die Punktgruppe einer elliptischen (oder auch hyperelliptischen) Kurve weit verbreitet, wobei hier zusätzliche Strukturen dieser Gruppen viele Variationen des ursprünglichen Verfahrens zulassen. Insbesondere sind Ziffernentwicklungen zu gewissen nicht-rationalen Basen von Interesse. Ein Ziel des Projekts ist es, in verschiedenen Konfigurationen optimale Entwicklungen zu bestimmen und die resultierenden Algorithmen einer präzisen asymptotischen und probabilistischen Analyse im Sinne von D. E. Knuth zu unterziehen.

Während Menschen üblicherweise an das klassische Dezimalsystem (Basis Zehn mit Ziffern von 0 bis 9) gewöhnt sind, verwenden Computer meist das Binärsystem (Basis Zwei) mit Ziffern 0 und 1. Für spezielle Anwendungen hingegen stellen sich andere Ziffernsysteme als nützlicher heraus. Zum Beispiel ist es in der Kryptographie, die man etwa für die sichere Kommunikation im Internet verwendet, effizienter, Ziffernsysteme in Basis Zwei mit Ziffern -1, 0 und 1 zu verwenden. Das Gewicht, d.h. die Anzahl der von NullverschiedenenZiffern,beeinflusstdanndie Laufzeitdes Verschlüsselungsalgorithmus. Erlaubt man auch die Ziffer -1, kann man ein- und dieselbe Zahl auf viele verschiedene Arten darstellen. Damit ist es möglich, eine Entwicklung minimalen Gewichts auszuwählen. Es ist bekannt, dass das durchschnittliche Gewicht bei Verwendung der Ziffern 0 und 1 gleich der Hälfte der Anzahl der Ziffern ist, während Zulassen von -1 das durchschnittliche Gewicht auf ein Drittel der Anzahl der Ziffern senkt. Benutzt man noch mehr Ziffern, verringert sich das durchschnittliche Gewicht noch weiter. Es war ein zentrales Ziel des Projekts, das durchschnittliche Gewicht für eine große Klasse von Ziffernentwicklungen so präzise wie möglich zu bestimmen. Es stellte sich heraus, dass ein passendes Werkzeug, um solche Entwicklungen zu beschreiben, sogenannte Transduktor-Automaten sind. Diese können durch endlich viele Zustände und Übergänge zwischen diesen Zuständen be- schrieben werden, welche die Eingabedaten (die Standardbinärentwicklung) in die gewünschte Entwicklung übersetzen. Das durchschnittliche Gewicht sowie die zugehörige Standardabweichung kann dann durch Betrachten entsprechender Eigenschaften des Transduktor- Automaten analysiert werden. Die Resultate hängen sehr stark von den Zusammenhangseigenschaften des Transduktors ab. Im einfachsten Fall stellt sich heraus, dass das Gewicht einer zufälligen Entwicklung annähernd normalverteilt ist. Eine solche Analyse ist typisch für das wissenschaftliche Gebiet der mathematischen Analyse von Algorithmen. Dort ist das Ziel, die Laufzeit verschiedener Algorithmen so präzise wie möglich zu bestimmen, wobei üblicherweise Methoden aus verschiedenen Teilgebieten der Mathematik herangezogen werden. Ein anderes Beispiel eines im Rahmen dieses Projekts untersuchten Algorithmus ist der sogenannte Dual-Pivot-Quicksort-Algorithmus. Das Sortieren von Listen von Werten ist ein wesentlicher Baustein in vielen Anwendungen und sollte so effizient wie möglich durchgeführt werden. Die Laufzeit eines Sortieralgorithmus wird üblicherweise durch die Anzahl von erforderlichen Vergleichen gemessen. Indem man die Anzahl der Vergleiche durch einen sogenannten Gitterpfad in einem speziellen Wahrscheinlichkeitsmodell beschreibt, war es möglich zu zeigen, dass eine bestimmte Variante von Dual-Pivot- Quicksort in der Tat optimal in ihrer Klasse ist, und ihre Laufzeit konnte mit sehr hoher Präzision bestimmt werden. Gitterpfade können auch benutzt werden, um gewisse Baumparameter zu beschreiben. Da- bei handelt es sich um Graphen, die aus Knoten und Verbindungen zwischen diesen Knoten bestehen, ohne dass dabei Kreise entstehen. Hier analysierten wir verschiedene Wachstumsparameter dieser Bäume, zum Beispiel die Horton Strahler-Zahl, die auch zur Beschreibung von Flussnetzwerken verwendet wird. Um unsere Resultate zu erzielen, waren ausführliche Computerberechnungen erforderlich. Dazuimplementierten wir zwei Module für das quelloffene Computeralgebrasystem SageMath: eines für Manipulationen von Transduktor- Automaten und das andere für Berechnungen mit asymptotischen Entwicklungen. Das Ziel bei der Implementierung war es, vielseitige Module zu entwickeln, die den vollen Funktionsumfang von SageMath bei Berechnungen mit Transduktor- Automaten bzw. asymptotischen Entwicklungen benutzen.