Literaturliste aus der Hochschulbibliographie

Anzahl der Treffer: 144
Erstellt: Thu, 28 Mar 2024 23:03:06 +0100 in 0.4365 sec


Counting paths in graphs. - Ilmenau. - 35 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2023

Lovász erkannte als einer der ersten den engen Zusammenhang zwischen der Anzahl der Subgraphen #Sub(H, G) und der Anzahl der Homomorphismen #Hom(H, G). Radu Curticapean, Holger Dell und Dániel Marx formalisierten diese Erkenntnisse unter dem Namen der ‚Graph Motif Parameter‘. Des Weit- eren zeigten sie, dass #Sub(H, G) = ∑ ρ (−1)|V (H)|−|V (Hρ )| &hahog; ∏ B∈ρ(|B| − 1)! #Aut(H) &hahog; #Hom(Hρ, G) (1) gilt [?]. In dieser Arbeit analysieren wir das Zählen von Pfaden mittels graphHom2. Wir zeigen, dass es unter gewissen Annahmen keinen Algorithmus der Laufzeit f (k)&hahog;no(&worte;k/ log(&worte;k)) für das Zählen von k-Pfaden in einem Zielgraph auf n-Ecken gibt, sofern wir graphHom2 nutzen, wobei f eine berechenbare Funktion ist die nur von k abhängt. Außerdem beweisen wir, dass Pfade, unter allen zusammenhängenden Graphen, die Anzahl der zu betrachtenden Quotientengraphen Qρ maximieren. Zudem befassen wir uns mit dem Entscheidungsproblem, Pfade in Graphen aufzufinden, und zeigen eine hinreichende Existenzbedingung für Pk ⊆ G.



Berkholz, Christoph; Nordström, Jakob
Near-optimal lower bounds on quantifier depth and Weisfeiler-Leman refinement steps. - In: Journal of the ACM, ISSN 1557-735X, Bd. 70 (2023), 5, 32, S. 32:1-32:32

We prove near-optimal tradeoffs for quantifier depth (also called quantifier rank) versus number of variables in first-order logic by exhibiting pairs of n-element structures that can be distinguished by a k-variable first-order sentence but where every such sentence requires quantifier depth at least nΩ (k/log k). Our tradeoffs also apply to first-order counting logic and, by the known connection to the k-dimensional Weisfeiler-Leman algorithm, imply near-optimal lower bounds on the number of refinement iterations. A key component in our proof is the hardness condensation technique introduced by Razborov in the context of proof complexity. We apply this method to reduce the domain size of relational structures while maintaining the minimal quantifier depth needed to distinguish them in finite variable logics.



https://doi.org/10.1145/3195257
Berkholz, Christoph; Vinall-Smeeth, Harry
A dichotomy for succinct representations of homomorphisms. - In: 50th International Colloquium on Automata, Languages, and Programming, (2023), S. 113:1-113:19

The task of computing homomorphisms between two finite relational structures A and B is a well-studied question with numerous applications. Since the set Hom(A, B) of all homomorphisms may be very large having a method of representing it in a succinct way, especially one which enables us to perform efficient enumeration and counting, could be extremely useful. One simple yet powerful way of doing so is to decompose Hom(A, B) using union and Cartesian product. Such data structures, called d-representations, have been introduced by Olteanu and Závodný [Olteanu and Závodný, 2015] in the context of database theory. Their results also imply that if the treewidth of the left-hand side structure A is bounded, then a d-representation of polynomial size can be found in polynomial time. We show that for structures of bounded arity this is optimal: if the treewidth is unbounded then there are instances where the size of any d-representation is superpolynomial. Along the way we develop tools for proving lower bounds on the size of d-representations, in particular we define a notion of reduction suitable for this context and prove an almost tight lower bound on the size of d-representations of all k-cliques in a graph.



https://doi.org/10.4230/LIPIcs.ICALP.2023.113
Carmeli, Nofar; Zeevi, Shai; Berkholz, Christoph; Conte, Alessio; Kimelfeld, Benny; Schweikardt, Nicole
Answering (unions of) conjunctive queries using random access and random-order enumeration. - In: ACM transactions on database systems, ISSN 0362-5915, Bd. 47 (2022), 3, S. 9:1-9:49

As data analytics becomes more crucial to digital systems, so grows the importance of characterizing the database queries that admit a more efficient evaluation. We consider the tractability yardstick of answer enumeration with a polylogarithmic delay after a linear-time preprocessing phase. Such an evaluation is obtained by constructing, in the preprocessing phase, a data structure that supports polylogarithmic-delay enumeration. In this article, we seek a structure that supports the more demanding task of a “random permutation”: polylogarithmic-delay enumeration in truly random order. Enumeration of this kind is required if downstream applications assume that the intermediate results are representative of the whole result set in a statistically meaningful manner. An even more demanding task is that of “random access”: polylogarithmic-time retrieval of an answer whose position is given. We establish that the free-connex acyclic CQs are tractable in all three senses: enumeration, random-order enumeration, and random access; and in the absence of self-joins, it follows from past results that every other CQ is intractable by each of the three (under some fine-grained complexity assumptions). However, the three yardsticks are separated in the case of a union of CQs (UCQ): while a union of free-connex acyclic CQs has a tractable enumeration, it may (provably) admit no random access. We identify a fragment of such UCQs where we can guarantee random access with polylogarithmic access time (and linear-time preprocessing) and a more general fragment where we can guarantee tractable random permutation. For general unions of free-connex acyclic CQs, we devise two algorithms with relaxed guarantees: one has logarithmic delay in expectation, and the other provides a permutation that is almost uniformly distributed. Finally, we present an implementation and an empirical study that show a considerable practical superiority of our random-order enumeration approach over state-of-the-art alternatives.



https://doi.org/10.1145/3531055
Schneider, Ludwig;
Über praktisch schnelle Verfahren zur Konstruktion von Suffixarrays. - Ilmenau. - 145 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2022

Suffixarrays sind eine der zentralen Datenstrukturen für String-Algorithmen und finden weitreichende praktische Anwendungen. Die effiziente Konstruktion dieser ist seit der ersten Veröffentlichung in 1990 ein sehr reges Forschungsgebiet geblieben. Im Jahr 2006 wurde der Algorithmus DivSufSort veröffentlicht und obwohl seitdem eine Vielzahl weiterer Suffixarray-Konstruktions-Algorithmen entwickelt wurden, konnte dieser in seiner praktischen Performanz 15 Jahre lang nicht unterboten werden. Doch im Jahr 2021 wurde ein neuer Algorithmus GSACA-DS vorgestellt, welcher unter Verwendung von speziellen Eigenschaften von Lyndon-Wörtern DivSufSort endlich in der Praxis schlagen kann. Obwohl DivSufSort solch hohe praktische Relevanz hat, entzog sich dieser bisher einer rein formellen Darstellung. GSACA-DS besitzt einen formal komplexen Ansatz, weshalb die originale Arbeit keine vollständige Grundlage für dessen Funktionsweise darstellt. Im Rahmen dieser Arbeit sollen diese Lücken in der Literatur gefüllt werden, indem beide Verfahren inklusive ihrer theoretischen Grundlagen vorgestellt, analysiert und zum ersten Mal deren Korrektheit bewiesen werden.



Walzer, Stefan;
Peeling close to the orientability threshold - spatial coupling in hashing-based data structures. - In: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, (2021), S. 2194-2211

https://dl.acm.org/doi/10.5555/3458064.3458195
Gupta, Rachit;
Fairness in personnel scheduling. - Ilmenau. - 88 Seiten
Technische Universität Ilmenau, Masterarbeit 2021

Die Personaleinsatzplanung ist ein komplexes Optimierungsproblem, bei dem es um die Zuteilung von Mitarbeitern zum Arbeitsplan in einer Vielzahl von Branchen geht. In dieser Arbeit betrachten wir eine spezielle Variante, die "faire" Einsatzpläne erstellen soll. Der Arbeitgeber hat, ähnlich wie bei der traditionellen Personaleinsatzplanung, die Kontrolle über die Zuweisung von Einsatzorten und Arbeitszeiten an die Arbeitnehmer. Andererseits steht es den Arbeitnehmern frei, Präferenzen für die von ihnen gewünschte Arbeit zu äußern. Durch diese Präferenzen werden die Mitarbeiter in das Planungssystem einbezogen, was sich positiv auf die Arbeitsmoral und die Produktivität auswirken soll. Ziel ist es, ein faires Planungssystem zu schaffen, das den Anforderungen des Unternehmens gerecht wird und die Arbeitswünsche der Mitarbeiter berücksichtigt. In dem in dieser Arbeit vorgeschlagenen Modell geben die Unternehmen ihren Bedarf für jeden Tag an, und die Arbeitnehmer geben ihre Präferenzen an. Unser Algorithmus versucht, einen Plan zu erstellen, der sowohl für Arbeitgeber als auch für Arbeitnehmer eine Win-Win-Situation darstellt. Um dies zu erreichen, versuchen wir, einen Zeitplan zu erstellen, der den Anforderungen des Unternehmens und den Präferenzen der Arbeitnehmer so weit wie möglich gerecht wird. Wir haben den Algorithmus mit drei verschiedenen Ansätzen implementiert. Mit allen drei Ansätzen wurden verschiedene Computerexperimente durchgeführt, und ihre Ergebnisse werden diskutiert. Unser Ansatz erstellt erfolgreich einen kurz-, mittel- und langfristigen Zeitplan, der zu einem guten Prozentsatz die Präferenzen der Mitarbeiter erfüllt.



Hasenbein, René;
Analyse und experimentelle Evaluation moderner Heap-Strukturen. - Ilmenau. - 98 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2021

Diese Arbeit befasst sich mit einer seit 2015 existierenden Idee für die Implementierung von Prioritätswarteschlangen. Es handelt sich dabei um die von Thomas Dueholm Hansen, Haim Kaplan, Robert E. Tarjan und Uri Zwick vorgeschlagenen "Hollow Heaps". Von den klassischen Fibonacci-Heaps unterscheiden sie sich dadurch, dass sie auf die Cascading-Cut-Prozedur verzichten und stattdessen ein Konzept "leerer Knoten" einführen und teils sogar auf die für Heaps übliche Baumstruktur verzichten. Diese Arbeit stellt Fibonacci-Heaps und Hollow Heaps einheitlich und ausführlich dar und führt experimentelle Vergleiche. In dieser Arbeit wird gezeigt, dass die Wahl zwischen Fibonacci-Heaps und Hollow Heaps bis auf in wenigen Ausnahmen zugunsten der Hollow Heaps ausfallen sollte. Weiterhin sind in unseren Experimenten Binärheaps - als wahrscheinlich grundlegendste Heapstruktur - sogar schneller als ihre Konkurrenten.



Koch, Alexander; Walzer, Stefan
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
Walzer, Stefan;
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
Fiedler, Christian;
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.



Alder, Sascha;
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.



Hohlbein, Christian;
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.



Dietzfelbinger, Martin; Walzer, Stefan
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
Dietzfelbinger, Martin; Walzer, Stefan
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
Dietzfelbinger, Martin; Keller, Jörg
Determining minimum hash width for hash chains. - In: CECC 2019, (2019), article no. 18, 5 Seiten

https://doi.org/10.1145/3360664.3360682
Simidyan, Petros;
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.



Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman
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

Dietzfelbinger, Martin; Walzer, Stefan
Constant-time retrieval with O(log m) extra bits. - In: 36th International Symposium on Theoretical Aspects of Computer Science, (2019), S. 24:1-24:16

https://doi.org/10.4230/LIPIcs.STACS.2019.24
Aumüller, Martin; Dietzfelbinger, Martin; Heuberger, Clemens; Krenn, Daniel; Prodinger, Helmut
Dual-Pivot quicksort: optimality, analysis and zeros of associated lattice paths. - In: Combinatorics, probability & computing, ISSN 1469-2163, Bd. 28 (2019), 4, S. 485-518

https://doi.org/10.1017/S096354831800041X
Maier, Tobias; Sanders, Peter; Walzer, Stefan
Dynamic space efficient hashing. - In: Algorithmica, ISSN 1432-0541, Bd. 81 (2019), 8, S. 3162-3185

https://doi.org/10.1007/s00453-019-00572-x
Schwetschenau, René;
Sortieren und Suchbäume für Strings im Word-RAM-Modell. - Ilmenau. - 40 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2019

Möchte man eine Menge S von Strings effzient abspeichern und Operationen auf S wie das Einfügen, Suchen oder Entfernen von Strings definieren, werden üblicherweise Suchbäume verwendet. J. Bentley und R. Sedgewick haben sich in den 1990er Jahren mit diesem Problem beschäftigt und den ternären Suchbaum vorgestellt. M. Dietzfelbinger, P. Schlag und S. Walzer haben 2018 für ein anderes Problem eine neue spezielle Suchbaumstruktur für Bitstrings fester Länge entwickelt. In dieser Arbeit werden die beiden Suchbaumstrukturen verglichen und die Suchbaumstruktur für Bitstrings fester Länge verallgemeinern, so dass sie mit beliebigen Strings umgehen kann.



Mitzenmacher, Michael; Panagiotou, Konstantinos; Walzer, Stefan
Load thresholds for cuckoo hashing with double hashing. - In: 16th Scandinavian Symposium and Workshops on Algorithm Theory, (2018), Seite 29:1-29:9

http://dx.doi.org/10.4230/LIPIcs.SWAT.2018.29
Walzer, Stefan;
Load thresholds for cuckoo hashing with overlapping blocks. - In: 45th International Colloquium on Automata, Languages, and Programming, (2018), Seite 102:1-102:10

http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.102
Dietzfelbinger, Martin; Schlag, Philipp; Walzer, Stefan
A subquadratic algorithm for 3XOR. - In: 43rd International Symposium on Mathematical Foundations of Computer Science, (2018), Seite 59:1-59:15

