Average Case-Analyse von Algorithmen

Forschungsprojekt P 14200Average Case-Analyse von AlgorithmenPeter KIRSCHENHOFER11.10.1999 Die Analyse von Algorithmen ist ein schnellwachsencles wissenschaftliches Teilgebiet im Grenzbereich zwischen Mathematik und Informatik. Vom Standpunkt der Anwendungen aus betrachtet, ist es bedeutend, die dominierenden Kostenparameter spezieller Algorithmen wie Laufzeit oder Speicherbedarf zu analysieren. Dies gilt insbesondere auch für das Studium zahlentheoretischer Algorithmen. Dazu zahlen wir u.a. auch die Analyse von Algorithmen bei denen digitale Eigenschaften der Schlüssel von Datenmengen eine entscheidende Rolle spielen. Im Bereich der Analyse von Algorithmen können zwei verschiedene Standpunkte unterschieden werden. Bei der worst case-Analyse wird das Verhalten des Algorithmus unter solchen Umständen untersucht, die zu besonders schlechtem Verhalten führen. Obwohl diese Art der Analyse zahlreiche interessante mathematische Probleme bei der Konstruktion von extremen Situationen hervorbringt, wird dadurch keine gute Information über das Verhalten des Algorithmus im allgerneinen gegeben, da extreme Situationen nur selten auftreten. Im Gegensatz dazu beschäftigt sich die average case-Analyse mit den durchschnittlichen Kosten des Algorithmus unter Annahme eines geeigneten Wahrscheinlichkeitsmodells für die Eingangsdaten. Es stellt sich heraus, daß die average case-Analyse Methoden aus verschiedenen mathernatischen Teilgebieten wie Kombinatorik, Reelle und Komplexe Analysis oder Wahrscheinlichkeitstheorie benötigt. Oftmals agieren die Algorithmen auf kombinatorischen Objekten (z.B.: 0,1-Folgen oder Binärbäumen); die Relationen zwischen den betrachteten Parametern (z.B.: Rekursionen) lassen sich oftmals in Funktionalgleichungen, Differentialgleichungen oder allgemeinere Beziehungen zwischen geeigneten Erzeugenden Funktionen übersetzen. Um explizite oder asymptotische Resultate über die Koeffizenten dieser Funktionen zu erhalten, kann man sich analytischer Methoden wie Singularitätenanalyse oder Integraltransformationen bedienen. Es stellt sich heraus, daß Methoden aus der analytischen Zahlentheorie dabei eine bedeutende Rolle spielen, da spezielle Funktionen wie die Riemannsche oder die Hurwitzsche Zetafunktion oftmals in ihren Mellintransformierten auftreten. Transformationsresultate, wie die Funktionalgleichung für die Dedekindsche Etafunktion und verwandte Resultate haben große Bedeutung für die asymptotische Analyse höher Momente spezieller Kostenparameter von Algorithmen. Ziel diese Projektes ist es, grundlegende Methoden der average case-Analyse von Algorithmen in verschiedene Richtungen weiterzuentwickeln, wie etwa: - Die Entwicklung von Methoden, die es erlauben, das asymptotische Verhalten gewisser alternierender Summen unmittelbar zu bestimmen, die häufig in der Analyse von Datenstrukturen auftreten, die auf digitalen Eigenschaften von Schlüsseln beruhen; - Die Untersuchung von kombinatorischen und analytischen Eigenschaften bestimmter Familien von Orthogonalpolynomen, die jüngst im Zusammenhang mit dem Studium spezieller diophantischer Gleichungen aufgetreten sind; - Die average case-Analyse von digitalen zahlentheoretischen Funktionen von einem automatentheoretischen Standpunkt aus; - Die Übersetzung von Rekursionen und kombinatorischen Dekompositionen in mehr oder weniger unmittelbare Information über das (asymptotische) Verhalten gewisser Kostenparameter von Algorithmen. Zusätzliche Forschungsprobleme sind im Zusammenhang mit anderen Projekten dieses Forschungsschwerpunktes zu erwarten, insbesondere mit den Projekten von Drmota, Hellekalek, Larcher, sowie Tichy und Kirschenhofer.

In diesem Projekt wurden algorithmische Fragestellungen zahlen-theoretischen Ursprungs mit Hilfe kombinatorischer Methoden untersucht. Dieses Projekt wurde mit 1.5.2002 unter dem Titel "Kombinatorische Grundlagen der Analyse zahlentheoretischer Algorithmen" in den Forschungsschwerpunkt "Zahlentheoretische Algorithmen und Anwendungen" eingegliedert. Zentraler Inhalt dieses Projekts war die Bereitstellung kombinatorischer Grundlagen und Methoden für Aufgaben im Zusammenhang mit algorithmischen Fragestellungen in der Zahlentheorie. Ein erster Schwerpunkt waren dabei diophantische Gleichungen, das heißt Gleichungen, die im Bereich der ganzen Zahlen zu lösen sind. Fragestellungen im Zusammenhang mit derartigen Gleichungen werden in der Mathematik bereits seit der Antike behandelt. Viele derzeit untersuchte Fragestellungen in diesem Problemkreis haben einen algorithmischen Hintergrund. Im gegenständlichen Projekt wurden dabei Gleichungen zwischen Polynomen betrachtet, die sich aus kombinatorischen Abzählproblemen ergeben. Es konnte gezeigt werden, dass für gewisse Klassen derartiger Polynome, die sich aus strukturell verwandten kombinatorischen Problemstellungen ergeben, die zugehörigen Diophantischen Gleichungen unter geeigneten Zusatzvoraussetzungen nur endlich viele Lösungen besitzen. Für bestimmte Werte der zugrundeliegenden Parameter können diese Lösungen auch konstruktiv bestimmt werden. Beim Beweis der Resultate kommen einerseits Methoden aus dem Bereich der enumerativen Kombinatorik, andererseits aber auch Resultate über spezielle Funktionen, wie Systeme von Orthogonalpolynomen zum Einsatz. Ein weiterer Schwerpunkt war die Untersuchung von Ziffernsystemen und Ziffernfunktionen über algebraischen Zahlkörpern mit kombinatorischen Methoden aus der Automatentheorie. Dabei geht es um die Existenz und die Eigenschaften von Systemen zur Zahlendarstellung in Zahlbereichen wie den Gaußschen ganzen Zahlen und allgemeineren algebraischen Strukturen. Fragestellungen dieser Art sind u.a. von großer Bedeutung bei der Konstruktion von kryptographischen Systemen, d.h. Systemen zur Verschlüsselung von Daten unter dem Gesichtspunkt der Geheimhaltung. Stellt man die Zahlen, deren "ganzzahliger Anteil" gleich 0 ist geometrisch dar, so ergibt sich bei den meisten betrachteten Ziffernsystemen ein fraktales Gebilde. Im gegenständlichen Projekt wurden sogenannte Zählautomaten aus der Theorie der Formalen Sprachen benützt um Resultate über diese Fraktale herzuleiten, die wichtige Rückschlüsse auf die zugrundeliegenden Zahlsysteme erlauben. Eine Reihe der im Rahmen dieses Projektes durchgeführten Forschungsarbeiten erfolgten in Vernetzung mit Projekten des Forschungsschwerpunktes S83 "Zahlentheoretische Algorithmen und Anwendungen" des FWF.