Foundations for actively secure card-based cryptography. - In: 10th International Conference on Fun with Algorithms, (2020), S. 17.1-17:23
https://doi.org/10.4230/LIPIcs.FUN.2021.17
Random hypergraphs for hashing-based data structures. - Ilmenau : Universitätsbibliothek, 2020. - 1 Online-Ressource (ix, 165 Seiten)
Technische Universität Ilmenau, Dissertation 2020
Diese Arbeit behandelt Wörterbücher und verwandte Datenstrukturen, die darauf aufbauen, mehrere zufällige Möglichkeiten zur Speicherung jedes Schlüssels vorzusehen. Man stelle sich vor, Information über eine Menge S von m = |S| Schlüsseln soll in n Speicherplätzen abgelegt werden, die durch [n] = {1, ,n} indiziert sind. Jeder Schlüssel x [ELEMENT OF] S bekommt eine kleine Menge e(x) [SUBSET OF OR EQUAL TO] [n] von Speicherplätzen durch eine zufällige Hashfunktion unabhängig von anderen Schlüsseln zugewiesen. Die Information über x darf nun ausschließlich in den Plätzen aus e(x) untergebracht werden. Es kann hierbei passieren, dass zu viele Schlüssel um dieselben Speicherplätze konkurrieren, insbesondere bei hoher Auslastung c = m/n. Eine erfolgreiche Speicherung der Gesamtinformation ist dann eventuell unmöglich. Für die meisten Verteilungen von e(x) lässt sich Erfolg oder Misserfolg allerdings sehr zuverlässig vorhersagen, da für Auslastung c unterhalb eines gewissen Auslastungsschwellwertes c* die Erfolgswahrscheinlichkeit nahezu 1 ist und für c jenseits dieses Auslastungsschwellwertes nahezu 0 ist. Hauptsächlich werden wir zwei Arten von Datenstrukturen betrachten: - Eine Kuckucks-Hashtabelle ist eine Wörterbuchdatenstruktur, bei der jeder Schlüssel x [ELEMENT OF] S zusammen mit einem assoziierten Wert f(x) in einem der Speicherplätze mit Index aus e(x) gespeichert wird. Die Verteilung von e(x) wird hierbei vom Hashing-Schema festgelegt. Wir analysieren drei bekannte Hashing-Schemata und bestimmen erstmals deren exakte Auslastungsschwellwerte im obigen Sinne. Die Schemata sind unausgerichtete Blöcke, Doppel-Hashing sowie ein Schema für dynamisch wachsenden Schlüsselmengen. - Auch eine Retrieval-Datenstruktur speichert einen Wert f(x) für alle x [ELEMENT OF] S. Diesmal sollen die Werte in den Speicherplätzen aus e(x) eine lineare Gleichung erfüllen, die den Wert f(x) charakterisiert. Die entstehende Datenstruktur ist extrem platzsparend, aber ungewöhnlich: Sie ist ungeeignet um Fragen der Form "ist y [ELEMENT OF] S?" zu beantworten. Bei Anfrage eines Schlüssels y wird ein Ergebnis z zurückgegeben. Falls y [ELEMENT OF] S ist, so ist z = f(y) garantiert, andernfalls darf z ein beliebiger Wert sein. - Wir betrachten zwei neue Hashing-Schemata, bei denen die Elemente von e(x) in einem oder in zwei zusammenhängenden Blöcken liegen. So werden gute Zugriffszeiten auf Word-RAMs und eine hohe Cache-Effizienz erzielt. Eine wichtige Frage ist, ob Datenstrukturen obiger Art in Linearzeit konstruiert werden können. Die Erfolgswahrscheinlichkeit eines naheliegenden Greedy-Algorithmus weist abermals ein Schwellwertverhalten in Bezug auf die Auslastung c auf. Wir identifizieren ein Hashing-Schema, das diesbezüglich einen besonders hohen Schwellwert mit sich bringt. In der mathematischen Modellierung werden die Speicherpositionen [n] als Knoten und die Mengen e(x) für x [ELEMENT OF] S als Hyperkanten aufgefasst. Drei Eigenschaften der entstehenden Hypergraphen stellen sich dann als zentral heraus: Schälbarkeit, Lösbarkeit und Orientierbarkeit. Weite Teile dieser Arbeit beschäftigen sich daher mit den Wahrscheinlichkeiten für das Vorliegen dieser Eigenschaften abhängig von Hashing Schema und Auslastung, sowie mit entsprechenden Schwellwerten. Eine Rückübersetzung der Ergebnisse liefert dann Datenstrukturen mit geringen Anfragezeiten, hoher Speichereffizienz und geringen Konstruktionszeiten. Die theoretischen Überlegungen werden dabei durch experimentelle Ergebnisse ergänzt und gestützt.
https://www.db-thueringen.de/receive/dbt_mods_00047127
Obere Schranken für die maximale Kettenlänge bei linearen Hashfunktionen. - Ilmenau. - 56 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2020
In der vorliegenden Arbeit werden obere und untere Schranken für die erwartete maximale Kettenlänge bei linearen Hashfunktionen studiert, wenn Hashing mit verketteten Listen als Kollisionsbehandlung verwendet wird. Es werden Funktionen h, die von einem endlichen Universium U in eine endliche Wertemenge M abbilden, betrachtet. Sei S eine n-elementige Teilmenge von U. Es wird die Wirkung von h auf S studiert. Zunächst wird eine allgemeine obere Schranke für Hashfunktion aus universellen Hashklassen gezeigt. Für solche Funktionen liegt die erwartete maximale Kettenlänge in O(n^(1/2)). Es wird dann eine schärfere obere Schranke für zwei Familien von Hashfunktionen gezeigt, welche aus Mathias Bæk Tejs Knudsen: Linear Hashing Is Awesome. SIAM J. Comput. 48(2): 736-741 (2019) stammt. Für derartige Familien von Hashfunktionen liegt die erwartete maximale Kettenlänge in O(n^(1/3)). Abschließend werden zwei untere Schranken für die erwartete maximale Kettenlänge aus Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos: Linear Hash Functions. J. ACM 46(5): 667-683 (1999) vorgestellt. Diese Ergebnisse werden für eine weitere Familie von Hashfunktionen über endlichen Körper gezeigt.
Engineering von Algorithmen zur Berechnung eines minimalen Schnittes in Graphen. - Ilmenau. - 90 Seiten
Technische Universität Ilmenau, Masterarbeit 2020
In dieser Masterarbeit wird mittels Algorithm Engineering eine möglichst schnelle Implementation des Algorithmus von Nagamochi-Ibaraki für das Open Graph Drawing Framework erarbeitet, die ebenfalls auf großen Graphen schnell ist. Zusätzlich soll die Berechnung einer Maximum Adjacency Ordering ( MAO ) und der Algorithmus von Nagamochi-Ibaraki im praktischen Einsatz beschleunigt werden. Hierbei ist eine MAO eine Totalordnung über die Knotenmenge des Graphen. Zuerst wurden verschiedene Implementationen für die MAO Berechnung erstellt. Ein Ergebnis dieser Implementationen ist die BoundedList, in der maximal B Elemente in einer Liste enthalten sein dürfen, um Lösch- und Einfügeoperationen einzusparen. Bei dem Vergleich der MAO Berechnungen auf verschiedenen Problemfamilien ist ein Ergebnis, dass die BoundedList in der Praxis schneller ist als die Priority-Queue Variante, die von anderen experimentellen Auswertungen verwendet wurde. Daraufhin wurde die BoundedList in Nagamochi-Ibaraki zusammen mit den Padberg-Rinaldi Heuristiken eingearbeitet. Hierbei existieren ebenfalls verschiedene Varianten der Implementation. Eine dieser verwendet eine kompakte Kontraktion um Knoten zu kontrahieren. Dagegen erfolgt die Umsetzung einer anderen Variante mittels Union-Find, um zusammengehörige Knotenmengen zu bilden, die die zu kontrahierenden Knoten repräsentieren. Unter den getesteten Graphen befinden sich ebenfalls Graphen, die realen Netzwerken nachempfunden wurden. Hierbei ist ein Ergebnis, dass das Abbrechen der MAO Berechnung und das Kontrahieren von kontrahierbaren Knotenmengen innerhalb einer Runde von Nagamochi-Ibaraki vorteilhaft bei Graphen mit Clusterkoeffizienten unter 10 Prozent ist. Ansonsten ist die vollständige Berechnung der MAO zu empfehlen. Des weiteren ist während der Masterarbeit aufgefallen, dass die Implementation einer schnellen Kontraktion erheblich ist.
Experimente mit grundlegenden Algorithmen und Datenstrukturen und deren Implementierung. - Ilmenau. - 69 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2019
In der Informatik gibt es diverse Möglichkeiten zur Implementierung von Algorithmen und Datenstrukturen. Diese können sich anschließend bezüglich ihrer Laufzeit oder im Speicherverbrauch unterscheiden. Anhand verschiedener mathematischer Analysen lassen sich Schranken für diese Parameter der Algorithmen und Datenstrukturen berechnen. Durch die modernen Rechnerarchitekturen und deren interne Abläufe können sich diese berechneten Laufzeiten allerdings von den berechneten Schranken unterscheiden. Das Ziel dieser Forschung ist es, zu bestimmen, ob die modernen Rechnerarchitekturen solch großen Einfluss auf die Algorithmen und Datenstrukturen aufweisen, oder ob die bisherigen Annahmen noch zutreffen. Um dieses Problem zu untersuchen, werden ausgewählte Algorithmen und Datenstrukturen implementiert und anschließend Messungen durchgeführt. Dabei fallen die Betrachtungen im Wesentlichen auf grundlegende Algorithmen und Datenstrukturen. Genauer gesagt werden zunächst Stacks und Queues in verschiedenen Implementierungsvarianten untersucht. Anschließend wird offenes und geschlossenes Hashing betrachtet. Dabei werden verschiedene Sondierverfahren miteinander verglichen. Da es verschiedenste Verfahren zum Sortieren von Informationen gibt, werden anschließen fünf Sortieralgorithmen untersucht und dabei ihre Laufzeiten verglichen. Den Abschluss bildet die eigene Implementierung der Addition und Multiplikation zum Rechnen mit großen Ganzzahlen. Und letztendlich ein Vergleich zwischen Quickselect und Mergesort zum Finden des kleinsten Elements in einem Array. Die Betrachtung der Messergebnisse zeigt, dass die mathematischen Annahmen und Schranken für die gewählten Algorithmen und Datenstrukturen immer noch zutreffen und somit keine einzelnen Algorithmen durch die Computerarchitektur entgegen dieser Analysen optimiert werden. Auf dieser Grundlage können also die getroffenen Annahmen weiter verfolgt werden.
Efficient Gauss elimination for near-quadratic matrices with one short random block per row, with applications. - In: 27th Annual European Symposium on Algorithms, (2019), S. 39:1-39:18
https://doi.org/10.4230/LIPIcs.ESA.2019.39
Dense peelable random uniform hypergraphs. - In: 27th Annual European Symposium on Algorithms, (2019), S. 38:1-38:16
https://doi.org/10.4230/LIPIcs.ESA.2019.38
Determining minimum hash width for hash chains. - In: CECC 2019, (2019), article no. 18, 5 Seiten
https://doi.org/10.1145/3360664.3360682
Zählende und invertierbare Bloom-Filter : Theorie und Experiment. - Ilmenau. - 51 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2019
Bloom-Filter, Parallelisierbaren Bloom-Filter, Compresed Bloom-Filter, Learned Bloom-Filter, Invertible Bloom-Filter, Invertible Bloom Lookup Table. Cuckoo-Hashing. Alternative zu Bloom-Filtern: Cuckoo-Filter. Anwendungen der Bloom-Filter. Experimente mit Bloom-Filtern.
Sequential and parallel algorithms and data structures : the basic toolbox. - Cham : Springer, 2019. - xv, 509 Seiten ISBN 978-3-030-25208-3
Literaturverzeichnis: Seite 467-485