https://doi.org/10.4230/LIPIcs.MFCS.2018.59
Dietzfelbinger, Martin;
Universal hashing via integer arithmetic without primes, revisited. - In: Adventures Between Lower Bounds and Higher Altitudes, (2018), S. 257-279

https://doi.org/10.1007/978-3-319-98355-4_15
Le Van, Khanh;
Vergleich zweier Algorithmen für perfektes Hashing. - Ilmenau. - 61 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2018

In dieser Arbeit werden wir uns mit HDC- und FHCD-Algorithmen beschäftigen, welche für eine gegebene Schlüsselmenge eine Datenstruktur konstruiert, die für diese Schlüsselmenge eine perfekte Hashfunktion darstellt. Dabei interessieren wir uns für drei Parameter, die entscheidend für die Performanz sind: die Konstruktionszeit, die Darstellungsgröße und die Auswertungszeit. Beide Algorithmen weisen starke Ähnlichkeiten auf und sollen laut Autoren höchstens lineare Zeit für die Konstruktion benötigen. Jedoch konnten wir dies nur bei HDC nachweisen. Die lineare Platzkomplexität konnte bei beiden festgestellt werden.



Xia, Qi;
Schnelle Konstruktion von Wörterbüchern und Retrieval-Datenstrukturen. - Ilmenau. - 63 Seiten
Technische Universität Ilmenau, Masterarbeit 2018

Diese Arbeit besteht grundsätzlich aus zwei Teilen. Der erste Teil ist beschäftigt mit der Datenstruktur Wörterbuch und ihren Konstruktionsverfahren. Um ein Wörterbuch mit sowohl einer konstanten Zugriffszeit als auch einer hohen Speicherauslastung zu konstruieren, wird Cuckoo-Hashing als eine effiziente Technik zur Erstellung von Hashtabellen verwendet. In der Arbeit werden zwei Verallgemeinerungsschemata des Cuckoo-Hashings betrachtet. Dabei werden verschiedene Zuordnungsalgorithmen systematisch beschrieben und analysiert. Im zweiten Teil der Arbeit werden Retrieval-Datenstrukturen behandelt. Zur effizienteren Konstruktion von Retrieval-Datenstrukturen in Bezug auf den verwendeten Speicherplatz werden Lazy-Gauss-Elimination (LGE) und Broadword-Programmierung eingesetzt. Damit kann ein großes lineares Gleichungssystem schneller gelöst werden. Zum Ende des zweiten Teils werden zusätzlich konkrete Implementierungen sowie experimentelle Ergebnisse des LGE und der Broadword-Programmierung präsentiert.



Kassem, Mohamad Karam;
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.



Kastner, Julia; Koch, Alexander; Walzer, Stefan; Miyahara, Daiki; Hayashi, Yu-ichi; Mizuki, Takaaki; Sone, Hideaki
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
Walzer, Stefan;
Cuckoo hashing with overlapping buckets. - In: Dagstuhl Reports, ISSN 2192-5283, Bd. 7 (2017), 5, S. 16

https://doi.org/10.22032/dbt.42358
Dietzfelbinger, Martin; Mitzenmacher, Michael; Pagh, Rasmus; Woodruff, David P.; Aumüller, Martin
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
Gerstenberg, Philipp;
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.



Schlag, Philipp;
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.



Aumüller, Martin; Dietzfelbinger, Martin; Klaue, Pascal
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
Mattern, Christopher;
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
Frank, Hannes;
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.



Aumüller, Martin; Dietzfelbinger, Martin
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
Jaberi, Raed;
Algorithms for computing the 2-vertex-connected components and the 2-blocks of directed graphs, 2015. - Online-Ressource (PDF-Datei: VII, 121 S., 1023 KB) Ilmenau : Techn. Univ., Diss., 2015

In dieser Dissertation beschäftigen wir uns mit mehreren Problemen in gerichteten Graphen. Zuerst betrachten wir das Problem der Berechnung der $2$-fach knotenzusammenhängenden Komponenten in gerichteten Graphen. Wir präsentieren einen neuen Algorithmus zur Lösung dieses Problems in Zeit $O(nm)$ und wir betrachten drei Anwendungen dieses Algorithmus. Sei $G=(V,E)$ ein gerichteter Graph. Ein $2$-gerichteter Block in $G$ ist eine maximale Knotenmenge $C^{2d}\subseteq V$ mit $|C^{2d}|\geq 2$, so dass für jedes Paar von verschiedenen Knoten $x,y\in C^{2d}$ zwei knoten disjunkte Wege von $x$ nach $y$ und zwei knoten disjunke Wege von $y$ nach $x$ in $G$ existieren.Wir präsentieren zwei Algorithmen zur Berechnung der $2$-gerichteten Blöcke von $G$ in Zeit $O(\min\lbrace m,(t_{sap}+t_{sb})n\rbrace n)$, wobei $t_{sap}$ die Anzahl der starken Artikulations\-punkte von $G$ und $t_{sb}$ die Anzahl der starken Brücken von $G$ ist. Wir untersuchen zwei weitere relevante Begriffe: die $2$-starken Blöcke und die $2$-Kanten-Blöcke von $G$. Wir geben zwei Algorithmen zur Berechnung der $2$-starken Blöcke von $G$in Zeit $O( \min \lbrace m,t_{sap} n\rbrace n)$ an und wir zeigen, dass die $2$-Kanten-Blöcke von $G$ in Zeit $O(\min \lbrace m, t_{sb} n \rbrace n)$ bestimmt werden können. Wir untersuchen auch einige Optimierungsprobleme, die mit starken Artikulationspunkten und $2$-Blöcken zusammenhängen. Gegeben sei ein stark zusammenhängender Graph $G=(V,E)$. Wir wollen einen minimalen stark zusammenhängenden spannenden Teilgraphen $G^{*}=(V,E^{*})$ von $G$ finden, so dass die starken Artikulationspunkte von $G$ mit den starken Artikulationspunkten von $G^{*}$ übereinstimmen. Wir zeigen, dass es einen $17/3$-Approximationsalgorithmus für dieses NP-schwere Problem gibt, der lineare Laufzeit hat. Wir betrachten auch das Problem der Berechnung eines minimalen stark zusammenhängenden spannenden Teilgraphen mit denselben $2$-Blöcken in einem stark zusammenhängenden Graphen. Wir präsentieren Approximationsalgorithmen für drei Versionen dieses Problems, die sich in der Art der $2$-Blöcke unterscheiden. Im Gegensatz zu $2$-stark-zusammenhängenden Komponenten kann Entfernung der nicht zu $2$-gerichteten Blöcken gehörenden starken Artikulations\-punkte aus $G$ diese Blöcke ändern. Wir untersuchen das Problem der Berechnung einer minimalen Teilmenge $V^{*}$ der starken Artikulationspunkte, die nicht in diesen Blöcke liegen, so dass das Entfernen von $V^{*}$ denselben Effekt hat. Außerdem untersuchen wir andere Versionen dieses Problems, die sich in der Art der $2$-Blöcke unterscheiden. Ein gerichteter Graph $G=(V,E)$ heißt einfach zusammenhängend, wenn für jedes Paar von Knoten $v,w\in V$ höchstens ein einfacher Weg von $v$ nach $w$ in $G$ existiert. Buchsbaum und Carlisle (1993) gaben einen Algorithmus an, der in Zeit $O(n^{2})$ überprüft, ob $G$ einfach zusammenhängend ist. In dieser Dissertation beschreiben wir eine verbesserte Version dieses Algorithmus, die Laufzeit $O(s\cdot t+m)$ hat, wobei $s,t$ die Anzahl der Quellen beziehungsweise Senken im reduzierten Graphen sind, den man auf folgende Weise erhält: Kontrahieren jeder stark zusammenhängenden Komponente zu einem Knoten und dann Eliminierung von Knoten mit Eingangsgrad oder Ausgangsgrad $1$ durch eine Kontrahierenoperation. Außerdem zeigen wir, dass das Problem der Berechnung einer Kantenteilmenge $C\subseteq E$ (beziehungsweise Knotenteilmenge $F\subseteq V$), deren Löschen einen einfach-zusammenhängenden Graphen übrig lässt, NP-schwer ist.



http://www.db-thueringen.de/servlets/DocumentServlet?id=26841
Jaberi, Raed;
Computing the 2-blocks of directed graphs. - In: RAIRO. Theoretical informatics and applications. - Les Ulis : EDP Sciences, [1986]- , ISSN: 1290-385X , ZDB-ID: 1492140-6, ISSN 1290-385X, Bd. 49 (2015), 2, S. 93-119

Let $G$ be a directed graph. A \textit{$2$-directed block} in $G$ is a maximal vertex set $C^{2d}\subseteq V$ with $|C^{2d}|\geq 2$ such that for each pair of distinct vertices $x,y \in C^{2d}$, there exist two vertex-disjoint paths from $x$ to $y$ and two vertex-disjoint paths from $y$ to $x$ in $G$. In this paper we present two algorithms for computing the $2$-directed blocks of $G$ in $O(\min\lbrace m,(t_{sap}+t_{sb})n\rbrace n)$ time, where $t_{sap}$ is the number of the strong articulation points of $G$ and $t_{sb}$ is the number of the strong bridges of $G$. Furthermore, we study two related concepts: the $2$-strong blocks and the $2$-edge blocks of $G$. We give two algorithms for computing the $2$-strong blocks of $G$ in $O(\min \lbrace m,t_{sap} n\rbrace n)$ time and we show that the $2$-edge blocks of $G$ can be computed in $O(\min \lbrace m, t_{sb} n \rbrace n)$ time. In this paper we also study some optimization problems related to the strong articulation points and the $2$-blocks of a directed graph. Given a strongly connected graph $G=(V,E)$, we want to find a minimum strongly connected spanning subgraph $G^{*}=(V,E^{*})$ of $G$ such that the strong articulation points of $G$ coincide with the strong articulation points of $G^{*}$. We show that there is a linear time $17/3$ approximation algorithm for this NP-hard problem. We also consider the problem of finding a minimum strongly connected spanning subgraph with the same $2$-blocks in a strongly connected graph $G$. We present approximation algorithms for three versions of this problem, depending on the type of $2$-blocks.



https://doi.org/10.1051/ita/2015001
Mattern, Christopher;
On probability estimation by exponential smoothing . - In: 2015 Data Compression Conference (DCC 2015), ISBN 978-1-4799-8430-5, (2015), S. 460

http://dx.doi.org/10.1109/DCC.2015.36
Mattern, Christopher;
On probability estimation via relative frequencies and discount. - In: 2015 Data Compression Conference (DCC 2015), ISBN 978-1-4799-8430-5, (2015), S. 183-192

http://dx.doi.org/10.1109/DCC.2015.27
Aumüller, Martin;
On the analysis of two fundamental randomized algorithms : multi-pivot quiocksort and efficient hash functions. - Ilmenau : Univ.-Bibliothek, 2015. - Online-Ressource (PDF-Datei: VIII, 235 S., 1,63 MB) : Ilmenau, Techn. Univ., Diss., 2015
Parallel als Druckausg. erschienen

Im ersten Teil der vorliegenden Arbeit werden Multi-Pivot-Quicksort-Algorithmen betrachtet. Die Idee mehr als ein Pivotelement im Quicksort-Algorithmus zu nutzen, erschien über viele Jahre als unpraktikabel. Dies änderte sich, als im Jahr 2009 ein Dual-Pivot-Algorithmus von V. Yaroslavskiy zum Standard-Sortierverfahren in Java 7 wurde. Die vorliegende Arbeit stellt eine Studie von Multi-Pivot-Quicksort-Algorithmen dar, also Quicksort-Varianten, die mit mehr als einem Pivotelement arbeitet. Sie beschreibt die Konstruktionsprinzipien von 2-Pivot-Algorithmen in Bezug auf die bei der Sortierung notwendigen Schlüsselvergleiche. Ein Ergebnis dieser Untersuchung sind zwei optimale und leicht zu implementierende 2-Pivot-Algorithmen. Die Verallgemeinerung auf >= 3 Pivotelemente benötigt nur kleine Anpassungen. Diese Arbeit betrachtet außerdem die theoretische Analyse von Kostenmaßen, die es ermöglichen, Multi-Pivot-Quicksort-Algorithmen hinsichtlich ihres Speicher- und Cacheverhaltens zu vergleichen. Sie schließt mit einer Laufzeitstudie der besprochenen Algorithmen. Der zweite Teil der Arbeit beschäftigt sich mit dem Einsatz von Hashfunktionen in Algorithmen und Datenstrukturen. Hashfunktionen bilden eine Kernkomponente, z.B. beim Aufbau einer Hashtabelle oder bei Lastbalancierung. Oft wird dabei eine unrealistische Annahme getätigt : Die Hashwerte seien voll zufällig. Die Speicherplatzkomplexität einer solchen Funktion ist für den praktischen Einsatz für unverhältnismäßig hoch. Das Ziel ist, einfache Konstruktionen zu finden, deren Zufallseigenschaften beweisbar gut sind. Diese Arbeit beschreibt eine solche einfache Konstruktion von Hashfunktionen, die in einer Vielzahl von Anwendungen beweisbar gut ist. Zu diesen Anwendungen zählen Cuckoo Hashing mit einem sogenannten Stash, die Konstruktion einer perfekten Hashfunktion, die Simulation einer uniformen Hashfunktion, verschiedene Algorithmen zur Lastbalancierung und verallgemeinertes Cuckoo Hashing in einer leicht abgeschwächten Variante mit verschiedenen Einfügealgorithmen. Der zentrale Beitrag dieser Dissertation ist ein einheitliches Analysekonzept. Dieses ermöglicht es, eine auf Hashfunktionen basierende Datenstruktur oder einen auf Hashfunktionen basierenden Algorithmus nur mit Mitteln der Theorie von Zufallsgraphen zu analysieren, ohne Details der Hashfunktion offenzulegen.



