Automatische Entwicklung multivariater erzeugender Funktionen in kombinatorischen Abzählproblemen

01.12.2002 - 31.10.2005
Forschungsförderungsprojekt
Viele inetressante 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ür 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. Der 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 Programme zu erweitern, sodaß auch Funktionen in mehreren Variablen 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.

Personen

Projektleiter_in

Institut

Förderungsmittel

  • FWF - Österr. Wissenschaftsfonds (National) Fonds zur Förderung der wissenschaftlichen Forschung (FWF)