Titelaufnahme

Titel
Parking functions and generalizations / Georg Seitz
VerfasserSeitz, Georg
Begutachter / BegutachterinPanholzer, Alois
Erschienen2009
UmfangIV, 92 Bl. : graph. Darst.
HochschulschriftWien, Techn. Univ., Dipl.-Arb., 2009
Anmerkung
Zsfassung in dt. Sprache
SpracheEnglisch
DokumenttypDiplomarbeit
Schlagwörter (DE)Parkfunktionen / diskrete Mathematik
Schlagwörter (EN)parking functions / discrete mathematics
URNurn:nbn:at:at-ubtuw:1-23417 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Parking functions and generalizations [0.48 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Betrachte eine Einbahnstraße mit n nummerierten Parkplätzen in einer Reihe.

m aufeinanderfolgende Fahrer wollen in dieser Straße parken, wobei jeder einen bevorzugten Parkplatz hat. Jeder Fahrer fährt zu der gewählten Stelle und parkt dort, falls sie frei ist. Falls nicht, nimmt er den nächsten freien Parkplatz, falls vorhanden. Andernfalls verlässt er die Straße.

Die Funktion p : [m] ->[n], die jedem Fahrer i den bevorzugten Parkplatz p(i) zuweist, heißt Parkfunktion (parking function), falls alle m Fahrer erfolgreich parken können.

Viele Beziehungen zwischen Parkfunktionen und anderen kombinatorischen Objek- ten wie zum Beispiel markierten Bäumen, azyklischen Funktionen, Warteschlangen, nichtkreuzenden Partitionen und speziellen Polytopen sind bekannt.

Parkfunktionen wurden auf verschiedene Arten verallgemeinert, und sie treten in der Analyse von Hashing-Varianten und Sortier-Algorithmen auf.

In dieser Arbeit werden einige grundlegende Eigenschaften von Parkfunktionen gesammelt. Es wird gezeigt, wo Parkfunktionen bei der Analyse von Hashtabellen auftreten, und ein neues Resultat über Haltepunkte (breakpoints) von Parkfunktionen wird präsentiert.

Anschließend werden bekannte Relationen zwischen Parkfunktionen und azyklis- chen Funktionen bzw. markierten Bäumen sowie eine Beziehung zwischen Parkfunktionen und Warteschlangen behandelt.

Schließlich werden Verallgemeinerungen von Parkfunktionen studiert, unter anderem bucket parking functions, x-parking functions und defective parking functions.

Zusammenfassung (Englisch)

Consider a one-way street with n numbered parking slots in a line. There are m consecutive drivers who wish to park in this street, each of which has a preferred parking slot in mind. Each driver proceeds to the chosen place and parks there, if it is empty. If not, the driver takes the first available space, if any. If no space is empty, the driver leaves.

The function p : [m] ->[n] which associates each driver i with his preferred parking slot p(i) is called a parking function if all drivers are able to park.

Many relations between parking functions and other combinatorial objects are known, such as labeled trees, acyclic functions, priority queues, noncrossing partitions and special polytopes. Parking functions have been generalized in various ways, and they appear in the analysis of hashing variants and sorting algorithms.

In this work, we collect some basic properties of parking function. We show where they appear in the analysis of hashing with linear probing and then give a new result on breakpoints.

Furthermore, we present known relations between parking functions, acyclic functions and labeled trees and a relation between parking functions and priority queues.

Finally, we study generalizations of parking functions, such as bucket parking functions, x-parking functions und defective parking functions.