http://www.db-thueringen.de/servlets/DocumentServlet?id=26263
Dietzfelbinger, Martin; Jaberi, Raed
On testing single connectedness in directed graphs and some related problems. - In: Information processing letters, ISSN 1872-6119, Bd. 115 (2015), 9, S. 684-688

http://dx.doi.org/10.1016/j.ipl.2015.04.008
Dietzfelbinger, Martin; Rink, Michael
Towards optimal degree distributions for left-perfect matchings in random bipartite graphs. - In: Theory of computing systems, ISSN 1433-0490, Bd. 56 (2015), 4, S. 593-611

http://dx.doi.org/10.1007/s00224-014-9577-1
Dietzfelbinger, Martin; Mehlhorn, Kurt; Sanders, Peter
Algorithmen und Datenstrukturen : Die Grundwerkzeuge. - Berlin, Heidelberg : Springer Vieweg, 2014. - Online-Ressource (XII, 380 S. 101 Abb, online resource). - (eXamen.press) ISBN 978-3-642-05472-3

Arithmetik für ganze Zahlen -- Einleitung -- Darstellung von Folgen durch Arrays und verkettete Listen -- Hashtabellen und assoziative Arrays -- Sortieren und Auswählen -- Prioritätswarteschlangen -- Geordnete Folgen -- Die Darstellung von Graphen -- Graphdurchläufe -- Kürzeste Wege -- Minimale Spannbäume -- Generische Ansätze für die Optimierung -- Anhang.



https://doi.org/10.1007/978-3-642-05472-3
Rink, Michael;
Thresholds for matchings in random bipartite graphs with applications to hashing-based data structures, 2014. - Online-Ressource (PDF-Datei: XVII, 267 S., 1,95 MB) Ilmenau : Techn. Univ., Diss., 2014

Wir betrachten randomisierte Algorithmen, die bei Eingabe einer Menge S von n Schlüsseln aus einem Universum U, oder einer Menge von n Schlüssel-Wert-Paaren eine Datenstruktur für eine der folgenden Aufgaben bauen. Bei Aufruf der Operation lookup für einen Schlüssel x aus U: * Entscheide, ob x Element von S ist (Mengenzugehörigkeitstester [MZT]). * Falls x aus S ist, gib den Wert zurück welcher x zugeordnet ist. Ansonsten gib einen Wert mit der Interpretation "x ist nicht aus S" zurück (Wörterbuch [WB]) oder gib einen beliebigen Wert zurück (Retrieval-Datenstruktur [RDS]). * Falls x aus S ist, gib eine von x abhängige natürliche Zahl zurück, wobei für alle x aus S diese Zahlen paarweise verschieden sind und ihr Wertebereich in etwa die Größe n hat (perfekte Hashfunktion [PHF]). Die Datenstrukturen die wir behandeln sind Varianten von Cuckoo-Hashing und des Bloomier-Filters, welchen die gleiche einfache Struktur zu Grunde liegt. Sie bestehen aus einer Tabelle mit m Zellen der Breite r Bits sowie einer konstanten Anzahl an Hashfunktionen, welche benutzt werden, um die Elemente aus U auf eine konstante Anzahl an Tabellenzellen abzubilden. Unter der Annahme voll zufälliger Hashfunktionen beschäftigen wir uns damit, wie diese Datenstrukturen in Linearzeit (bezüglich n) konstruiert werden können und welche Ladung n/m bzw. welcher Platzverbrauch m&hahog;r in Abhängigkeit vom Zeitbedarf für lookup erreicht werden kann. Dies führt zu der Frage, ob ein bipartiter Zufallsgraph mit n Knoten (Schlüsseln) links und m Knoten (Zellen) rechts und Kanten bestimmt über die Hashfunktionenein Matching eines bestimmten Typs hat und darüber hinaus, wie solch ein Matching effizient berechnet werden kann. Schwerpunkte der Dissertation sind: * die Optimierung der Lookup-Zeit für WB und MZT (basierend auf Cuckoo-Hashing) bezüglich: (i) einer Beschränkung der durchschnittlichen Anzahl an Zellenzugriffen, (ii) der erwarteten Anzahl an Seitenzugriffen unter der Annahme, dass die Tabelle (Speicher) in Speicherseiten gleicher Größe unterteilt ist. * die Minimierung des Platzbedarfs von RDS und PHF (basierend auf dem Bloomier-Filter), wobei für jeden Schlüssel die Anzahl der Zellenzugriffe nach oben durch eine Konstante beschränkt ist. * eine effiziente Simulation voll zufälliger Hashfunktionen, welche von allen behandelten Datenstrukturen vorausgesetzt werden



http://www.db-thueringen.de/servlets/DocumentServlet?id=25985
Knacker, David;
Theoretische Betrachtungen zu Routing-Algorithmen. - 57 S. : Ilmenau, Techn. Univ., Bachelor-Arbeit, 2014

Die beste Möglichkeit, um in einem Graphen kürzeste Pfade zu berechnen, war für eine lange Zeit der Algorithmus von Dijkstra. In den letzten Jahren wurden jedoch mehrere Algorithmen entwickelt, welche einen alternativen Platz-Laufzeit-Trade-off ermöglichen. In dieser Arbeit werden wir zwei dieser Algorithmen genauer betrachten und uns überlegen, wie man diese analysiert. Diese sind die Contraction-Hierarchies, eingeführt von Geisberger et al. in "Faster and simpler hierarchical routing in road networks" und die Transit-Notes, eingeführt von Bast et al. in "Ultrafast shortest-path queries via transit nodes". Dafür führen wir eine neue Kenngröße für Graphen ein, die Highway-Dimension. Diese wurde von Abraham et al. in den Arbeiten "Highway dimension, shortest paths, and provably efficient algorithms" und "Vc-dimension and shortest path algorithms" definiert. Wir werden Aussagen über die Güte dieser Algorithmen, in Abhängigkeit dieser Kenngröße, treffen.



Csuhaj-Varjú, Ersébet; Dietzfelbinger, Martin; Ésik, Zoltán
Mathematical foundations of computer science 2014 : 39th international symposium, MFCS 2014, Budapest, Hungary, August 25 - 29, 2014 ; proceedings. - Berlin [u.a.] : Springer, 2014. - (Lecture notes in computer science ; ...)
Pape, Felix;
Einfache und effiziente Algorithmen für Rank/Select auf Bitmaps. - 33 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2014

Rank und Select sind wichtige Operationen für platzeffiziente Datenstrukturen, weshalb es interessant ist, diese möglichst schnell und platzsparend Lösen zu können. Rank gibt die Anzahl der 1-Bits bis zu einer Position an und Select liefert die Position des i-ten 1-Bits. Es existieren Algorithmen die in der Theorie diese Probleme mit konstantem Zeitaufwand lösen können. Im Rahmen dieser Bachelorarbeit werden unterschiedliche Algorithmen und Grundlagen für rank und select auf Bitmaps betrachtet und diese auf ihre Laufzeit sowie ihren Platzverbrauch auf 64-bit Architekturen hin untersucht. Es wird näher auf die Algorithmen von Vigna, sowie die von Navarro und Providel eingegangen. Diese Algorithmen und deren Grundlagen werden beschrieben und in der Praxis verglichen.



Aumüller, Martin; Dietzfelbinger, Martin; Dietzfelbinger, Martin *1956-*; Wölfel, Philipp;
Explicit and efficient hash families suffice for cuckoo hashing with a stash. - In: Algorithmica, ISSN 1432-0541, Bd. 70 (2014), 3, S. 428-456

It is shown that for cuckoo hashing with a stash as proposed by Kirsch et al. (Proc. 16th European Symposium on Algorithms (ESA), pp. 611-622, Springer, Berlin, 2008) families of very simple hash functions can be used, maintaining the favorable performance guarantees: with constant stash size s the probability of a rehash is O(1/n^(s+1)), the lookup time and the deletion time are O(s) in the worst case, and the amortized expected insertion time is O(s) as well. Instead of the full randomness needed for the analysis of Kirsch et al. and of Kutzelnigg (Discrete Math. Theor. Comput. Sci., 12(3):81-102, 2010) (resp. (log n)-wise independence for standard cuckoo hashing) the new approach even works with 2-wise independent hash families as building blocks. Both construction and analysis build upon the work of Dietzfelbinger and Woelfel (Proc. 35th ACM Symp. on Theory of Computing (STOC), pp. 629-638, 2003). The analysis, which can also be applied to the fully random case, utilizes a graph counting argument and is much simpler than previous proofs. The results can be generalized to situations where the stash size is non-constant.



http://dx.doi.org/10.1007/s00453-013-9840-x
Dietzfelbinger, Martin; Wölfel, Philipp;
Tight lower bounds for greedy routing in higher-dimensional small-world grids. - In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, (2014), S. 816-829

We consider Kleinberg's celebrated small world graph model (Kleinberg, 2000), in which a D-dimensional grid {0,\dots,n-1}^D is augmented with a constant number of additional unidirectional edges leaving each node. These long range edges are determined at random according to a probability distribution (the augmenting distribution), which is the same for each node. Kleinberg suggested using the inverse D-th power distribution, in which node v is the long range contact of node u with a probability proportional to |u-v|^(-D). He showed that such an augmenting distribution allows to route a message efficiently in the resulting random graph: The greedy algorithm, where in each intermediate node the message travels over a link that brings the message closest to the target w.r.t. the Manhattan distance, finds a path of expected length O((log n)^2) between any two nodes. We prove that greedy routing does not perform asymptotically better for any uniform and isotropic augmenting distribution, i.,e., the probability that node u has a particular long range contact v is independent of the labels of u and v and only a function of |u-v|. In particular, we show that for such graphs the expected greedy routing time between two arbitrary nodes s and t is Omega((log|s-t|)^2). This lower bound proves and strengthens a conjecture by Aspnes, Diamadi, and Shah (2000). In order to obtain the result, we introduce a novel proof technique: We define a so-called budget game, in which a token travels over a game board, from one end to the other, while the player manages a "probability budget". In each round, the player "bets" part of her remaining probability budget on step sizes. A step size is chosen at random according to a probability distribution of the player's bet. The token then makes progress as determined by the chosen step size, while some of the player's bet is removed from her probability budget. We prove a tight lower bound for such a budget game, and then obtain a lower bound for greedy routing in the D-dimensional grid by a reduction.



Chemissov, Alexej;
Evaluierung effizienter Hashverfahren mit randomisierten Hashfunktionen. - 47 S. : Ilmenau, Techn. Univ., Bachelor-Arbeit, 2014

In dieser Arbeit werden mehrere Hashverfahren betrachtet und implementiert. Anschließend werden die Verfahren anhand geeigneter Experimente miteinander verglichen. Das Ziel der Arbeit ist, anhand der Experimente eine Aussage bezüglich des praktischen Einsatzes der Verfahren zu treffen. Wir betrachten offenes Hashing mit verketteten Listen und erweitern dieses auf binäre Bäume und AVL-Bäume. Weiterhin untersuchen wir zwei geschlossene Hashverfahren: Robin Hood Hashing und eine Kombination aus d-ärem und geblocktem Cuckoo Hashing. Unterschiedliche Einfügestrategien für das Cuckoo Hashing, wie Random Walk, Local Search von Megha Khosla und Breitensuchenstrategie, werden miteinander verglichen. Wir untersuchen das Verhalten der Verfahren mit und ohne Verdopplungsstrategie und stellen fest, für welche Zwecke jedes der vorgestellten Hashverfahren besser geeignet ist.



Hirte, Steffen;
Load balancing using iterated bisection. - 56 S. Ilmenau : Techn. Univ., Masterarbeit, 2014

Das Problem der Lastbalancierung tritt auf, wenn eine große Berechnungsaufgabe in kleinere Instanzen zerteilt und auf mehreren Prozessoren separat ausgefuhrt werden muss. Aus praktischen Gründen ist es oftmals ungünstig oder zu schwierig, ein Problem direkt in die gewünschte Anzahl an Stücken zu teilen. Deswegen bietet sich die wiederholte Zweiteilung eines Problems an. Dabei wird das HeaviestFirst-Prinzip berücksichtigt, d.h. es wird stets die größte, noch nicht geteilte Instanz als nächstes fragmentiert. Wenn genug Stücke erzeugt wurden, können diese auf die Prozessoren verteilt und ausgeführt werden. Weil das größte erzeugte Stück die Gesamtlaufzeit auf dem parallelen System bestimmt, ist es wünschenswert, dass alle entstehenden Probleme etwa gleich groß sind. Die Problemstellung wurde von Bischof, Ebner und Erlebach (1998) eingeführt. In derselben Arbeit erfolgte für verschiedene Verteilungsklassen eine Worstcase-Analyse. Weiterhin zeigten Bischof, Schickinger und Steger (1999), dass man auch fur pessimistische Verteilungen eine gute erwartete Gesamtlaufzeit vorhersagen kann. Mit Hilfe der Methoden von Dean, Majumdar (2002) und Janson, Neininger (2008) lässt sich das durchschnittliche Gewicht des größten resultierenden Teilproblems fur ein gegebenes Ausgangproblem explizit ermitteln. Dabei muss jedoch die Schnittverteilung für jede auftretende Instanz explizit bekannt und vor allem gleich sein. In dieser Arbeit wird eine Situation betrachtet, in der die Schnittverteilungen aus einer Verteilungsklasse frei gewählt werden können. Es wird gezeigt, dass sich die entstehenden Problemgewichte durchschnittlich nur mit konstantem Faktor vom Optimalwert unterscheiden. Weiterhin wird demonstriert, dass auch die Abweichung vom Erwartungswert klein ist.



