Influence of branch mispredictions on sorting algorithms. - Ilmenau. - 90 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2018
Die klassische Analyse von Algorithmen beschäftigt sich normalerweise mit der Anzahl der klassischen Elementaroperationen (Additionen, Multiplikationen, Vergleiche, Swaps usw.). Manchmal reichen solche Analyseansätze nicht aus, um die Effizienz eines Algorithmus zu quantifizieren. Moderne Prozessorarchitekturen haben viele vershiedene Techniken, um ihre Ausführung zu verbessern, wie z.B. Befehelen-Pipelining, die viele Türen öffnen (wie Pipeline-Hazards), die erhebliche Auswirkungen haben und betrachtet werden sollen. Wir präsentieren eine detaillierte Studie zu Optimierungsmethoden für Quicksort-Varianten, die diese Aspekte, insbesondere die Branch-Misprediction, berücksichtigen. Wir beobachten signifikante Verbesserungen gegenüber naiven Ansätzen.
The minimum number of cards in practical card-based protocols. - In: Advances in Cryptology – ASIACRYPT 2017, (2017), S. 126-155
https://doi.org/10.1007/978-3-319-70700-6_5
Cuckoo hashing with overlapping buckets. - In: Dagstuhl Reports, ISSN 2192-5283, Bd. 7 (2017), 5, S. 16
https://doi.org/10.22032/dbt.42358
Theory and applications of hashing : report from Dagstuhl Seminar 17181. - In: , ISSN 2192-5283, Bd. 7 (2017), 5, S. 1-21
http://dx.doi.org/10.4230/DagRep.7.5.1
Konsistentes Hashing mit beschränkter Knotenlast. - Ilmenau. - 37 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2017
Bei Portalen, welche das Streamen und Herunterladen von Videos anbieten, findet sich die folgende Problemstellung: Auf einer Menge von Servern soll eine Menge von Videos derart abgespeichert werden, dass die Videos und somit die Server, auf welchen sie abgespeichert sind, später leicht und schnell wiederzufinden sind (zum Beispiel um sie zu streamen oder herunterzuladen). Weiterhin sollen die Videos möglich gleichverteilt auf den Servern gespeichert sein. Eine Besonderheit hierbei ist, dass die Menge der Server dynamisch ist, also im laufenden Betrieb neue Server zum Speichern von Videos zugeschaltet aber auch entfernt werden können. Die Videos sind ebenfalls dynamisch. Um die Videos den Servern auf eine solche Art und Weise zuzuordnen, kann ein Verfahren namens konsistentes Hashing benutzt werden, welches eine Abwandlung vom Standard-Hashing ist. In dieser Arbeit werden Abwandlungen von konsistentem Hashing untersucht, in denen die Kapazitäten der Behälter konstant und beschränkt sind. Dabei werden zwei herkömmliche Hashverfahren auf konsistentes Hashing angepasst und miteinander verglichen.
Untere Schranken für Berechnungsprobleme auf der Basis der 3SUM-Vermutung. - 105 Seiten
Technische Universität Ilmenau, Masterarbeit 2016
Das Problem 3SUM fragt bei Eingabe einer endlichen Menge A natürlicher Zahlen, ob es a, b, c in A mit a + b = c gibt. Es wird vermutet, dass jeder Algorithmus zur Lösung dieses Problems Zeit mindestens n^(2-o(1)) benötigt. Wir stellen mehrere Varianten dieses Problems vor und zeigen, dass sie bzgl. der 3SUM-Vermutung gleich schwer sind. Das Problem SetDisjointness fragt für mehrere Mengenpaare (S, S'), ob der Schnitt von S und S' leer ist oder nicht. Das Problem SetIntersection fragt nach den konkreten Elementen der Mengenschnitte. Nach einer Untersuchung der Reduktionen von 3SUM auf SetDisjointness und SetIntersection nach Kopelowitz, Pettie und Porat beweisen wir dieselben bedingten unteren Schranken von dem Problem 3XOR aus. Dieses fragt bei Eingabe einer endlichen Menge A von Bitstrings der Länge L, ob es u, v, w in A mit u XOR v = w gibt, wobei XOR der bitweise XOR-Operator ist. Die Reduktion gelingt ebenfalls für eine Verallgemeinerung von 3XOR. Zudem bestimmen wir für die von P&bovko;atra&hbore;scu betrachteten dynamischen Probleme DynamicReachability, DynamicShortestPaths und SubgraphConnectivity bedingte untere Schranken durch Reduktionen von SetDisjointness auf diese Probleme. Für DynamicReachability und DynamicShortestPaths erzwingt eine lineare Vorverarbeitungszeit eine Anfragezeit von >=N^(1/2-o(1)) pro Anfrage. Eine konstante Anfragezeit erzwingt eine Vorverarbeitungszeit von >=N^(2-o(1)). Für SubgraphConnectivity gelten entsprechende Schranken für die Vorverarbeitungszeit und die Summe der Anfrage- und Aktualisierungszeit.
How good is Multi-Pivot Quicksort?. - In: ACM transactions on algorithms, ISSN 1549-6333, Bd. 13 (2016), 1, Article No. 8, insges. 47 S.
https://doi.org/10.1145/2963102
On statistical data compression. - Ilmenau : Universitätsbibliothek, 2016. - 1 Online-Ressource (iii, 173 Seiten)
Technische Universität Ilmenau, Dissertation 2016
Im Zuge der stetigen Weiterentwicklung moderner Technik wächst die Menge an zu verarbeitenden Daten. Es gilt diese Daten zu verwalten, zu übertragen und zu speichern. Dafür ist Datenkompression unerlässlich. Gemessen an empirischen Kompressionsraten zählen Statistische Datenkompressionsalgorithmen zu den Besten. Diese Algorithmen verarbeiten einen Eingabetext buchstabenweise. Dabei verfährt man für jeden Buchstaben in zwei Phasen - Modellierung und Kodierung. Während der Modellierung schätzt ein Modell, basierend auf dem bereits bekannten Text, eine Wahrscheinlichkeitsverteilung für den nächsten Buchstaben. Ein Kodierer überführt die Verteilung und den Buchstaben in ein Codewort. Umgekehrt ermittelt der Dekodierer aus der Verteilung und dem Codewort den kodierten Buchstaben. Die Wahl des Modells bestimmt den statistischen Kompressionsalgorithmus, das Modell ist also von zentraler Bedeutung. Ein Modell mischt typischerweise viele einfache Wahrscheinlichkeitsschätzer. In der statistischen Datenkompression driften Theorie und Praxis auseinander. Theoretiker legen Wert auf Modelle, die mathematische Analysen zulassen, vernachlässigen aber Laufzeit, Speicherbedarf und empirische Verbesserungen; Praktiker verfolgen den gegenteiligen Ansatz. Die PAQ-Algorithmen haben die Überlegenheit des praktischen Ansatzes verdeutlicht. Diese Arbeit soll Theorie und Praxis annähren. Dazu wird das Handwerkszeug des Theoretikers, die Codelängenanlyse, auf Algorithmen des Praktikers angewendet. Es werden Wahrscheinlichkeitsschätzer, basierend auf gealterten relativen Häufigkeiten und basierend auf exponentiell geglätteten Wahrscheinlichkeiten, analysiert. Weitere Analysen decken Methoden ab, die Verteilungen durch gewichtetes arithmetisches und geometrisches Mitteln mischen und Gewichte mittels Gradientenverfahren bestimmen. Die Analysen zeigen, dass sich die betrachteten Verfahren ähnlich gut wie idealisierte Vergleichsverfahren verhalten. Methoden aus PAQ werden mit dieser Arbeit erweitert und mit einer theoretischen Basis versehen. Experimente stützen die Analyseergebnisse. Ein weiterer Beitrag dieser Arbeit ist Context Tree Mixing (CTM), eine Verallgemeinerung von Context Tree Weighting (CTW). Durch die Kombination von CTM mit Methoden aus PAQ entsteht ein theoretisch fundierter Kompressionsalgorithmus, der in Experimenten besser als CTW komprimiert.
http://www.db-thueringen.de/servlets/DocumentServlet?id=27239
Gütegarantien für Einfaches Tabellenhashing. - 34 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2016
Die Wahl einer geeigneten Familie von Hashfunktionen ist ein Kompromiss zwischen Ausführungsgeschwindigkeit und guten mathematischen Garantien. Hier stellen wir Einfaches Tabellenhashing vor, das von Mihai P&bovko;atra¸scu und Mikkel Thorup 2012 umfassend analysiert wurde.
Optimal partitioning for dual-pivot quicksort. - In: ACM transactions on algorithms, ISSN 1549-6333, Bd. 12 (2016), 2, Article No. 18, insges. 36 S.
A preliminary version of this work appeared in the Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP), Part 1, 33-44, 2013
https://doi.org/10.1145/2743020