Über die Analyse von zwei fundamentalen randomisierten Algorithmen

Im ersten Teil der vorliegenden Arbeit werden Multi-Pivot-Quicksort-Algorithmenbetrachtet. Die Idee mehr als ein Pivotelement im Quicksort-Algorithmus zunutzen, erschien über viele Jahre als unpraktikabel. Dies änderte sich, als imJahr 2009 ein Dual-Pivot-Algorithmus von V. Yaroslavskiy zumStandard-Sortierverfahren in Java 7 wurde. Die vorliegende Arbeit stellt eineStudie von Multi-Pivot-Quicksort-Algorithmen dar, also Quicksort-Varianten, diemit mehr als einem Pivotelement arbeiten. Sie beschreibt dieKonstruktionsprinzipien von 2-Pivot-Algorithmen in Bezug auf die bei derSortierung notwendigen Schlüsselvergleiche. Ein Ergebnis dieser Untersuchungsind zwei optimale und leicht zu implementierende 2-Pivot-Algorithmen. DieVerallgemeinerung auf >= 3 Pivotelemente benötigt nur kleine Anpassungen. DieseArbeit betrachtet außerdem die theoretische Analyse von Kostenmaßen, die esermöglichen, Multi-Pivot-Quicksort-Algorithmen hinsichtlich ihres Speicher- undCacheverhaltens zu vergleichen. Sie schließt mit einer Laufzeitstudie derbesprochenen Algorithmen. Der zweite Teil der Arbeit beschäftigt sich mit dem Einsatz von Hashfunktionenin Algorithmen und Datenstrukturen. Hashfunktionen bilden eine Kernkomponente,z.B. beim Aufbau einer Hashtabelle oder bei Lastbalancierung. Oft wird dabeieine unrealistische Annahme getätigt: Die Hashwerte seien voll zufällig. DieSpeicherplatzkomplexität einer solchen Funktion ist für den praktischen Einsatzfür unverhältnismäßig hoch. Das Ziel ist, einfache Konstruktionen zu finden,deren Zufallseigenschaften beweisbar gut sind. Diese Arbeit beschreibt einesolche einfache Konstruktion von Hashfunktionen, die in einer Vielzahl vonAnwendungen beweisbar gut ist. Zu diesen Anwendungen zählen Cuckoo Hashing miteinem sogenannten Stash, die Konstruktion einer perfekten Hashfunktion, dieSimulation einer uniformen Hashfunktion, verschiedene Algorithmen zurLastbalancierung und verallgemeinertes Cuckoo Hashing in einer leichtabgeschwächten Variante mit verschiedenen Einfügealgorithmen. Der zentraleBeitrag dieser Dissertation ist ein einheitliches Analysekonzept. Diesesermöglicht es, eine auf Hashfunktionen basierende Datenstruktur oder einen aufHashfunktionen basierenden Algorithmus nur mit Mitteln der Theorie vonZufallsgraphen zu analysieren, ohne Details der Hashfunktion offenzulegen.The first part of this thesis considers multi-pivot quicksort algorithms. Theidea of using more than one pivot element in quicksort was considered to beimpractical. This changed when a dual-pivot algorithm replaced thewell-engineered quicksort-based sorting algorithm in Java 7. The thesispresents a detailed study of multi-pivot quicksort algorithms. It explains theunderlying design choices for dual-pivot quicksort algorithms with respect tothe comparisons they make when sorting the input. Moreover, it describes twoeasy to implement optimal dual-pivot algorithms To analyze quicksort algorithmsusing more than two pivots, only slight modifications to the dual-pivot caseare necessary. This thesis also considers the theoretical analysis of thememory and cache behavior of multi-pivot quicksort algorithms. At the end, itreports on a large-scale study on the empirical running time of multi-pivotquicksort algorithms. The second part of this thesis considers the use of hash functions inalgorithms and data structures. Hash functions are applied in many differentsituations, e.g., when building a hash table or when distributing jobs amongmachines in load balancing. Traditionally, the analysis of a particularhashing-based algorithm or data structure assumes that a hash function mapskeys independently and uniformly at random to a range. Such functions areunrealistic, since their space complexity is huge. Consequently, the task is toconstruct explicit hash functions providing provable theoretical guarantees.The thesis describes such a construction. It will provide sufficient randomnessfor running many different applications, such as cuckoo hashing with a stash,the construction of a perfect hash function, the simulation of a uniform hashfunction, load balancing, and generalized cuckoo hashing in a sparse settingwith two alternative insertion algorithms. The main contribution of this partof the thesis is a unified framework based on the first moment method. Thisframework makes it possible to analyze a hashing-based algorithm or datastructure only using random graph theory, without exploiting details of thehash function. The hash functions are easy to implement and turn out to bepractical while providing strong randomness guarantees