Klaue, Pascal;
Optimale Partitionierungsverfahren für Multi-Pivot-Quicksort. - 65 S. : Ilmenau, Techn. Univ., Masterarbeit, 2014

Vor kurzer Zeit wurde eine neue Implementierung von Quicksort als Standard der Java 7 Laufzeitbibliothek gewählt. Überraschenderweise nutzte diese Implementierung zwei Pivotelemente, trotz der Annahme, dass dies zu keiner Verbesserung führen wird. Dadurch wurde neues Interesse in der Nutzbarkeit von Multipivotquicksort geweckt. Deswegen stelle ich in dieser Arbeit eine Methode vor, die es erlaubt eines der einflussreichsten Kostenmaße für das Sortieren, die Anzahl an Vergleichen, zu analysieren. Diese nutze ich um für dieses Kostenmaß optimale Partitionierungsverfahren zu beschreiben. Die Auswirkungen dieser optmalen Partitionierungsverfahren werden, dabei sowohl theoretisch, als auch experiementell untersucht.



Aumüller, Martin; Dietzfelbinger, Martin;
Optimal partitioning for dual pivot quicksort. - In: Automata, Languages, and Programming, (2013), S. 33-44

http://dx.doi.org/10.1007/978-3-642-39206-1_4
Mattern, Christopher;
Linear and geometric mixtures - analysis. - In: Data Compression Conference (DCC), 2013, ISBN 978-0-7695-4965-1, (2013), S. 301-310

http://dx.doi.org/10.1109/DCC.2013.38
Sukiennik, David;
Schnelle Kompression von Sensordaten. - 76 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2013

Das Ziel der Bachelorarbeit "Schnelle Kompression von Sensordaten" war die Entwicklung eines Kompressionsverfahrens für Sensordaten unter den restriktiven Bedingungen eingebetteter Systeme. Beispielsweise im Bereich der Medizin, Hausautomatisierung oder der Umweltüberwachung erfassen eingebettete Systeme Sensordaten, wobei eine Kompression einige Vorteile mit sich bringt. Eingangs werden Grundlagen über Sensordaten, Hard- und Software sowie Kompression geschaffen. Das Konzept prädiktorbasierter Kompression wird eingeführt. Anschließend wird eine Übersicht über geeignete Verfahren aus der Literatur und deren Struktur und Methoden erstellt. Daraufhin wird ein Konzept entworfen, das die vorher ausgearbeiteten Probleme lösen und gleichzeitig Restriktionen beachten soll: Es soll eine Bibliothek für prädiktorbasierte Kompression entstehen, die verschiedene Kombinationenen aus einer Auswahl diverser Prädiktoren und Codierungen ermöglicht. So kann einer Vielzahl der diffusen Beschränkungen Beachtung geschenkt werden. Im darauffolgenden Teil werden die Implementierung und ihre Abweichungen von der mathematischen Beschreibung nachgezeichnet. In der anschließenden Evaluierung und dem Vergleich mit bestehenden Verfahren ließen sich die Ergebnisse der Literatur reproduzieren. Teilweise gab es leichte Abweichungen, oft ließen sich die Verfahren aus der Literatur aber überbieten. Abschließend wird ein Ausblick gegeben mit Verbesserungsmöglichkeiten für die Bibliothek.



Rink, Michael;
Mixed hypergraphs for linear-time construction of denser hashing-based data structures. - In: SOFSEM 2013: Theory and Practice of Computer Science, (2013), S. 356-368

http://dx.doi.org/10.1007/978-3-642-35843-2_31
Jaberi, Raed;
Effiziente Algorithmen für grundlegende Graphprobleme. - 169 S. : Ilmenau, Techn. Univ., Masterarbeit, 2013

Die Berechnung der starken Zusammenhangskomponenten eines gerichteten Graphen ist eine wichtige Anwendung der Tiefensuche. Diese Arbeit beschäftigt sich mit bekannten Algorithmen für dieses Problem, die alle lineare Zeit benötigen: Tarjan-Algorithmus, Kosaraju-Sharir-Algorithmus und Cheriyan-Mehlhorn-Gabow-Algorithmus. Modifizierte Versionen werden in dieser Arbeit beschrieben und untersucht. Diese Varianten machen die Algorithmen schneller oder sparen Speicherplatz. Die Verfahren werden experimentell verglichen. Diese Arbeit befasst sich auch mit grundlegenden Graphproblemen für das Durchsuchen von großen Graphen, die nicht in den Hauptspeicher passen. Schließlich werden effiziente externe Algorithmen auf azyklische gerichtete Graphen, deren topologische Sortierung gegeben ist, beschrieben. Diese Algorithmen benutzen den Technik Time-Forward-Processing.



Dietzfelbinger, Martin;
On randomness in Hash functions. - In: 29th International Symposium on Theoretical Aspects of Computer Science, (2012), S. 25-28

In the talk, we shall discuss quality measures for hash functions used in data structures and algorithms, and survey positive and negative results. (This talk is not about cryptographic hash functions.) For the analysis of algorithms involving hash functions, it is often convenient to assume the hash functions used behave fully randomly; in some cases there is no analysis known that avoids this assumption. In practice, one needs to get by with weaker hash functions that can be generated by randomized algorithms. A well-studied range of applications concern realizations of dynamic dictionaries (linear probing, chained hashing, dynamic perfect hashing, cuckoo hashing and its generalizations) or Bloom filters and their variants. A particularly successful and useful means of classification are Carter and Wegman's universal or k-wise independent classes, introduced in 1977. A natural and widely used approach to analyzing an algorithm involving hash functions is to show that it works if a sufficiently strong universal class of hash functions is used, and to substitute one of the known constructions of such classes. This invites research into the question of just how much independence in the hash functions is necessary for an algorithm to work. Some recent analyses that gave impossibility results constructed rather artificial classes that would not work; other results pointed out natural, widely used hash classes that would not work in a particular application. Only recently it was shown that under certain assumptions on some entropy present in the set of keys even 2-wise independent hash classes will lead to strong randomness properties in the hash values. The negative results show that these results may not be taken as justification for using weak hash classes indiscriminately, in particular for key sets with structure. When stronger independence properties are needed for a theoretical analysis, one may resort to classic constructions. Only in 2003 it was found out how full randomness can be simulated using only linear space overhead (which is optimal). The "split-and-share" approach can be used to justify the full randomness assumption in some situations in which full randomness is needed for the analysis to go through, like in many applications involving multiple hash functions (e.g., generalized versions of cuckoo hashing with multiple hash functions or larger bucket sizes, load balancing, Bloom filters and variants, or minimal perfect hash function constructions). For practice, efficiency considerations beyond constant factors are important. It is not hard to construct very efficient 2-wise independent classes. Using k-wise independent classes for constant k bigger than 3 has become feasible in practice only by new constructions involving tabulation. This goes together well with the quite new result that linear probing works with 5-independent hash functions. Recent developments suggest that the classification of hash function constructions by their degree of independence alone may not be adequate in some cases. Thus, one may want to analyze the behavior of specific hash classes in specific applications, circumventing the concept of k-wise independence. Several such results were recently achieved concerning hash functions that utilize tabulation. In particular if the analysis of the application involves using randomness properties in graphs and hypergraphs (generalized cuckoo hashing, also in the version with a "stash", or load balancing), a hash class combining k-wise independence with tabulation has turned out to be very powerful.



http://dx.doi.org/10.4230/LIPIcs.STACS.2012.25
Mattern, Christopher;
Mixing strategies in data compression. - In: Data Compression Conference (DCC), 2012, ISBN 978-1-4673-0715-4, (2012), S. 337-346

We propose geometric weighting as a novel method to combine multiple models in data compression. Our results reveal the rationale behind PAQ-weighting and generalize it to a non-binary alphabet. Based on a similar technique we present a new, generic linear mixture technique. All novel mixture techniques rely on given weight vectors. We consider the problem of finding optimal weights and show that the weight optimization leads to a strictly convex (and thus, good-natured) optimization problem. Finally, an experimental evaluation compares the two presented mixture techniques for a binary alphabet. The results indicate that geometric weighting is superior to linear weighting.



http://dx.doi.org/10.1109/DCC.2012.40
Seifert, Andreas;
Moderne Verfahren der Routenplanung. - 73 S. : Ilmenau, Techn. Univ., Bachelor-Arbeit, 2012

Durch die Verfügbarkeit von detaillierten Straßendaten in digitaler Form ist die Bedeutung der Routenplanung in den letzten Jahren erheblich gestiegen. Neben dem genaueren Datenmaterial ermöglichen schnellere, auf Straßengraphen spezialisierte Algorithmen in Kombination mit moderner Hardware neue Anwendungsmöglichkeiten. In dieser Arbeit werden mehrere Verfahren vorgestellt, welche zu den derzeit schnellsten Algorithmen zur Wegfindung in Straßengraphen zählen. Mit unserer Implementierung werden die Eigenschaften dieser Algorithmen in Experimenten untersucht. Untersucht werden die Algorithmen PHAST, ContractionHierarchies und HubLabeling.



Aumüller, Martin; Dietzfelbinger, Martin; Dietzfelbinger, Martin *1956-*; Wölfel, Philipp;
Explicit and efficient hash families suffice for cuckoo hashing with a stash. - In: Algorithms – ESA 2012, (2012), S. 108-120

http://dx.doi.org/10.1007/978-3-642-33090-2_11
Rothenberger, Ralf;
Neue effiziente Versionen des "Lovász Local Lemma (LLL)". - 155 S. : Ilmenau, Techn. Univ., Masterarbeit, 2012

1975 formulierten Erdös und Lovász das Lovász Local Lemma (LLL). Dieses gibt lokale Bedingungen an, die jedes Ereignis einer Menge erfüllen muss, damit mit positiver Wahrscheinlichkeit kein Ereignis dieser Menge eintritt. Das LLL kann verwendet werden, um Existenzbeweise mit der probabilistischen Methode zu führen, beispielsweise um die Existenz erfüllender Belegungen für bestimmte KNF-Formeln zu zeigen. 1991 demonstrierte Beck erstmals, dass es auch eine konstruktive Variante des LLL unter etwas stärkeren Bedingungen gibt. 2010 gelang es Moser und Tardos, einen konstruktiven Beweis des LLL mit Hilfe eines einfachen randomisierten Algorithmus anzugeben, durch den die meisten Anwendungen des LLL algorithmisch gemacht werden können. Weiterhin geben Moser und Tardos eine Parallelisierung und eine Derandomisierung ihres Algorithmus an. In der Arbeit werden die Ergebnisse von Moser und Tardos sowie einige genauere Analysen und Verbesserungen der Moser-Tardos-Algorithmen durch andere Autoren vorgestellt. Insbesondere werden die Bedingungen, unter denen algorithmische Versionen des LLL möglich sind, genauer definiert.



Beyer, Stephan;
Analysis of the linear probing variant of cuckoo hashing. - 53 S. Ilmenau : Techn. Univ., Diplomarbeit, 2012

Cuckoo Hashing ist ein Hashingverfahren mit zwei Hashfunktionen, das Zugriffsoperationen im schlechtesten Fall in konstanter Zeit erlaubt. Leider wird dabei nur knapp die halbe Hash-Tabelle ausgenutzt. Eine bekannte Strategie zur Auflösung von Kollisionen ist lineares Sondieren, womit die gesamte Tabelle ausgenutzt werden kann. Allerdings werden Zugriffe mit zunehmender Tabellenauslastung extrem langsam. Wir analysieren den Platzverbrauch einer Cuckoo-Hashing-Variante, bei der zusätzlich ein Sondierungsschritt pro Hashfunktion erlaubt ist. Im Vergleich zu der Cuckoo-Hashing-Variante, die mind. 3 Hashfunktionen nutzt, eignet sich die Cuckoo-Hashing-Variante mit zusätzlichem Sondierungsschritt eher für Cache-Architekturen. Experimente haben bereits gezeigt, dass bei unserer Cuckoo-Hashing-Variante eine Platzauslastung von ungefähr 96,3% der Hash-Tabelle möglich ist. Wir beweisen (mehr oder weniger formal) eine obere und untere Schranke der Platzauslastung. Wir zeigen, dass unsere Cuckoo-Hashing-Variante mit hoher Wahrscheinlichkeit funktioniert, wenn die Platzauslastung höchstens 82,9% ist. Wir zeigen, dass sie mit hoher Wahrscheinlichkeit nicht funktioniert, wenn die Auslastung mindestens 98,1% beträgt.



Mattern, Christopher;
Combining non-stationary prediction, optimization and mixing for data compression. - In: First International Conference on Data Compression, Communications and Processing (CCP), 2011, ISBN 978-0-7695-4528-8, (2011), S. 29-37

http://dx.doi.org/10.1109/CCP.2011.22
Draque Penso, Lucia; Rautenbach, Dieter; Szwarcfiter, Jayme Luiz
Connectivity and diameter in distance graphs. - In: Networks, ISSN 1097-0037, Bd. 57 (2011), 4, S. 310-315

http://dx.doi.org/10.1002/net.20397
Dietzfelbinger, Martin; Mitzenmacher, Michael; Rink, Michael
Cuckoo hashing with pages. - In: Algorithms - ESA 2011, (2011), S. 615-627

http://dx.doi.org/10.1007/978-3-642-23719-5
Zapf, Benjamin;
Theoretische und experimentelle Untersuchungen zu modernen Priority-Queue-Realisierungen. - 116 S. : Ilmenau, Techn. Univ., Diplomarbeit, 2011

