|
Die kombinatorische Analyse von Bäumen (insbes. Anzahlfragen)
spielt wegen deren rekursiver Natur eine grundlegende Rolle bei
der average-case Analyse von rekursiven Algorithmen. Diese
kombinatorisch-analytische Methodik, die von P. Flajolet und
seinen Mitarbeitern bis hin zur Entwicklung von software
zur exakten und asymptotischen Behandlung von kombinatorischen
Anzahlproblemen und zur automatischen Analyse von Algorithmen
getrieben wurde (gfun, gdev, gaia, luo, combstruct), soll hier
an drei Beispielen erläutert werden: Bestimmung von Anzahlen
und Parameter für Binärbäume, Berechnung der Asymptotik
und Parameter für Binärbäume, Berechnung der Asymptotik
der mittleren inneren Weglänge von Binärbäumen, Kostenanalyse
für das symbolische Differenzieren.
für das symbolische Differenzieren.
Dieser Vortrag, wie auch derjenige über formale Reihen, Dieser Vortrag, wie auch derjenige über formale Reihen, soll als Vorbereitung für die Vorträge des Gastdozenten soll als Vorbereitung für die Vorträge des Gastdozenten Prof. Kirschenhofer dienen.
|
|
Formale Potenzreihen sind ein klassisches Hilfsmittel bei der Untersuchung
von kombinatorischen Zählproblemen. Neben der Möglichkeit, Anzahlfragen
von kombinatorischen Zählproblemen. Neben der Möglichkeit, Anzahlfragen
kompakt zu formulieren und (häufig, nicht immer) in diesem Formalismus
elegant zu lösen, ist insbesondere die enge Verwandschaft zur Analysis
elegant zu lösen, ist insbesondere die enge Verwandschaft zur Analysis
von Interesse, was immer dann zum Tragen kommt, wenn "geschlossene" Lösungen
von Interesse, was immer dann zum Tragen kommt, wenn "geschlossene" Lösungen
nicht möglich sind und man wenigstens Informationen über das asymptotische
nicht möglich sind und man wenigstens Informationen über das asymptotische
nicht möglich sind und man wenigstens Informationen über das asymptotische
nicht möglich sind und man wenigstens Informationen über das asymptotische
Verhalten von Anzahlfunktionen erhalten möchte (wie z.B. in der Analyse
Verhalten von Anzahlfunktionen erhalten möchte (wie z.B. in der Analyse
von Algorithmen).
Der Vortrag behandelt die grundlegenden arithmetischen Eigenschaften von formalen Reihen und zielt insbesondere auf die Behandlung der Komposition und deren Umkehrung. Das Umkehrproblem ist klassisch mit dem Namen von J.L Lagrange verbunden. Dessen berühmte Umkehrformel lässt sich so J.L Lagrange verbunden. Dessen berühmte Umkehrformel lässt sich so formulieren, dass die enge Beziehung zu Baumstrukturen offensichtlich wird. Tatsächlich ist diese Umkehrformel ein wichtiges technisches Hilfsmittel bei der Lösung von Anzahlproblemen für Bäume (siehe den einen bei der Lösung von Anzahlproblemen für Bäume (siehe den einen bei der Lösung von Anzahlproblemen für Bäume (siehe den einen bei der Lösung von Anzahlproblemen für Bäume (siehe den einen der Vorträge von F. Strüber) - sie lässt sich auch (wie in einem Vortrag der Vorträge von F. Strüber) - sie lässt sich auch (wie in einem Vortrag von E. Frank dargestellt) mit rein kombinatorischen Argumenten für Bäume von E. Frank dargestellt) mit rein kombinatorischen Argumenten für Bäume und mit ihnen verwandten Objekten (Gitterpfade, Lukasiewicz-Sprache) beweisen. Als Anwendung wird hier die sog. beta-Statistik berechnet, i.e. die Bestimmung der Anzahl von ebenen Bäumen mit gegebener Anzahl von Knoten und von Blättern. Dieser Vortrag, wie auch derjenige über "Bäume und average-case Analyse von Dieser Vortrag, wie auch derjenige über "Bäume und average-case Analyse von Algorithmen", soll als Vorbereitung für die Vorträge des Gastdozenten Algorithmen", soll als Vorbereitung für die Vorträge des Gastdozenten Prof. P. Kirschenhofer dienen.
|