The subject of this thesis is the application of computer algebra systems, MAPLE in particular, to asymptotic problems coming from discrete mathematics. Two specific problems are examined.<br />The first is concerned with patterns in labeled trees. We count the average number of times a particular pattern matches a tree of size n. Assuming that every tree of size n is equally likely, it is shown that the limiting distribution of the number of occurrences of the pattern is asymptotically normal, with mean value ~[mu]*n and variance ~[sigma]2 [[sigma] hoch 2]*n with computable constants [mu]>0 and [sigma]>=0. We provide an algorithm to compute [mu] explicitly and a MAPLE program that does most of the work. This part of the thesis is based on the paper ``The Distribution of Patterns in Random Trees'' coauthored with Frédéric Chyzak and Michael Drmota.<br />In the second part of the thesis, we generalize a class of functions which were introduced by Hayman and which we thus call Hayman-admissible. Hayman proved that the suitably normalized coefficients of these functions asymptotically follow a Gaussian distribution. He also assembled a useful list of closure properties, i.e., operations on Hayman-admissible functions that generate other Hayman-admissible functions. We generalize Hayman's result to functions in two dimensions, conserving many closure properties. We also present a MAPLE program that tests if a given function belongs to this class. This part of the thesis is based on the paper ``Extended Admissible Functions and Gaussian Limiting Distributions'' coauthored with Michael Drmota and Bernhard Gittenberger.<br />
de
dc.description.abstract
Diese Doktorarbeit beschäftigt sich mit mathematischen Methoden zur asymptotischen Behandlung von diskreten mathematischen Problemen mit Computer-Unterstützung. Konkret werden dabei zwei verschiedene Probleme behandelt.<br />Im ersten Teil der Arbeit werden Muster in (markierten) Bäumen untersucht. Ein Muster ist ein bestimmter vorgegebener Baum. Wir nehmen alle Bäume einer bestimmten Größe n als gleich wahrscheinlich an und untersuchen, wie oft das vorgegebene Muster im Durchschnitt vorkommt. Wir zeigen, dass die Anzahl der Muster einen zentralen Grenzwertsatz erfüllt. Im Speziellen kann für jedes Muster auch durch Lösung eines zugehörigen polynomiellen Gleichungssystems der Erwartungswert explizit berechnet werden. Ein MAPLE-Programm, das den größten Teil dieser Berechnungen erledigt, ist Teil der Arbeit. Wir besprechen weiters einige Möglichkeiten der Verallgemeinerung auf andere Muster oder andere Graphen. Dieser Teil der Dissertation basiert auf der gemeinsamen Arbeit ``The Distribution of Patterns in Random Trees'' mit Frédéric Chyzak und Michael Drmota.<br />Im zweiten Teil der Arbeit beschäftigen wir uns mit dem Begriff der ``zulässigen'' Funktionen, den Hayman 1956 eingeführt hat. Er bewies, dass geeignet normalisierte Koeffizienten von zulässigen Funktionen asymptotisch einer Normalverteilung folgen. Hayman präsentierte auch eine Liste von Basisfunktionen und Abschlussbedingungen, unter denen aus zulässigen Funktionen andere zulässige Funktionen erzeugt werden können. Wir verallgemeinern Haymans Ergebnis auf Funktionen in zwei Variablen, um damit einen weiteren Parameter untersuchen zu können, und präsentieren ein MAPLE-Programm, das für eine beliebige gegebene Funktion automatisch testet, ob sie zulässig (``extended admissible'') ist. Dieser Teil der Dissertation basiert auf der gemeinsamen Arbeit ``Extended Admissible Functions and Gaussian Limiting Distributions'' mit Michael Drmota und Bernhard Gittenberger.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Baum
de
dc.subject
Graphmarkierung
de
dc.subject
Muster
de
dc.subject
Asymptotik
de
dc.subject
Maple
de
dc.subject
Diskrete Mathematik
de
dc.title
Computer-assisted analytic methods for discrete problems
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Thomas Klausner
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Kirschenhofer, Peter
-
tuw.publication.orgunit
E104 - Institut für Diskrete Mathematik und Geometrie
-
dc.type.qualificationlevel
Doctoral
-
dc.identifier.libraryid
AC04219874
-
dc.description.numberOfPages
85
-
dc.identifier.urn
urn:nbn:at:at-ubtuw:1-13682
-
dc.thesistype
Dissertation
de
dc.thesistype
Dissertation
en
dc.rights.identifier
In Copyright
en
dc.rights.identifier
Urheberrechtsschutz
de
tuw.advisor.staffStatus
staff
-
tuw.assistant.staffStatus
staff
-
item.openaccessfulltext
Open Access
-
item.openairecristype
http://purl.org/coar/resource_type/c_db06
-
item.grantfulltext
open
-
item.mimetype
application/pdf
-
item.languageiso639-1
en
-
item.openairetype
doctoral thesis
-
item.fulltext
with Fulltext
-
item.cerifentitytype
Publications
-
crisitem.author.dept
E101 - Institut für Analysis und Scientific Computing