In der Informatik sind Prioritätswarteschlangen oder Priority Queues oft verwendete und etablierte Hilfsmittel, um in kurzer Zeit Objekte nach einer bestimmten Wichtung auszugeben. Auch aus diesem Grund haben Verbesserungen in diesem Bereich nichts von ihrer wissenschaftlichen Relevanz eingebüßt. Verschiedene Forschungseinrichtungen sind dabei diese Priority Queues effektiver oder auch nur einfacher zu gestalten. Dabei werden unterschiedliche Denkansätze verfolgt. Diese reichen von dynamischeren Baumstrukturen bis hin zu mehrteiligen Heaps. Die vorliegende Arbeit beschreibt und analysiert Ideen verschiedener Autoren aus den Jahren 2005 bis 2010 und führt einen Vergleich ausgewählter Arten an praktischen Beispielen durch. Die Algorithmen lassen sich hierbei nach den verschiedenen Baumstrukturen einteilen, auf denen sie aufgebaut sind. Daneben ist eine Unterteilung der Algorithmen nach ihrer Struktur möglich. Während bei einigen eine starre Struktur mit Markierungen genutzt wird, bieten andere Algorithmen die Möglichkeit die Struktur eingeschränkt oder auch zu großen Teilen zu variieren.



Dietzfelbinger, Martin;
Fingerprinting. - In: Algorithms unplugged, (2011), S. 181-193

Dietzfelbinger, Martin; Rowe, Jonathan E.; Wegener, Ingo; Wölfel, Philipp
Precision, local search and unimodal functions. - In: Algorithmica, ISSN 1432-0541, Bd. 59 (2011), 3, S. 301-322

We investigate the effects of precision on the efficiency of various local search algorithms on 1-D unimodal functions. We present a (1+1)-EA with adaptive step size which finds the optimum in O(log n) steps, where n is the number of points used. We then consider binary (base-2) and reflected Gray code representations with single bit mutations. The standard binary method does not guarantee locating the optimum, whereas using the reflected Gray code does so in O ((log n)2) steps. A(1+1)-EA with a fixed mutation probability distribution is then presented which also runs in O ((log n)2). Moreover, a recent result shows that this is optimal (up to some constant scaling factor), in that there exist unimodal functions for which a lower bound of Omega ((log n)2) holds regardless of the choice of mutation distribution. For continuous multimodal functions, the algorithm also locates the global optimum in O((log n)2). Finally, we show that it is not possible for a black box algorithm to efficiently optimise unimodal functions for two or more dimensions (in terms of the precision used).



http://dx.doi.org/10.1007/s00453-009-9352-x
Vöcking, Berthold; Alt, Helmut; Dietzfelbinger, Martin; Reischuk, Rüdiger; Scheideler, Christian; Vollmer, Heribert; Wagner, Dorothea
Algorithms unplugged. - Berlin, Heidelberg : Springer-Verlag, 2011. - Online-Ressource (X, 406 S.) ISBN 978-3-642-15328-0
Description based upon print version of record

Algorithms specify the way computers process information and how they execute tasks. Many recent technological innovations and achievements rely on algorithmic ideas - they facilitate new applications in science, medicine, production, logistics, traffic, communi cation and entertainment. Efficient algorithms not only enable your personal computer to execute the newest generation of games with features unimaginable only a few years ago, they are also key to several recent scientific breakthroughs - for example, the sequencing of the human genome would not have been possible without the invention of new algorithmic ideas that speed up computations by several orders of magnitude. The greatest improvements in the area of algorithms rely on beautiful ideas for tackling computational tasks more efficiently. The problems solved are not restricted to arithmetic tasks in a narrow sense but often relate to exciting questions of nonmathematical flavor, such as: How can I find the exit out of a maze? How can I partition a treasure map so that the treasure can only be found if all parts of the map are recombined? How should I plan my trip to minimize cost? Solving these challenging problems requires logical reasoning, geometric and combinatorial imagination, and, last but not least, creativity - the skills needed for the design and analysis of algorithms. In this book we present some of the most beautiful algorithmic ideas in 41 articles written in colloquial, nontechnical language. Most of the articles arose out of an initiative among German-language universities to communicate the fascination of algorithms and computer science to high-school students. The book can be understood without any prior knowledge of algorithms and computing, and it will be an enlightening and fun read for students and interested adults.



http://dx.doi.org/10.1007/978-3-642-15328-0
Ackermann, Heiner; Röglin, Heiko; Schellbach, Ulf; Schweer, Nils
Analysis of algorithms. - In: Algorithm engineering, (2010), S. 127-193

http://dx.doi.org/10.1007/978-3-642-14866-8_4
Dietzfelbinger, Martin;
Ingo Wegener: seine Bücher. - In: Informatik-Spektrum, ISSN 1432-122X, Bd. 33 (2010), 4, S. 485

http://dx.doi.org/10.1007/s00287-010-0463-1
Dourado, Mitre Costa; Draque Penso, Lucia; Rautenbach, Dieter; Szwarcfiter, Jayme Luiz
Brief announcement: on reversible and irreversible conversions. - In: Distributed computing, (2010), S. 395-397

We study two types of iterative 0/1-vertex-labeling processes in arbitrary network graphs where in each synchronous round every vertex - either never changes its label from 1 to 0, and changes its label from 0 to 1 if sufficiently many neighbours have label 1, - or changes its label if sufficiently many neighbours have a different label. In both scenarios the number of neighbours required for a change depends on individual threshold values of the vertices. Our contributions concern computational aspects related to the sets with minimum cardinality of vertices with initial label 1 such that during the process all vertices eventually change their label to 1 and remain with 1 as label. We establish hardness results for the general case and describe efficient algorithms for restricted instances.



http://dx.doi.org/10.1007/978-3-642-15763-9_37
Junqueira, Flavio Paiva; Marzullo, Keith; Herlihy, Maurice; Draque Penso, Lucia
Threshold protocols in survivor set systems. - In: Distributed computing, ISSN 1432-0452, Bd. 23 (2010), 2, S. 135-149

Many replication protocols employ a threshold model when expressing failures they are able to tolerate. In this model, one assumes that no more than t out of n components can fail, which is a good representation when failures are independent and identically distributed (IID). In many real systems, however, failures are not IID, and a straightforward application of threshold protocols yields suboptimal results. Here, we examine the problem of transforming threshold protocols into survivor-set protocols tolerating dependent failures. Our main goal is to show the equivalence between the threshold model and the core/survivor set model. Toward this goal, we develop techniques to transform threshold protocols into survivor set ones. Our techniques do not require authentication, self-verification or encryption. Our results show in one case that we can transform a threshold protocol to a subset by spreading a number of processes across processors. This technique treats a given threshold algorithm as a black box, and consequently can transform any threshold algorithm. However, it has the disadvantage that the transformation is not possible for all sets of survivor sets. The second technique instead focuses on transforming voters: functions that evaluate to a value out of a set of tallied values in a replication protocol. Voters are an essential part of many fault-tolerant protocols, and we show a universal way of transforming them. With such a transformation we expect that a large number of protocols in the literature can be directly transformed with our technique. It is still an open problem, however, if the two models are equivalent, and our results constitute an important first step in this direction.



http://dx.doi.org/10.1007/s00446-010-0107-3
Draque Penso, Lucia; Rautenbach, Dieter; Szwarcfiter, Jayme Luiz
Long cycles and paths in distance graphs. - In: Discrete mathematics, Bd. 310 (2010), 23, S. 3417-3420

For n a natural number and D a set of natural numbers, the distance graph P^D_n has vertex set {0,...,n-1}and edge set { ij | 0 <= i,j <= n-1, |j-i| is in D}. Note that the important and very well-studied circulant graphs coincide with the regular distance graphs. A fundamental result concerning circulant graphs is that for these graphs, a simple greatest common divisor condition, their connectivity, and the existence of a Hamiltonian cycle are all equivalent. Our main result suitably extends this equivalence to distance graphs. We prove that for a finite set D of order at least 2, there is a constant c_D such that the greatest common divisor of the integers in D is 1 if and only if for every n, P^D_n has a component of order at least n-c_D if and only if for every n >= c_D+3, P^D_n has a cycle of order at least n-c_D. Furthermore, we discuss some consequences and variants of this result.



http://dx.doi.org/10.1016/j.disc.2010.07.020
Dietzfelbinger, Martin; Goerdt, Andreas; Mitzenmacher, Michael; Montanari, Andrea; Pagh, Rasmus; Rink, Michael
Tight thresholds for cuckoo hashing via XORSAT. - In: Automata, languages and programming, (2010), S. 213-225

http://dx.doi.org/10.1007/978-3-642-14165-2_19
Dietzfelbinger, Martin; Rowe, Jonathan E.; Wegener, Ingo; Wölfel, Philipp
Tight bounds for blind search on the integers and the reals. - In: Combinatorics, probability & computing, ISSN 1469-2163, Bd. 19 (2010), 5/6, S. 711-728

https://doi.org/10.1017/S0963548309990599
Rothenberger, Ralf;
Shellsort: Analyse und Bewertung eines einfachen dateninvarianten randomisierten Sortierverfahrens. - 75 S. : Ilmenau, Techn. Univ., Bachelor-Arbeit, 2010

Die Arbeit beschäftigt sich mit dem 2010 in Michael T. Goodrichs Paper "Randomized Shellsort: A Simple Data-Oblivious Sorting Algorithm" vorgestellten randomisierten Shellsort-Algorithmus. Die in dem Paper gelieferten Inhalte und Beweise werden nachvollzogen und überprüft, für eventuell auftretende Unklarheiten werden außerdem alternative Lösungswege aufgezeigt. Als Ziel der Arbeit wird formal nachgewiesen, dass Goodrichs Algorithmus einfach und dateninvariant ist, über eine garantierte Laufzeit von O(n log n) verfügt und jede Eingabe mit sehr hoher Wahrscheinlichkeit sortiert. Die sehr hohe Sortierwahrscheinlichkeit wird außerdem experimentell nachgewiesen.



Aumüller, Martin;
An alternative analysis of cuckoo hashing with a stash and realistic hash functions. - 98 S. : Ilmenau, Techn. Univ., Diplomarbeit, 2010
Enth. außerdem: Thesen

Diese Arbeit beschäftigt sich mit Cuckoo-Hashing, einem speziellen Hash-Verfahren. Ein Nachteil dieses Verfahrens ist, dass das Einfügen eines Elements mit einer kleinen Wahrscheinlichkeit fehlschlägt. Diese ist für einige Anwendungen groß genug, um Cuckoo-Hashing trotz seiner guten Laufzeiteigenschaften dort nicht praktikabel einsetzen zu können. Eine aktuelle Arbeit von Kirsch et al. schlägt eine Lösung für dieses Problem vor, indem ein kleiner zusätzlicher Speicher, der sogenannte Stash, eingeführt wird. In dieser Diplomarbeit geben wir einen neuen Beweis dafür, dass der Stash in Cuckoo-Hashing zu einer enorm reduzierten Fehlerwahrscheinlichkeit führt. Weiterhin werden wir zeigen, dass dieser keinen wesentlichen Einfluss auf die Laufzeiten der insert-, delete- und lookup-Operationen hat. Wir werden beweisen, dass unsere Analyse für eine Klasse von effizient auswertbaren Hashfunktionen gilt und somit eine offene Frage von Kirsch et al. beantworten. Für diese Klasse wird ein abstraktes Ergebnis vorgestellt, das es ermöglicht die Idee dieser Hashklasse auch in anderen Zusammenhängen zu nutzen. In Experimenten zeigen wir auf, dass schon ein kleiner zusätzlicher Speicher mit nur neun Speicherplätzen für Schlüssel eine enorme Verbesserung für die praktische Einsatzfähigkeit von Cuckoo-Hashing bringt. Wir können damit problemlos in der Nähe der theoretisch maximalen Tabellenauslastung von Cuckoo-Hashing arbeiten, ohne Gefahr zu laufen, dass die Datenstruktur durch eine fehlschlagende Einfügeoperation neu aufgebaut werden muss. Insbesondere im Falle kleiner Tabellen wird sich der Stash als wertvolle Erweiterung erweisen. Weiterhin werden wir auch die zwei populären Varianten d-äres Cuckoo-Hashing und geblocktes Cuckoo-Hashing näher betrachten. Dabei wird sich herausstellen, dass in diesen Varianten ein zusätzlicher Speicher die Fehlerwahrscheinlichkeit bei kleinen Tabellengrößen deutlich senkt. Im Gegensatz zu normalem Cuckoo-Hashing ist ein Stash jedoch im Falle großer Tabellen nutzlos.



Draque Penso, Lucia; Rautenbach, Dieter; Szwarcfiter, Jayme Luiz
Cycles, paths, connectivity and diameter in distance graphs. - In: Graph theoretic concepts in computer science, (2010), S. 320-328

http://dx.doi.org/10.1007/978-3-642-11409-0
Osdoba, Manuel;
Moderne Konstruktionen von Expandergraphen. - 84 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2010

Expandergraphen sind in Bezug auf die Kanten dünn besetzte Graphen, die gleichzeitig eine hohe Konnektivität besitzen. Die Feststellung ob man in einem Expander mit einem gewünschten Expansionsgrad expandieren kann ist co-NP-vollständig. Folglich ist das Generieren eines gewünschten Graphen durch Erraten der Adjazenzmatrix sehr ineffizient. Diese Arbeit nutzt Erkenntnisse eines Papers (2008) von Noga Alon, Asaf Shapira und Oded Schwartz. Hierauf basierend werden Konstruktionen von expliziten und voll expliziten Expandern die in der Knotenanzahl polynomiell berechenbar sind vorgestellt. Zur Generierung großer Expander wird das Ersetzungsprodukt (Replacement Product) genutzt. Dieses lässt durch die mehrmalige Einbettung eines Expanders in einen anderen einen großen Expander entstehen, für den dann der Expansionsparameter abgeschätzt wird. Weiterhin sind Beweise zu finden die die Abhängigkeit des Expansionsparameters von dem zweitgrößten Eigenwert darstellen.



