Automatische Entwicklung erzeugender Funktionen

Viele interessante Probleme in den Anwendungen, wie z.B. Analyse von Algorithmen, können auf kombinatorische Abzählprobleme reduziert werden. In vielen Fällen ist es jedoch nicht möglich, explizite Ausdrücke für die betrachteten Anzahlen zu bekommen oder diese Ausdrücke lassen die Größenordnung der Zahlen nicht erkennen. Eine wichtige Methode zur Gewinnung des asymptotischen Verhaltens ist das Übersetzen der Folge der Anzahlen in eine erzeugende Funktion. Damit wird das Problem mit analytischen Methoden behandelbar. Das Ziel des Projekts ist die Entwicklung von algorithmisch anwendbaren Methoden zur Gewinnung von asymptotischen Entwicklungen für die Koeffizienten von erzeugenden Funktionen. Insbesondere sollen die folgenden Themen behandelt werden: 1.Die Erweiterung des Zulässigkeitsbegriffs von Hayman auf Funktionen in mehreren Variablen. 2. Die asymptotische Lösung von Systemen von Funktionalgleichungen, insbesondere f"ur den Fall von nicht stark zusammenhängenden Abhängigkeitsgraphen. 3.Vorbereitung der Resultate auf Automatisierung und Implementierung in MAPLE Ad 1: Ein Zugang zur Gewinnung von Koeffizienten einer erzeugenden Funktion ist Haymans Begriff der Zulässigkeit und dessen Modifikationen. Einerseits kennt man die asymptotische Entwicklung der Koeffizienten von zulässigen Funktionen, andererseits erfüllen diese Funktionen Abschlußbedingungen, die es ermöglichen, aus einer gegebenen Menge von zulässigen Funktionen weitere zu konstruieren. Da kombinatorische Abzählprobleme, die von mehreren Parametern abhängen, auf erzeugende Funktionen in mehreren Variablen führen, ist eine Verallgemeinerung des Haymanschen Konzeptes auf Funktionen in mehreren Variablen wünschenswert. Ad 2: Abzählprobleme, bei denen die kombinatorischen Strukturen rekursiv definiert sind, führen in der Regel zu erzeugenden Funktionen, die implizit durch ein System von Funktionalgleichungen gegeben sind. Für den Fall eines stark zusammenhängenden Abhängigkeitsgraphen ist in der Literatur bereits behandelt. Ziel des Projekts ist die Erweiterung dieser Resultate auf allgemeinere Systeme von Funktionalgleichungen. Ad 3: Für univariate zulässige Funktionen existieren bereits MAPLE Programme. Es ist geplant im Rahmen des Projekts diese Programm zu erweitern, sodaß auch Funktionen in mehreren Variablen behandVariablen behandelt werden können. Da zulässige Funktionen Abschlußbedingungen erfüllen, sind sie gut geeignet zur Automatisierung. Was Systeme von Funktionalgleichungen betrifft, ist geplant, zunächst die vorhandenen Resultate über stark zusammenhängende Abhängigkeitsgraphen zu implementieren. Zur Behandlung des allgemeinen Falls ist ein besseres Verständnis der zugrundeliegenden Theorie erforderlich. Dies auszuarbeiten ist Teil des Projekts.

Zum Lösen kombinatorischer Anzahlprobleme beniötigt man häufig die Koeffizienten von Potenzreihen. Sogenannte Hayman-zulässige Funktionen sind analytische Funktionen, deren Koeffizienten auf eine ziemlich einfache Art und Weise bestimmt werden können. Außerdem erfüllen sie bestimmte Abgeschlossenheits- Eigenschaften (AE). Das impliziert, daßes einfach ist, Hayman-zulässige Funktionen zu konstruieren, sofern man eine Klasse zulässiger Funktion kennt. Andererseits kann man eine gegebene Funktion gemäß den AE zerlegen und so auf H-Zulssigkeit testen. Einer der Hauptresultate des Projektes war die Verallgemeinerung von HZulässigkeit auf Funktionen in mehreren Variablen derart, daß sie noch AE erfüllen. Dies wurde auf zwei Arten getan: Erstens wurde eine Klasse von Funktionen in zwei Variablen definiert, deren Gestalt häufig in der probabilistischen Kombinatorik auftritt. Für diese Klasse, wurde ein Software-Tool (in MAPLE zum Testen von Zulässigkeit entwickelton Zweitens wurde ein Begriff der HZulässigkeit für Funktionen in mehereren Variablen entwickelt. Diese Funktionsklasse hat Anwendungen in der abzählenden Kombinatorik und ebenfalls starke AE. Ein weiteres Ergebnis war die Verbesserung eines Resultats von Lefmann und Savicky zur Beziehung zwischen der Komplexität einer Booleschen Funktion und der Wahrscheinlichkeit, daß ein zuf`allig gewählter Term, der aus Booleschen Variablen (und ihren Negationen) und den logischen Operatoren UND und ODER besteht, diese Funktion darstellt. Dies konnte durch Übersetzung der auftretenden Strukturen in Systeme von Funktionsgleichungen erzielt werden. Weitere Fortschritte sind in der Analyse baumartiger Strukturen erzielt worden. Es konnten Formparameter wie z.B. Profil, Knotengrad, Abstnde zwischen zwei Knoten, Knotenhöhe, Blatthöhen, etc. einiger Baumklassen (unmarkierte und monoton markierte Bäume) bestimmt werden.