Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0923.68097
Panholzer, Alois
Studies on the average form of some tree families with special consideration of their applications to computer science. (Untersuchungen zur durchschnittlichen Gestalt gewisser Baumfamilien mit besonderer Berücksichtigung von Anwendungen in der Informatik.) (German)
[B D] Wien: Österreichischer Kunst- und Kulturverlag. 219 S. (1999). ISBN 3-85437-176-4

Summary: Die vorliegende Arbeit ist der Analyse von bestimmten, in der Informatik relevanten Baumstrukturen gewidmet. Verschiedenste Klassen von Bäumen treten als mathematische Objekte nicht nur direkt oder indirekt in vielen Algorithmen auf, sondern besitzen auch eine Reihe von Anwendungen ausserhalb der Informatik.\par Da Bäume im wesentlichen die einfachsten nichttrivialen rekursiv definierten Objekte darstellen, lässt sich dieser Sachverhalt bei der Analyse der Verteilung von bestimmten Baumparametern oftmals übersetzen in Rekursionen der betrachteten Grössen. Unter Verwendung von -- je nach Art der Rekursion unterschiedlich anzusetzenden -- Erzeugenden Funktionen erhalten wir daraus Gleichungen für diese Funktionen. Mit Hilfe der sogenannten symbolischen Operatormethode sind diese Gleichungen meist auch direkt aus der formalen Gleichung der Bäume zu erhalten.\par Nun kann man versuchen, die so erhaltenen Gleichungen dieser Erzeugenden Funktionen der Verteilungen zu lösen. Dies ist zwar oftmals nicht möglich, aber man kann aus diesen Beziehungen leicht Gleichungen für die Erzeugenden Funktionen der Faktoriellen Momente der betrachteten Grössen gewinnen, welche einfacher zu lösen sind.\par Schliesslich bleibt noch das Ablesen der Koeffizienten, um zu exakten Resultaten für die gesuchten Grössen zu gelangen. Gelingt dies nicht bzw. sind die erhaltenen Ergebnisse zu wenig aufschlussreich, kann man auch versuchen, direkt aus der Erzeugenden Funktion das asymptotische Verhalten der betrachteten Parameter zu bestimmen.\par Dieses grobe Schema wird im wesentlichen bei der Analyse aller fünf hier behandelten Problemkreise verwendet. Als verwendete mathematische Methoden seien aus der Theorie der formalen Reihen die symbolische Operatormethode und die Inversionsformel von Lagrange erwähnt. Für die Lösung der auftretenden Differentialgleichungen werden verschiedene Methoden aus der Theorie der Gewöhnlichen Differentialgleichungen, wie beispielsweise die Variation der Konstanten, angewandt. \par Für das Ablesen der Koeffizienten werden einerseits eine Reihe von Beziehungen für Harmonische Zahlen verwendet, andererseits wird für die Gewinnung von geschlossenen Formen bestimmter Summen Zeilberger's bzw. Gosper's Algorithmus benützt. Um asymptotische Ergebnisse zu erhalten, werden Methoden angewandt, die direkt von den exakten Resultaten ausgehen, wie beispielsweise die Euler'sche Summenformel oder das Arcussinusgesetz. Bei Bedarf wird allerdings ausgehend von den Erzeugenden Funktionen die Singularitätenanalyse durchgeführt. Weiter finden für die Bestimmung einer Grenzverteilung probabilistische Verfahren Verwendung, wie beispielsweise der Grenzwertsatz von Lévy.\par Es sei auch angemerkt, dass in dieser Arbeit ausgiebig von den Möglichkeiten der zur Verfügung stehenden Formelmanipulationsprogramme, im speziellen des Softwarepaketes Maple, Gebrauch gemacht wurde. Ohne Softwareunterstützung ist die Berechnung eines Grossteils der hier gebrachten Ergebnisse nicht mehr durchführbar.

MSC 2000:: *68R10 Graph theory in connection with computer science
68-02 Research monographs (computer science)

Keywords: tree structure

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.
	Elementary number theory. Primes, congruences, and secrets.

Simple Search

Zentralblatt MATH Berlin [Germany]