Niggl, Karl-Heinz; Wunderlich, Henning
Implicit characterizations of FPTIME and NC revisited. - In: The journal of logic and algebraic programming, Bd. 79 (2010), 1, S. 47-60

Various simplified or improved, and partly corrected well-known implicit characterizations of the complexity classes FPTIME and NC are presented. Primarily, the interest is in simplifying the required simulations of various recursion schemes in the corresponding (implicit) framework, and in developing those simulations in a more uniform way, based on a step-by-step comparison technique, thus consolidating groundwork in implicit computational complexity.



http://dx.doi.org/10.1016/j.jlap.2009.02.005
Peilke, Hendrik;
Algorithmen für Datenströme: ein extrem platzeffizienter Algorithmus für das Finden von Duplikaten. - 55 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2009

Für einen Datenstrom der Länge n über dem Alphabet [m] mit n>m, betrachtet die Arbeit das Problem des Duplikatfindens mit einem einzigen Durchlauf. Es wird ein randomisiertes Lösungsverfahren für dieses Problem vorgestellt, welches lediglich Platz O((log m)&dzcy;) Bits benötigt. Dieser Algorithmus wurde Anfang 2009 von P. Gopalan und J. Radhakrishnan in ihrer Arbeit "Finding Duplicates in a Data Stream" vorgestellt und beantwortet die Frage nach der Existenz eines randomisierten Algorithmus für das Problem FindeDuplikat mit sublinearem Platzverbrauch. Die Arbeit verfeinert und erweitert dabei das zu Grunde liegende Werk.



Wunderlich, Henning;
Contributions to structural communication complexity, 2009. - Online-Ressource (PDF-Datei: 91 S., 740 KB) Ilmenau : Techn. Univ., Diss., 2009

In der Dissertation werden strukturelle Probleme in Yaos Kommunikationsmodell untersucht, die sich thematisch drei Bereichen dieses Gebietes zuordnen lassen: Der erste Teil der Arbeit beschäftigt sich mit dem fundamentalen Problem der Herleitung unterer Schranken für die randomisierte Kommunikationskomplexität. Hauptergebnis ist die folgende Charakterisierung, die auch als nicht-triviale Verallgemeinerung von Shannons "Noiseless Coding Theorem" angesehen werden kann: die durchschnittliche deterministische Informationskomplexität stimmt bis auf einen konstanten Faktor mit der durchschnittlichen deterministischen Kommunikationskomplexität überein, und zwar für jede Funktion und jede Verteilung auf den Eingaben. Ein weiteres Ergebnis sind untere Schranken für die public coin Las Vegas Kommunikationskomplexität, die um einen konstanten Faktor besser sind, als die bis dahin bekannten. Der zweite Teil beschäftigt sich mit der 30 Jahre alten PH-vs.-PSPACE-Frage in der Kommunikationskomplexität. Wir übertragen dazu die Todaschen Sätze aus der klassischen Komplexitätstheorie in Yaos Modell und entwickeln ein Maß für die Klasse BP-Parität-P, denapproximativen GF(2)-Rang. Über eine enge Beziehung zu dem Konzept"matrix rigidity" erhalten wir ein Maßkonzentrationsresultat: die meisten Funktionen haben eine fast lineare BP-Parität-P-Komplexität. Wir entwickeln außerdem ein Protokoll für die innere Produktfunktionmod 2 mit wenigen Alternierungen. Dies könnte darauf hinweisen, dass die Klasse BP-Parität-P "klein" ist im Vergleich zu PSPACE. Des Weiteren leiten wir für auf dünnen quasi-zufälligen Graphfamilien basierenden Adjazenzproblemen eine hohe Parität-P-Komplexität her, die dem Logarithmus des Kehrwerts der Kantendichte entspricht. Im dritten Teil untersuchen wir Überdeckungsstrukturgraphen. Diese sind definiert als Schnittgraphen von maximalen monochromatischen Untermatrizen einer Matrix. Wir zeigen, dass nicht jeder Graph ein Überdeckungsstrukturgraph ist. Danach betrachten wir die Teilklasseder "schönen" Graphen und charakterisieren schöne quadratfreie bipartite und schöne Kantengraphen quadratfreier bipartiter Graphen.



http://www.db-thueringen.de/servlets/DocumentServlet?id=14685
Aumüller, Martin; Dietzfelbinger, Martin; Dietzfelbinger, Martin *1956-*; Rink, Michael
Experimental variations of a theoretically good retrieval data structure. - In: Algorithms - ESA 2009, (2009), S. 742-751

A retrieval data structure implements a mapping from a set S of n keys to range R={0,1}^r , e.g. given by a list of key-value pairs (x,v)?S×R, but an element outside S may be mapped to any value. Asymptotically, minimal perfect hashing allows to build such a data structure that needs n*log_2(e)+nr+o(n) bits of memory and has constant evaluation time. Recently, data structures based on other approaches have been proposed that have linear construction time, constant evaluation time and space consumption O(nr) bits or even (1+?)nr bits for arbitrary ?>0. This paper explores the practicability of one such theoretically very good proposal, bridging a gap between theory and real data structures.



http://dx.doi.org/10.1007/978-3-642-04128-0_66
Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martin
Hash, displace, and compress. - In: Algorithms - ESA 2009, (2009), S. 682-693

A hash function h, i.e., a function from the set U of all keys to the range range [m]={0,...,m-1} is called a perfect hash function (PHF) for a subset S?U of size n?m if h is 1-1 on S. The important performance parameters of a PHF are representation size, evaluation time and construction time. In this paper, we present an algorithm that permits to obtain PHFs with expected representation size very close to optimal while retaining O(n) expected construction time and O(1) evaluation time in the worst case. For example in the case m=1.23n we obtain a PHF that uses space 1.4 bits per key, and for m=1.01n we obtain space 1.98 bits per key, which was not achievable with previously known methods. Our algorithm is inspired by several known algorithms; the main new feature is that we combine a modification of Pagh's hash-and-displace&hardcy; approach with data compression on a sequence of hash function indices. Our algorithm can also be used for k-perfect hashing, where at most k keys may be mapped to the same value.



http://dx.doi.org/10.1007/978-3-642-04128-0_61
Dietzfelbinger, Martin; Edelkamp, Stefan
Perfect hashing for state spaces in BDD representation. - In: KI 2009: advances in artificial intelligence, (2009), S. 33-40

http://dx.doi.org/10.1007/978-3-642-04617-9_5
Dietzfelbinger, Martin; Wölfel, Philipp;
Brief announcement: tight lower bounds for greedy routing in uniform small world rings. - In: Proceedings of the 2009 ACM Symposium on Principles of Distributed Computing, (2009), S. 300-301

Motivated by Kleinberg's Small World Graph model and packet routing strategies in peer-to-peer networks, greedy routing algorithms on augmented networks have been investigated thoroughly. We prove tight lower bounds for one- and two-sided greedy routing on augmented rings.



Dietzfelbinger, Martin; Wölfel, Philipp;
Tight lower bounds for greedy routing in uniform small world rings. - In: Proceedings of the 2009 ACM International Symposium on Theory of Computing, (2009), S. 591-600

We consider augmented ring-based networks with vertices 0,...,n-1, where each vertex is connected to its left and right neighbor and possibly to some further vertices (called long range contacts). The outgoing edges of a vertex v are obtained by choosing a subset D of {1,2,...n-1}, with 1, n-1 in D, at random according to a probability distribution mu on all such D and then for each i in D connecting v to (v+i) mod n by a unidirectional link. The choices for different v are done independently and uniformly in the sense that the same distribution mu is used for all v. The expected number of long range contacts is l=E(|D|)-2. Motivated by Kleinberg's (2000) Small World Graph model and packet routing strategies for peer-to-peer networks, the greedy routing algorithm on augmented rings, where a packet sitting in a node v is routed to the neighbor of v closest to the destination of the package, has been investigated thoroughly, both for the "one-sided case", where packets can travel only in one direction, and the "two-sided case", where there is no such restriction. In this paper, for both the one-sided and the two-sided case and for an arbitrary distribution mu, we prove a lower bound of Omega((log n)2/l) on the expected number of hops that are needed by the greedy strategy to route a package between two randomly chosen vertices on the ring. This bound is tight for Omega(1)<=l=O(log n).



Dietzfelbinger, Martin; Rink, Michael
Applications of a splitting trick. - In: Automata, languages and programming, (2009), S. 354-365

We study applications of a simple method for circumventing the "full randomness assumption" when building a hashing-based data structure for a set S of keys. The general approach is to "split" S into "pieces" S_i , by a splitting hash function. On a piece S_i, a method or data structure for generating full randomness is used that uses more space than |S_i|. Under certain circumstances, this data structure can be "shared" among the constructions for the pieces S_i , which leads to a tighter overall space bound. The method was introduced in the context of cuckoo hashing and its variants, but it seems to have wider applicability. To demonstrate its power and some subtleties, we study three new applications, improving previous constructions: (i) Space-efficient simulation of full randomness on S (following work by Pagh and Pagh (2003/08) and Dietzfelbinger and Woelfel (2003)); (ii) Construction of highly independent functions in the style of Siegel (1989/2004); (iii) One-probe schemes as in work by Buhrman, Miltersen, Radhakrishnan, and Venkatesh (2000/02) and Pagh and Pagh (2002).



http://dx.doi.org/10.1007/978-3-642-02927-1_30
Schellbach, Ulf;
On risks of using a high performance hashing scheme with common universal classes, 2009. - Online-Ressource (PDF-Datei: 81 S., 868 KB) : Ilmenau, Techn. Univ., Diss., 2009
Parallel als Druckausg. erschienen

Der Beitrag dieser Dissertation ist die mathematische Analyse eines Hashing-Verfahrens namens Cuckoo Hashing in Kombination mit einfachen, effizient auswertbaren Funktionen zweier Hashklassen, die wir die multiplikative Klasse bzw. die lineare Klasse nennen. Cuckoo Hashing hat die deutliche Tendenz, mit Funktionen dieser beiden Klassen schlecht zu funktionieren. Um dies zu beweisen, untersuchen wir den Einfluss der inneren Struktur solcher Funktionen auf das Verhalten des Cuckoo-Verfahrens, wenn der Versuch unternommen wird, eine Schlüsselmenge S in anfangs leere Tabellen einzufügen. Cuckoo Hashing verwendet zwei Tabellen der jeweiligen Größe m. Man weiß, dass die Einfügung einer beliebigen Menge S der Größe n = (1 - delta)m für eine beliebige Konstante delta (0,1) (was einen Lastfaktor n/(2m) von bis zu 1/2 liefert) mit Wahrscheinlichkeit O(1/n) fehlschlägt, falls die Hashfunktionen aus einer Omega(log n)-fach unabhängigen Klasse gewählt werden. Damit läßt sich beweisen, dass die erwarteten amortisierten Kosten einer einzelnen Einfügung konstant sind. Demgegenüber beweisen wir untere Schranken der folgenden Art: Wenn S eine uniform zufällig gewählte Schlüsselmenge der Größe m/2$ ist (Lastfaktor 1/4 (!)), dann schlägt die Einfügung von S mit großer Wahrscheinlichkeit Omega(1), oder sogar 1 - o(1), fehl, falls Funktionen der multiplikativen bzw. der linearen Klasse gewählt werden. Damit beantworten wir eine Frage, die bereits von Pagh und Rodler aufgeworfen wurde, als sie mit Hilfe von Experimenten feststellten, dass es riskant ist, Cuckoo Hashing mit Funktionen der multiplikativen Klasse zu kombinieren. Unsere Resultate zeigen, dass paarweise Unabhängigkeit und uniforme Verteilung der Hashwerte keine Garantie dafür ist, dass Cuckoo Hashing gut funktioniert. Zudem machen unsere Ergebnisse exemplarisch deutlich, dass bei der Anwendung eines kürzlich veröffentlichten Resultates von Mitzenmacher und Vadhan, welches besagt, dass selbst Funktionen aus einfachen, schwach universellen Klassen unter gewissen Bedingungen zu hochgradig unabhängigen und fast uniform zufälligen Werten führen können, Vorsicht geboten ist: Falls dessen Bedingungen nicht erfüllt sind, gilt es unter Umständen nicht.



http://www.db-thueringen.de/servlets/DocumentServlet?id=14080
Dietzfelbinger, Martin; Schellbach, Ulf
On risks of using cuckoo hashing with simple universal hash classes. - In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, ISBN 978-0-89871-680-1, (2009), S. 795-804

Draque Penso, Lucia; Rautenbach, Dieter; Rautenbach, Dieter *1972-*; Szwarcfiter, Jayme Luiz
Connectivity and diameter in distance graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 17 S., 177 KB). - (Preprint ; M09,12)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12976
Draque Penso, Lucia; Rautenbach, Dieter; Rautenbach, Dieter *1972-*; Szwarcfiter, Jayme Luiz
Long cycles and paths in distance graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 12 S., 242 KB). - (Preprint ; M09,11)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12973
Dietzfelbinger, Martin; Schellbach, Ulf
Weaknesses of Cuckoo hashing with a simple universal hash class: the case of large universes. - In: SOFSEM 2009: theory and practice of computer science, (2009), S. 217-228

http://dx.doi.org/10.1007/978-3-540-95891-8_22
Dietzfelbinger, Martin; Rowe, Jonathan E.; Wegener, Ingo; Wölfel, Philipp
Precision, local search and unimodal functions. - In: GECCO 2008, (2008), S. 771-778

We investigate the effects of precision on the efficiency of various local search algorithms on 1-D unimodal functions. We present a (1+1)-EA with adaptive step size which finds the optimum in O(log n) steps, where n is the number of points used. We then consider binary and Gray representations with single bit mutations. The standard binary method does not guarantee locating the optimum, whereas using Gray code does so in O((log n)^2) steps. A (1+1)-EA with a fixed mutation probability distribution is then presented which also runs in O((log n)^2). Moreover, a recent result shows that this is optimal (up to some constant scaling factor), in that there exist unimodal functions for which a lower bound of Omega((log n)^2) holds regardless of the choice of mutation distribution. Finally, we show that it is not possible for a black box algorithms to efficiently optimise unimodal functions for two or more dimensions (in terms of the precision used).



