|
Die Analyse von Algorithmen beschäftigt sich mit der
Untersuchung von Kostenparametern wie etwa Laufzeit oder
Speicherbedarf konkreter Algorithmen. Dabei kann grob
unterschieden werden in die Bestimmung des sogenannten
"worst case"-Verhaltens, bei dem es darum geht,
Extremsituationen zu ermitteln, die den Kostenparameter
des Algorithmus möglichst groß werden lassen, und
des Algorithmus möglichst groß werden lassen, und
in die Bestimmung des "average case"-Verhaltens, bei
dem auf der Basis eines Wahrscheinlichkeitsmodells für
dem auf der Basis eines Wahrscheinlichkeitsmodells für
die Eingabedaten das durchschnittliche Verhalten
des Kostenparameters analysiert wird.
Im gegenständlichen Vortrag wurde an Hand einiger
ausgewählter baumartiger Datenstrukturen (binary search trees,
digital tries, Patricia tries, digital search trees) versucht,
die grundlegenden Ideen der average case-Analyse zu
erläutern. Charakteristische Schritte, wie die
Auffindung kombinatorischer Dekompositionen der zugrundeliegenden
Bäume, die Übersetzung in funktionale Beziehungen zwischen
geeigneten erzeugenden Funktionen und die Gewinnung
von expliziten bzw. asymptotischen Resultaten wurden exemplarisch
erläutert. Ziel war die Verdeutlichung der Tatsache, dass in
diesem Bereich Methoden aus verschiedenen Bereichen der Mathematik,
wie Graphentheorie, Kombinatorik, reelle und komplexe Analysis
in einem Zusammenspiel zur Anwendung zu bringen sind.
Bücher: Bücher:
|