Dietzfelbinger, Martin; Rowe, Jonathan E.; Wegener, Ingo; Wölfel, Philipp
Tight bounds for blind search on the integers. - Ilmenau : Univ.-Bibliothek. - Online-Ressource (PDF-Datei: 12 S., 669,8 KB)Onlineausg.: Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science : STACS 2008, 21 - 23 February, Bordeaux, France / Susanne Albers; Pascal Weil (eds.). - Wadern : IBFI Schloss Dagstuhl, 2008. - ISBN 978-3-939897-06-4, S. 241-252

We analyze a simple random process in which a token is moved in the interval $A={0,dots,n$: Fix a probability distribution $mu$ over ${1,dots,n$. Initially, the token is placed in a random position in $A$. In round $t$, a random value $d$ is chosen according to $mu$. If the token is in position $ageq d$, then it is moved to position $a-d$. Otherwise it stays put. Let $T$ be the number of rounds until the token reaches position 0. We show tight bounds for the expectation of $T$ for the optimal distribution $mu$. More precisely, we show that $min_mu{E_mu(T)=Thetaleft((log n)^2 ight)$. For the proof, a novel potential function argument is introduced. The research is motivated by the problem of approximating the minimum of a continuous function over $[0,1]$ with a "blind'' optimization strategy.



http://nbn-resolving.de/urn:nbn:de:0030-drops-13486
Dietzfelbinger, Martin; Pagh, Rasmus
Succinct data structures for retrieval and approximate membership (extended abstract). - In: , (2008), S. 385-396

The retrieval problem is the problem of associating data with keys in a set. Formally, the data structure must store a function f : U -> {0,1}^r that has specified values on the elements of a given subset S of U, |S|=n, but may have any value on elements outside S. All known methods (e.g. those based on perfect hash functions), induce a space overhead of (n) bits over the optimum, regardless of the evaluation time. - We show that for any k query time O(k) can be achieved using space that is within a factor 1+exp(-k) of optimal, asymptotically for large n. The time to construct the data structure is O(n), expected. If we allow logarithmic evaluation time, the additive overhead can be reduced to O(log log n) bits whp. - Further, we note a general reduction that transfers the results on retrieval into analogous results on approximate membership, a problem traditionally addressed using Bloom filters. This makes it possible to get arbitrarily close to the lower bound. The evaluation procedures of our data structures are extremely simple. For the results stated above we assume free access to fully random hash functions. This assumption can be justified using extra space o(n) to simulate full randomness on a RAM.



http://dx.doi.org/10.1007/978-3-540-70575-8_32
Dietzfelbinger, Martin; Hühne, Martin; Weidling, Christoph
A dictionary implementation based on dynamic perfect hashing. - In: Journal of experimental algorithmics, ISSN 1084-6654, Bd. 12.2008, 1.11, insges. 25 S.

We describe experimental results on an implementation of a dynamic dictionary. The basis of our implementation is dynamic perfect hashing&hardcy; as described by Dietzfelbinger et al. (SIAM J. Computing 23, 1994, pp. 738--761), an extension of the storage scheme proposed by Fredman et al. (J. ACM 31, 1984, pp. 538--544). At the top level, a hash function is used to partition the keys to be stored into several sets. On the second level, there is a perfect hash function for each of these sets. This technique guarantees O(1) worst-case time for lookup and expected O(1) amortized time for insertion and deletion, while only linear space is required. We study the practical performance of dynamic perfect hashing and describe improvements of the basic scheme. The focus is on the choice of the hash function (both for integer and string keys), on the efficiency of rehashing, on the handling of small buckets, and on the space requirements of the implementation.



http://doi.acm.org/10.1145/1370596.1370602
Dietzfelbinger, Martin;
Fingerprinting. - In: Taschenbuch der Algorithmen, (2008), S. 193-204

Vöcking, Berthold; Alt, Helmut; Dietzfelbinger, Martin; Reischuk, Rüdiger; Scheideler, Christian; Vollmer, Heribert; Wagner, Dorothea
Taschenbuch der Algorithmen. - Berlin, Heidelberg : Springer-Verlag, 2008. - Online-Ressource (X, 448 S.). - (eXamen.press) ISBN 978-3-540-76394-9

Heriber



http://dx.doi.org/10.1007/978-3-540-76394-9
Fugmann, Marcel;
Theoretische und praktische Untersuchungen von Verfahren zur Konstruktion extrem platzeffizienter perfekter Hash-Funktionen. - 68 S. Ilmenau : Techn. Univ., Diplomarbeit, 2008

Chazelle et al. und Botelho et al. stellten ein perfekte Hash-Funktion vor, die sich durch einen extrem geringen Platzbedarf von nur zwei Bits pro Schlüssel auszeichnet. Dabei kommen mehrere Einzelfunktionen zum Einsatz. Für jeden Schlüssel wird über einen geeigneten Algorithmus jeweils die relevante Einzelfunktion ausgewählt, über die der Schlüssel abgebildet wird. Zur Konstruktion der Gesamtfunktion werden Hypergraphen eingesetzt, um die Zuordnung der Schlüssel zu den Einzelfunktionen zu finden. Anschließend genügt es, die Knotenfärbungen des Hypergraphen zu speichern, um die Gesamtfunktion rekonstruierbar zu gestalten. Durch den Einsatz der Hypergraphen kann die Gesamtfunktion in linearer Zeit gefunden werden und die Konstruktion benötigt nur linearen Platz. Im Rahmen der Arbeit wurde dieses Verfahren untersucht, implementiert und das Verhalten bei verschiedenen eingesetzten Einzelfunktionen getestet.



Dietzfelbinger, Martin
Tight bounds for blind search on the integers. - Dortmund : TU, Secretary of the SFB 531, 2008. - 13 Bl.. - (Reihe Computational Intelligence ; 240)
Dietzfelbinger, Martin
Probabilistic methods in the design and analysis of algorithms : 07391 abstracts collection ; Dagstuhl seminar. - [Wadern] : [Internat. Begegnungs- und Forschungszentrum für Informatik], 2007. - Online-Ressource (PDF-Datei: 18 S., 240 KB). - (Dagstuhl seminar proceedings ; 07391)
http://d-nb.info/991699130/34
Eisterlehner, Folke;
Statische Analyse der Komplexität von Programmen. - 132 S. Ilmenau : Techn. Univ., Diplomarbeit, 2007

Basierend auf der Arbeit [TCS '04] von Kristiansen und Niggl stellen Niggl und Wunderlich in ihrer Arbeit [SIAM '06] eine Methode M zur statischen Analyse des Ressourcenbedarfs von imperativen Programmen vor, die aus beliebigen Basisanweisungen (auf beliebigen Datenstrukturen) mittels Sequenzierung, Konditionalen und FOR-Schleifen gebildet werden. Diese Methode ermöglicht unter anderem die Zertifizierung von "polynomiell größenbeschränkten" Programmen; dies sind solche imperative Programme P mit Variablen X_1, ... , X_n, für welche mit i=1,..., n gilt: Nach der Ausführung von P ist die Größe des in X_i gespeicherten Datenobjekts beschränkt durch ein Polynom in den Größen der initialen Belegung von X_1,...,X_n. Ferner wurde gezeigt, dass die zertifizierten "String-Programme" genau die polynomialzeitberechenbaren Funktionen (FP) berechnen. Diese Diplomarbeit untersucht nun Modifikationen an M sowie an der in Mehlers Diplomarbeit [TU-Ilmenau '05] vorgestellten Methode M', eine um den "additiven Fall" verallgemeinerte Verfeinerung von M, mit dem Ziel, die Klasse der zertifierten Progamme gegenüber M und M' signifikant zu erweitern. Ausgangspunkt der Überlegungen ist die Arbeit [CiE '05] von Kristiansen und Jones. Dort wird eine weitere Zertifizierungsmethode vorgestellt, welche insbesondere wachstumsneutrale zyklische Zuweisungsfolgen zulässt, die sowohl eine Zertifizierung durch M, als auch durch M' verhindern. In dieser Diplomarbeit wird gezeigt, dass eine verfeinerte Analyse des potentiellen gegenseitigen Einflusses von Variablen erlaubt, Programme mit wachstumsneutralgen Zuweisungszyklen durch eine Modifikation M'' von M zu zertifizieren. Ferner wird gezeigt, wie sich die duch M' realisierten Modifikationen in die verfeinerte Analyse integrieren lassen. Grundlegend für die verfeinerte Analyse ist eine genaue Untersuchung und Charakterisierung des M zugrundeliegenden Matrizenkalküls. Als Ergebnis der genauen Charakterisierung der verwendeten Operatoren wird erstmalig ein effizienter Algortihmus, Closure, vorgestellt, der aus einem gegebenen Zertifikat Y für ein Programm in n Variablen die j-te Spalte der transitiven Hülle von Y in Zeit O(n&dzcy; log n) und mit Platzbedarf O(nø) berechnet. Closure basiert wesentlich auf teilweise neuen graphentheoretischen Analysen und liefert erstmalig den Nachweis, dass sowohl M und M' als auch M'' effiziente Zertifizierungsverfahren darstellen.



Dietzfelbinger, Martin;
Design strategies for minimal perfect hash functions. - In: Stochastic algorithms: foundations and applications, (2007), S. 2-17

http://dx.doi.org/10.1007/978-3-540-74871-7
Rink, Michael;
Untersuchungen zu neueren Bloom-Filter-Varianten und d-left-Hashing. - 206 S. Ilmenau : Techn. Univ., Diplomarbeit, 2007

Der standard Bloom-Filter, 1970 von Burton H. Bloom entworfen, ist eine einfache probabilistische Datenstruktur zur Berechnung der charakteristischen Funktion einer Menge. Er erlaubt eine kleine Falsch-Positiv-Rate, ermöglicht aber eine hohe Speichereffizienz. In den letzten Jahren haben Bloom-Filter stark an Popularität gewonnen und die Original-Datenstruktur wurde auf vielfältige Weise angepasst und verändert. Die Varianten lassen sich in drei Kategorien unterteilen: Bloom-Filter für Mengen, Counting-Bloom-Filter für Multimengen und Bloomier-Filter für Wörterbücher. Diese Diplomarbeit behandelt neuere Bloom-Filter-Varianten mit Schwerpunkt auf der Analyse und dem Vergleich ihrer Fehlerwahrscheinlichkeiten. Dafür wurde die relevante Literatur aufgearbeitet und einer einheitlichen mathematischen Darstellung unterzogen. Vorteile einzelner Varianten stellten sich als stark anwendungsspezifisch heraus. Beispielsweise erreichten Datenstrukturen die auf Fingerprints und der d-left-Hashing-Technik basieren erst ab einer bestimmten Größe eine kleinere Falsch-Positiv-Rate als die Standard-Konstruktion.



Dietzfelbinger, Martin; Wunderlich, Henning
A characterization of average case communication complexity. - In: Information processing letters, ISSN 1872-6119, Bd. 101 (2007), 6, S. 245-249

It is well known that the average case deterministic communication complexity is bounded below by an entropic quantity, which one would now call deterministic information complexity. In this paper we show a corresponding upper bound. We also improve known lower bounds for the public coin Las Vegas communication complexity by a constant factor.



http://dx.doi.org/10.1016/j.ipl.2006.10.006
Dietzfelbinger, Martin; Weidling, Christoph
Balanced allocation and dictionaries with tightly packed constant size bins. - In: Theoretical computer science, Bd. 380 (2007), 1/2, S. 47-68

We study a particular aspect of the balanced allocation paradigm (also known as the "two-choices paradigm"): constant sized bins, packed as tightly as possible. Let d >= 1 be fixed, and assume there are m bins of capacity d each. To each of n <= d*m$ balls two possible bins are assigned at random. How close can dm/n = 1 + epsilon be to 1 so that with high probability each ball can be put into one of the two bins assigned to it, without any bin overflowing? We show that epsilon > (2/e)^(d-1) is sufficient. If a new ball arrives with two new randomly assigned bins, we wish to rearrange some of the balls already present in order to accommodate the new ball. We show that on average it takes constant time to rearrange the balls to achieve this, for epsilon > beta^d, for some constant beta < 1. An alternative way to describe the problem is in data structure language. Generalizing cuckoo hashing (Pagh and Rodler, 2004), we consider a hash table with m positions, each representing a bucket of capacity d >= 1. Keys are assigned to buckets by two fully random hash functions. How many keys can be placed in these bins, if key x may go to bin h_1(x) or to bin h_2(x)? We obtain an implementation of a dictionary that accommodates n keys in m = (1+epsilon)n/d buckets of size d = O(log(1/epsilon)), so that key x resides in bucket h_1(x) or h_2(x). For a lookup operation, only two hash functions have to be evaluated and two segments of d contiguous memory cells have to be inspected. If d >= 1 + 3.26 * ln(1/epsilon), a static arrangement exists with high probability. If d >= 16 * \ln(1/epsilon), a dynamic version of the dictionary exists so that the expected time for inserting a new key is log(1/epsilon)^(O(log log(1/epsilon))).



http://dx.doi.org/10.1016/j.tcs.2007.02.054
Senitsch, Stefan;
Ein kombinatorischer Beweis für das PCP-Theorem. - 85 S. Ilmenau : Techn. Univ., Diplomarbeit, 2007

Das PCP-Theorem ist eine Charakterisierung der Klasse NP über sogenannte randomisierte Turingmaschinen, Maschinen, in deren Berechnungen Zufallsexperimente durchgeführt werden. Mit Hilfe des PCP-Theorems war es möglich, Nichtapproximierbarkeitsergebnisse für viele NP-schwere Optimierungsprobleme zu beweisen, so dass es als einer der wichtigsten Sätze der Komplexitätstheorie in den letzten 20 Jahren gilt. Sein ursprünglicher Beweis durch Arora et al. Anfang der 90er Jahre galt insbesondere wegen seiner komplizierten algebraischen Berechnungen als sehr komplex und schwer lesbar. Das Ziel eines einfacheren Beweises erreichte Irit Dinur 2005 nach Meinung vieler Experten, indem sie einen rein kombinatorischen Beweis präsentierte. Ziel dieser Arbeit ist es, Dinurs Beweis so darzustellen, dass er auch für Nicht-Experten verständlich ist. Dabei werden neben dem eigentlichen Beweis auch umfangsreiche Voraussetzungen aus der Mathematik und theoretischen Informatik bereitgestellt.



Niggl, Karl-Heinz; Wunderlich, Henning
Certifying polynomial time and linear/polynomial space for imperative programs. - In: SIAM journal on computing, ISSN 1095-7111, Bd. 35 (2006), 5, S. 1122-1147

https://doi.org/10.1137/S0097539704445597
Wunderlich, Henning; Niggl, Karl-Heinz
Implicit characterizations of FPTIME and NC revisited. - In: 5th International Workshop on Proof, Computation, Complexity, (2006), S. 47-51

Eisterlehner, Folke; Niggl, Karl-Heinz
An alternative correctness proof of a certification method for FPTIME. - In: 5th International Workshop on Proof, Computation, Complexity, (2006), S. 18-19

Niggl, Karl-Heinz; Kahle, Reinhard; Elbl, Birgit
5th International Workshop on Proof, Computation, Complexity : PCC '06 ; Ilmenau, July 24 - 25, 2006. - Ilmenau : Univ.-Verl. Ilmenau, 2006. - Online-Ressource (PDF-Datei: 57 S., 412,3 KB)Parallel als Druckausg. erschienen

http://www.db-thueringen.de/servlets/DocumentServlet?id=6361
Mehler, Jan;
Zertifizierung von Laufzeit- und Speicherplatzbedarf für imperative Programme. - 134 S. Ilmenau : Techn. Univ., Diplomarbeit, 2006

Diese Diplomarbeit beschreibt ein Verfahren zur statischen Analyse des Ressourcenbedarfs von imperativen Programmen. Unter imperativen Programmen ist dabei eine um (fast) beliebige Datentypen und Basisanweisungen bereicherte Version von loop-Programmen zu verstehen. Einzige Anforderung an Datentypen ist, dass einer Variablen X dieses Datentyps eine natürliche "Größe" oder "Länge" |X| zugeordnet werden kann. Von einer Basisanweisung imp(P_1, ..., P_m) wird gefordert, dass die Größe jedes Ein-/Ausgabe-Parameters polynomiell beschränkt werden kann. Das heißt, dass für jeden Ein-/Ausgabe-Parameter P_i ein Polynom imp_|P_i|(p_1, ..., p_m) existiert, so dass die Größe des in P_i zurückgelieferten Wertes kleiner oder gleich imp_|P_i|(|P_1|, ..., |P_m) ist. Das formale Problem, das diese Arbeit näher betrachtet, besteht nun darin, zu einem gegebenem imperativen Programm alleine durch eine Analyse des Quellcodes zu entscheiden, ob alle auftretenden Variablen "polynomiell längenbeschränkt" sind. Das heißt es ist zu entscheiden, ob für jede Variable X_i eines Programms P, das die Variablen X_1, ..., X_n verwendet, ein Polynom p_{X_i}(x_1, ..., x_n) existiert, so dass gilt: {|X_1| = s_1, ..., |X_n| = s_n} P {|X_i| <= p_{X_i}(s_1, ..., s_n)} Es wird gezeigt, dass dieses Problem unentscheidbar ist. Trotz dieser Erkenntnis werden in dieser Arbeit mit M und M' zwei "Zertifizierer" für die polynomielle Längenbeschränktheit von imperativen Programm vorgestellt. Im Falle, dass ein Programm zertifiziert werden kann, sind M und M' zusätzlich dazu in der Lage, eine konkrete polynomielle Längenschranke anzugeben. Weiterhin werden mit allgemeinen Loop-Programmen, String-Programmen und Powerstring-Programmen drei imperative Programmiersprachen vorgestellt. Es wird gezeigt, dass die durch M bzw. M' zertifizierbaren allgemeinen Loop-Programme genau die Funktionen in FLINSPACE berechnen, die durch M bzw. M' zertifizierbaren String-Programme genau die Funktionen in FP berechnen und die durch M bzw. M' Powerstring-Programme genau die Funktionen in FPSPACE berechnen.



Dietzfelbinger, Martin; Tamaki, Hisao
On the probability of rendezvous in graphs. - In: Random structures & algorithms, ISSN 1098-2418, Bd. 26 (2005), 3, S. 266-288

In a simple graph G without isolated nodes the following random experiment is carried out: each node chooses one of its neighbors uniformly at random. We say a rendezvous occurs if there are adjacent nodes u and v such that u chooses v and v chooses u; the probability that this happens is denoted by s(G). Métivier, Saheb, and Zemmari [Randomized rendezvous, Algorithms, trees, combinatorics, and probabilities, Eds. G. Gardy and A. Mokkadem, Trends in Mathematics, 183-194. Birkhäuser, Boston, 2000.] asked whether it is true that s(G) s(Kn) for all n-node graphs G, where Kn is the complete graph on n nodes. We show that this is the case. Moreover, we show that evaluating s(G) for a given graph G is a #P-complete problem, even if only d-regular graphs are considered, for any d 5.



https://doi.org/10.1002/rsa.20032
Dietzfelbinger, Martin; Weidling, Christoph
Balanced allocation and dictionaries with tightly packed constant size bins. - In: Automata, languages and programming, (2005), S. 166-178

http://dx.doi.org/10.1007/11523468_14
Niggl, Karl-Heinz;
Control structures in programs and computational complexity. - In: Annals of pure and applied logic, ISSN 1873-2461, Bd. 133 (2005), 1/3, S. 247-273

http://dx.doi.org/10.1016/j.apal.2004.10.011
Dietzfelbinger, Martin;
Primality testing in polynomial time : from randomized algorithms to "PRIMES is in P". - Berlin : Springer, 2004. - Online-Ressource (X, 147p. Also available online). - (Lecture notes in computer science ; 3000) ISBN 978-3-540-25933-6

This book is devoted to algorithms for the venerable primality problem: Given a natural number n, decide whether it is prime or composite. The problem is basic in number theory, efficient algorithms that solve it, i.e., algorithms that run in a number of computational steps which is polynomial in the number of digits needed to write n, are important for theoretical computer science and for applications in algorithmics and cryptology. This book gives a self-contained account of theoretically and practically important efficient algorithms for the primality problem, covering the randomized algorithms by Solovay-Strassen and Miller-Rabin from the late 1970s as well as the recent deterministic algorithm of Agrawal, Kayal, and Saxena. The textbook is written for students of computer science, in particular for those with a special interest in cryptology, and students of mathematics, and it may be used as a supplement for courses or for self-study



http://dx.doi.org/10.1007/b12334
Kristiansen, Lars; Niggl, Karl-Heinz
On the computational complexity of imperative programming languages. - In: Theoretical computer science, Bd. 318 (2004), 1/2, S. 139-161

http://dx.doi.org/10.1016/j.tcs.2003.10.016
Dietzfelbinger, Martin;
Gossiping and broadcasting versus computing functions in networks. - In: Discrete applied mathematics, ISSN 1872-6771, Bd. 137 (2004), 2, S. 127-153

https://doi.org/10.1016/S0166-218X(03)00257-9
Weidling, Christoph;
Platzeffiziente Hashverfahren mit garantierter konstanter Zugriffszeit, 2004. - Online-Ressource (PDF-Datei: 136 S., 1336 KB) : Ilmenau, Techn. Univ., Diss., 2004
Parallel als Druckausg. erschienen

Wir stellen ein neues Verfahren zur Konstruktion einer minimalen perfekten Hashfunktion (MPHF) und ein neues cachefreundliches dynamisches Wörterbuch vor, beschreiben die neuen Verfahren algorithmisch und analysieren sie hinsichtlich Platzbedarf und Laufzeit. Für die Analyse nehmen wir an, dass die in den Verfahren benutzten Hashfunktionen volle Unabhängigkeit gewährleisten. Schließlich werden wir jeweils experimentelle Resultate angeben und interpretieren. Wir zeigen, dass man eine minimale perfekte Hashfunktion für n Schlüssel mit einem Platzbedarf von 0.93n Wörtern in erwarteter Zeit O(n) realisieren kann. Zur Auswertung der MPHF werden 2 Hashfunktionen berechnet und zwei Speicherzugriffe durchgeführt. Unser dynamisches Wörterbuch benötigt (1+epsilon)n Platz für ein beliebiges epsilon > 0. Bei der Suche müssen 2 Hashfunktionen ausgewertet und 2d Speicherzellen inspiziert werden, die in zwei zusammenhängenden Speicherbereichen liegen, wobei d >= 1+3.26 ln(1/epsilon). Wir können zeigen, dass für d >= 90.1 ln(1/epsilon) die erwartete Einfügezeit für einen neuen Schlüssel konstant ist. Am Ende werden wir zeigen, wie man dynamisches Hashing mit Zeichenketten cachefreundlich realisieren kann.



http://www.db-thueringen.de/servlets/DocumentServlet?id=2431
Kristiansen, Lars; Niggl, Karl-Heinz
The Garland measure and computational complexity of stack programs. - In: Electronic notes in theoretical computer science, ISSN 1571-0661, Bd. 90 (2003), S. 15-35

https://doi.org/10.1016/S1571-0661(03)00003-3
Dietzfelbinger, Martin; Naudts, Bart; Hoyweghen, Clarissa; Wegener, Ingo
The analysis of a recombinative hill-climber on H-IFF. - In: IEEE transactions on evolutionary computation, ISSN 1089-778X, Bd. 7 (2003), 5, S. 417-423

Dietzfelbinger, Martin; Wölfel, Philipp;
Almost random graphs with simple hash functions. - In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, (2003), S. 629-638

Dietzfelbinger, Martin; Tamaki, Hisao
On the probability of rendezvous in graphs. - Saarbrücken : Max-Planck-Inst. für Informatik, Bibliothek & Dokumentation, 2003. - 27 S. - (Forschungsberichte des Max-Planck-Instituts für Informatik ; 2003-1-006)
Dietzfelbinger, Martin; Wölfel, Philipp;
Almost random graphs with simple hash functions. - Saarbrücken : Max-Planck-Inst. für Informatik, Bibliothek & Dokumentation, 2003. - 20 S. - (Forschungsberichte des Max-Planck-Instituts für Informatik ; 2003-1-005)
Dietzfelbinger, Martin;
The probability of a rendezvous is minimal in complete graphs. - In: Algorithms and Computation, (2002), S. 55-66

http://dx.doi.org/10.1007/3-540-36136-7_6
Niggl, Karl-Heinz;
Control structures in programs and computational complexity. - 60 S. = 571,4 KB, Text : Ilmenau, Techn. Univ., Habil.-Schr., 2002
Digitalisat der Druckausg.

http://www.db-thueringen.de/servlets/DocumentServlet?id=3175
Dietzfelbinger, Martin
The analysis of a recombinative hill climber on HIFF. - Dortmund : Secretary of the SFB 531, 2002. - 6 Bl. - (Reihe computational intelligence ; 138)
Dietzfelbinger, Martin; Hagerup, Torben
Simple minimal perfect hashing in less space. - In: Algorithms — ESA 2001, (2001), S. 109-120

http://dx.doi.org/10.1007/3-540-44676-1_9
Dietzfelbinger, Martin; Gambin, Anna; Lasota, Sławomir
On different models for packet flow in multistage interconnection networks. - In: Fundamenta informaticae, ISSN 0169-2968, Bd. 46 (2001), 4, S. 287-314

Bellantoni, Stephen J.; Niggl, Karl-Heinz; Schwichtenberg, Helmut
Higher type recursion, ramification and polynomial time. - In: Annals of pure and applied logic, ISSN 1873-2461, Bd. 104 (2000), 1/3, S. 17-30

http://dx.doi.org/10.1016/S0168-0072(00)00006-3
Niggl, Karl-Heinz;
[Rezension von: Bellantoni, Stephen; Cook, Stephen, A new recursion-theoretic characterization of the polytime functions...]. - In: The bulletin of symbolic logic. - Cambridge : Cambridge Univ. Press, ISSN 1079-8986, 3, S. 351-353
, Rezension von
Rezension von
Niggl, Karl-Heinz;
The mu-measure as a tool for classifying computational complexity. - In: Archive for mathematical logic, ISSN 0933-5846, Bd. 39 (2000), 7, S. 515-539

Bellantoni, Stephen J.; Niggl, Karl-Heinz
Ranking primitive recursions: the low Grzegorczyk classes revisited. - In: SIAM journal on computing, ISSN 1095-7111, Bd. 29 (1999), 2, S. 401-415

https://doi.org/10.1137/S009753979528175X
Niggl, Karl-Heinz;
M [omega] considered as a programming language. - In: Annals of pure and applied logic, ISSN 1873-2461, Bd. 99 (1999), 1/3, S. 73-92

http://dx.doi.org/10.1016/S0168-0072(99)80002-5
Alon, Noga; Dietzfelbinger, Martin; Miltersen, Peter Bro; Petrank, Erez; Tardos, Gábor
Linear hash functions. - In: Journal of the ACM, ISSN 1557-735X, Bd. 46 (1999), 5, S. 667-683

https://doi.org/10.1145/324133.324179