http://www.tu-ilmenau.de

Logo TU Ilmenau


FG Komplexitätstheorie und Effiziente Algorithmen


Ansprechpartner

Univ.-Prof. Dr. Martin Dietzfelbinger

Fachgebietsleiter

Telefon +49 (0)3677 69 2656

E-Mail senden

Ihre Position

INHALTE

Veröffentlichungen

Hochschulbibliographie der TU Ilmenau (UB)

Anzahl der Treffer: 112
Erstellt: Sat, 18 Nov 2017 07:53:13 +0100 in 0.3677 sec


Aumüller, Martin; Dietzfelbinger, Martin; Heuberger, Clemens; Krenn, Daniel; Prodinger, Helmut
Counting zeros in random walks on the integers and analysis of optimal dual-pivot quicksort. - In: De.arxiv.org. - [S.l.] : Arxiv.org, (2016), insges. 13 S.
https://arxiv.org/abs/1602.04031
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.


http://www.gbv.de/dms/ilmenau/abs/873748816schla.txt
Aumüller, Martin; Dietzfelbinger, Martin; Klaue, Pascal
How good is Multi-Pivot Quicksort?. - In: ACM transactions on algorithms : TALG. - New York, NY, ISSN 15496333, Bd. 13Bd. 13 (2016), 1, Article no. 8, insges. 47 S.
http://dx.doi.org/10.1145/2963102
Mattern, Christopher
On statistical data compression. - Ilmenau : Universitätsbibliothek. - 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.


http://www.gbv.de/dms/ilmenau/abs/846375419frank.txt
Aumüller, Martin; Dietzfelbinger, Martin
Optimal partitioning for dual-pivot quicksort. - In: ACM transactions on algorithms : TALG. - New York, NY, ISSN 15496333, Bd. 12Bd. 12 (2016), 2, Article no. 18, insges. 36 S.
http://dx.doi.org/10.1145/2743020
Jaberi, Raed
Algorithms for computing the 2-vertex-connected components and the 2-blocks of directed graphs. - 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, ISSN 1290385X, 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.


http://dx.doi.org/10.1051/ita/2015001
Mattern, Christopher
On probability estimation by exponential smoothing . - In: 2015 Data Compression Conference (DCC 2015) : 7 - 9 April, 2015, Snowbird, Utah, USA. - Piscataway, NJ : IEEE / Data Compression Conference (Snowbird, Utah) : 2015.04-07-09. - Piscataway, NJ : IEEE, 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) : 7 - 9 April, 2015, Snowbird, Utah, USA. - Piscataway, NJ : IEEE / Data Compression Conference (Snowbird, Utah) : 2015.04-07-09., 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. - Online-Ressource (PDF-Datei: VIII, 235 S., 1,63 MB)
Ilmenau : Techn. Univ., Diss., 2015

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 : devoted to the rapid publication of short contributions to information processing. - Amsterdam [u.a.] : Elsevier, 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. - New York, NY : Springer, ISSN 14330490, Bd. 56 (2015), 4, S. 593-611
http://dx.doi.org/10.1007/s00224-014-9577-1
Rink, Michael
Thresholds for matchings in random bipartite graphs with applications to hashing-based data structures. - 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.


http://www.gbv.de/dms/ilmenau/abs/810605104knack.txt
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. - (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.


http://www.gbv.de/dms/ilmenau/abs/796314071pape.txt
Aumüller, Martin; Dietzfelbinger, Martin; Woelfel, Philipp
Explicit and efficient hash families suffice for cuckoo hashing with a stash. - In: Algorithmica : an international journal in computer science. - New York, NY : Springer, ISSN 14320541, 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 / Annual ACM-SIAM Symposium on Discrete Algorithms ; 25 (Portland, Or.) : 2014.01.05-07. : [Portland, Oregon, USA, January 5 - 7, 2014]. - New York, NY : Assoc. for Computing Machinery, ISBN 978-1-61197-338-9, (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.


http://www.gbv.de/dms/ilmenau/abs/787198404chemi.txt
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.


http://www.gbv.de/dms/ilmenau/abs/782294278hirte.txt
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.


http://www.gbv.de/dms/ilmenau/abs/780528867klaue.txt
Dietzfelbinger, Martin; Mehlhorn, Kurt; Sanders, Peter
Algorithmen und Datenstrukturen : die Grundwerkzeuge. - Berlin [u.a.] : Springer Vieweg. - XII, 380 S.. - (eXamen.press)
Korrigierte Übers. der engl. Ausg. (2008) von Kurt Mehlhorn und Peter Sanders. - Literaturverz. S. [351] - 362
http://www.gbv.de/dms/ilmenau/toc/618339744.PDF
Aumüller, Martin; Dietzfelbinger, Martin
Optimal partitioning for dual pivot quicksort. - In: Automata, languages, and programming : 40th international colloquium, ICALP 2013, Riga, Latvia, July 8 - 12, 2013 ; proceedings, part I. - Berlin [u.a.] : Springer / ICALP ; 40 (Riga) : 2013.07.08-12., ISBN 978-3-642-39206-1, (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 : 20 - 22 April 2013, Snowbird, Utah, USA. - Piscataway, NJ : IEEE / Data Compression Conference (Snowbird, Utah) : 2013.03.20-22., 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 : 39th International Conference on Current Trends in Theory and Practice of Computer Science, Špindleruv Mlýn, Czech Republic, January 26 - 31, 2013 ; proceedings. - Berlin [u.a.] : Springer / SOFSEM ; 39 (Špindleruv Mlýn) : 2013.01.26-31., ISBN 978-3-642-35843-2, (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.


http://www.gbv.de/dms/ilmenau/abs/73939326Xjaber.txt
Dietzfelbinger, Martin
On randomness in Hash functions. - In: 29th International Symposium on Theoretical Aspects of Computer Science : STACS '12, February 29th to March 3rd, 2012, Paris, France. - Saarbrücken/Wadern : Schloss Dagstuhl - Leibniz-Center for Informatics / STACS ; 29 (Paris) : 2012.02.29-03.03. - Saarbrücken/Wadern : Schloss Dagstuhl - Leibniz-Center for Informatics, ISBN 978-3-939897-35-4, (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 : 10 - 12 April 2012, Snowbird, Utah, USA ; proceedings. - Piscataway, NJ : IEEE / Data Compression Conference (Snowbird, Utah) : 2012.04.10-12., 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; Wölfel, Philipp
Explicit and efficient hash families suffice for cuckoo hashing with a stash. - In: Algorithms - ESA 2012 : 20th annual European symposium, Ljubljana, Slovenia, September 10 - 12, 2012 ; proceedings. - Berlin [u.a.] : Springer / ESA ; 20 (Ljubljana, Slovenia) : 2012.09.10-12., ISBN 978-3-642-33090-2, (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.


http://www.gbv.de/dms/ilmenau/abs/728858541rothe.txt
Dietzfelbinger, Martin; Rink, Michael
Towards optimal degree-distributions for left-perfect matchings in random bipartite graphs. - In: Computer science - theory and applications : 7th International Computer Science Symposium in Russia, CSR 2012, Nizhny Novgorod, Russia, July 3 - 7, 2012 ; proceedings. - Berlin [u.a.] : Springer / International Computer Science Symposium in Russia ; 7 (Nizhny Novgorod) : 2012.07.03-07., ISBN 978-3-642-30642-6, (2012), S. 99-111

http://dx.doi.org/10.1007/978-3-642-30642-6_11
Dietzfelbinger, Martin; Peilke, Hendrik; Rink, Michael
A more reliable greedy heuristic for maximum matchings in sparse random graphs. - In: Experimental algorithms : 11th international symposium, SEA 2012, Bordeaux, France, June 7 - 9, 2012 ; proceedings. - Berlin [u.a.] : Springer / SEA ; 11 (Bordeaux) : 2012.06.07-09., ISBN 978-3-642-30850-5, (2012), S. 148-159

http://dx.doi.org/10.1007/978-3-642-30850-5_14
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.


http://www.gbv.de/dms/ilmenau/abs/685166759beyer.txt
Mattern, Christopher
Combining non-stationary prediction, optimization and mixing for data compression. - In: First International Conference on Data Compression, Communications and Processing (CCP), 2011 : 21 - 24 June 2011, Palinuro, Cilento Coast, Italy. - Piscataway, NJ : IEEE / International Conference on Data Compression, Communications and Processing ; 1 (Palinuro) : 2011.06.21-24., 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 : an international journal. - New York, NY : Wiley-Interscience, ISSN 10970037, 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 : 19th annual European symposium, Saarbrücken, Germany, September 5 - 9, 2011 ; proceedings. - Berlin [u.a.] : Springer / ESA ; 19 (Saarbrücken) : 2011.09.05-09., ISBN 978-3-642-23719-5, (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.


http://www.gbv.de/dms/ilmenau/abs/667580549zapf.txt
Dietzfelbinger, Martin
Fingerprinting. - In: Algorithms unplugged : . - Berlin [u.a.] : Springer, ISBN 978-3-642-15327-3, (2011), S. 181-193

Dietzfelbinger, Martin; Rowe, Jonathan E.; Wegener, Ingo; Woelfel, Philipp
Precision, local search and unimodal functions. - In: Algorithmica : an international journal in computer science. - New York, NY : Springer, ISSN 14320541, 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
Algorithms unplugged. - Berlin [u.a.] : Springer. - X, 406 S.
Literaturangaben

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, communication 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://d-nb.info/1005009791/04
Ackermann, Heiner; Röglin, Heiko; Schellbach, Ulf; Schweer, Nils
Analysis of algorithms. - In: , ISBN 978-3-642-14866-8, (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 : Organ der Gesellschaft für Informatik e.V. - Berlin : Springer, ISSN 1432122X, 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 : 24th international symposium, DISC 2010, Cambridge, MA, USA, September 13 - 15, 2010 ; proceedings. - Berlin [u.a.] : Springer / DISC ; 24 (Cambridge, MA) : 2010.09.13-15., ISBN 978-3-642-15763-9, (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. - Berlin : Springer, ISSN 14320452, 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. - Amsterdam [u.a.] : Elsevier, 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 : 37th international colloquium, ICALP 2010, Bordeaux, France, July 6 - 10, 2010 ; proceedings, part I. - Berlin [u.a.] : Springer / ICALP ; 37 (Bordeaux) : 2010.07.06-10., ISBN 978-3-642-14165-2, (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 : CPC. - Cambridge : Cambridge Univ. Press, ISSN 14692163, Bd. 19 (2010), 5/6, S. 711-728
http://dx.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.


http://www.gbv.de/dms/ilmenau/abs/622447068aumue.txt
Draque Penso, Lucia; Rautenbach, Dieter; Szwarcfiter, Jayme Luiz
Cycles, paths, connectivity and diameter in distance graphs. - In: Graph theoretic concepts in computer science : 35th international workshop, WG 2009, Montpellier, France, June 24 - 26, 2009 ; revised papers. - Berlin [u.a.] : Springer / WG ; 35 (Montpellier) : 2009.06.24-26., ISBN 978-3-642-11409-0, (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. - [S.l.] : Elsevier Science, 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. - 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; Rink, Michael
Experimental variations of a theoretically good retrieval data structure. - In: Algorithms - ESA 2009 : 17th annual European symposium, Copenhagen, Denmark, September 7 - 9, 2009 ; proceedings. - Berlin [u.a.] : Springer / Annual European Symposium on Algorithms ; 17 (Copenhagen) : 2009.09.07-09., ISBN 978-3-642-04128-0, (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 : 17th annual European symposium, Copenhagen, Denmark, September 7 - 9, 2009 ; proceedings. - Berlin [u.a.] : Springer / Annual European Symposium on Algorithms ; 17 (Copenhagen) : 2009.09.07-09., ISBN 978-3-642-04128-0, (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 : 32nd Annual German Conference on AI, Paderborn, Germany, September 15 - 18, 2009 ; proceedings. - Berlin [u.a.] : Springer / KI ; 32 (Paderborn) : 2009.09.15-18., ISBN 978-3-642-04617-9, (2009), S. 33-40

http://dx.doi.org/10.1007/978-3-642-04617-9_5
Dietzfelbinger, Martin; Woelfel, Philipp
Brief announcement: tight lower bounds for greedy routing in uniform small world rings. - In: / ACM Symposium on Principles of Distributed Computing ; 28 (Calgary) : 2009.08.10-12. : ., ISBN 978-1-60558-396-9, (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; Woelfel, Philipp
Tight lower bounds for greedy routing in uniform small world rings. - In: / ACM International Symposium on Theory of Computing ; 41 (Bethesda, Md.) : 2009.05.31-06.02. : ., ISBN 978-1-60558-613-7, (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 : 36th international colloquium, ICALP 2009, Rhodes, Greece, July 5 - 12, 2009 ; proceedings, part I. - Berlin [u.a.] : Springer / ICALP ; 36 (Rhodes) : 2009.07.05-12., ISBN 978-3-642-02927-1, (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. - Online-Ressource (PDF-Datei: 81 S., 868 KB)
Ilmenau : Techn. Univ., Diss., 2009

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: / Annual ACM-SIAM Symposium on Discrete Algorithms ; 20 (New York) : 2009.01.04-06., ISBN 978-0-89871-680-1, (2009), S. 795-804

Draque Penso, Lucia; Rautenbach, Dieter; Szwarcfiter, Jayme Luiz
Connectivity and diameter in distance graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 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; Szwarcfiter, Jayme Luiz
Long cycles and paths in distance graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 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 : 35th Conference on Current Trends in Theory and Practice of Computer Science, Špindler&ring;uv Mly´n, Czech Republic, January 24 - 30, 2009 ; proceedings. - Berlin [u.a.] : Springer / SOFSEM ; 35 (Špindler&ring;uv Mly´n) : 2009.01.24-30., ISBN 978-3-540-95891-8, (2009), S. 217-228

http://dx.doi.org/10.1007/978-3-540-95891-8_22
Dietzfelbinger, Martin; Rowe, Jonathan E.; Wegener, Ingo; Woelfel, Philipp
Precision, local search and unimodal functions. - In: / GECCO ; 10 (Atlanta, Ga.) : 2008.07.12-16., ISBN 978-1-605-58131-6, (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; Woelfel, Philipp
Tight bounds for blind search on the integers. - 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: Automata, languages and programming ; Pt. 1. - Berlin [u.a.] : Springer / ICALP ; 35 (Reykjavik) : 2008.07.07-11., ISBN 978-3-540-70575-8, (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
Dasgupta, Sanjoy; Papadimitriou, Christos H.; Vazirani, Umesh Virkumar : Algorithms : Boston [u.a.], McGraw-Hill Higher Education, 2007. - In: Computer science review. - Amsterdam [u.a.] : Elsevier, ISSN 18767745, 2, S. 131-136
Rezension von
Rezension von : Algorithm design / Kleinberg, Jon. - Boston [u.a.] : Pearson, Addison-Wesley, 2006. - XXIII, 838 S.. - Literaturverz. S. [805] - 814
http://dx.doi.org/10.1016/j.cosrev.2008.03.001
Dietzfelbinger, Martin; Hühne, Martin; Weidling, Christoph
A dictionary implementation based on dynamic perfect hashing. - In: Journal of experimental algorithmics : JEA. - New York, NY : ACM, ISSN 10846654, Bd. 12Bd. 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: : ., ISBN 978-3-540-76393-2, (2008), S. 193-204

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.


http://www.gbv.de/dms/ilmenau/abs/566890496fugma.txt
Dietzfelbinger, Martin
Tight bounds for blind search on the integers. - Dortmund : TU, Secretary of the SFB 531. - 13 Bl.. - (Reihe Computational Intelligence. - 240)
Vöcking, Berthold; Alt, Helmut; Dietzfelbinger, Martin; Reischuk, Rüdiger; Scheideler, Christian; Vollmer, Heribert; Wagner, Dorothea
Taschenbuch der Algorithmen. - Berlin [u.a.] : Springer. - X, 448 S.. - (eXamen.press)
ISBN 3540763937 = 978-3-540-76393-2
Literaturangaben

Algorithmen sind genau definierte Handlungsvorschriften zur Lösung von Problemen in endlich vielen Schritten. Sie bestimmen in unserer heutigen von der Informatik bestimmten Welt zunehmend unser Leben. Das Buch geht auf das Informatikjahr 2006 zurück, wo im Internet wöchentlich ein Algorithmus mit dem Ziel präsentiert wurde, interessierten Laien und auch Schülern zu vermitteln, welche kreativen Ideen und Konzepte hinter Algorithmen stecken und welche Faszination von der Informatik ausgehen kann. Diese damals im Internet veröffentlichten 43 Algorithmen finden sich im vorliegenden Buch wieder, gründlich überarbeitet, teilweise erweitert und mit Beispielen versehen sowie mit Hinweisen auf weiterführende Literatur zu jedem Algorithmus. Der Leser erfährt viele interessante Details zum Suchen und Sortieren, zum Rechnen und Verschlüsseln, zum Planen und strategischen Handeln und zum Optimieren. - Ob der Leser wohl weiß, wie man ein Streichholzspiel gewinnt, lange Zahlen schneller als in der Schule multipliziert oder im Dunkeln aus einem Labyrinth entkommt? Nach Lektüre des Buches: ja. (2 S)


http://www.gbv.de/dms/bs/toc/559564864.pdf
Dietzfelbinger, Martin
Probabilistic methods in the design and analysis of algorithms : 07391 abstracts collection ; Dagstuhl seminar. - [Wadern] : [Internat. Begegnungs- und Forschungszentrum für Informatik]. - 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.


http://www.gbv.de/dms/ilmenau/abs/557351847eiste.txt
Dietzfelbinger, Martin
Design strategies for minimal perfect hash functions. - In: Stochastic algorithms: foundations and applications : 4th international symposium, SAGA 2007, Zurich, Switzerland, September 13 - 14, 2007 ; proceedings. - Berlin [u.a.] : Springer / SAGA ; 4 (Zurich) : 2007.09.13-14., ISBN 978-3-540-74871-7, (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.


http://www.gbv.de/dms/ilmenau/abs/550169911rink.txt
Dietzfelbinger, Martin; Wunderlich, Henning
A characterization of average case communication complexity. - In: Information processing letters : devoted to the rapid publication of short contributions to information processing. - Amsterdam [u.a.] : Elsevier, 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 : the journal of the EATCS. - Amsterdam [u.a.] : Elsevier, 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.


http://www.gbv.de/dms/ilmenau/abs/526281928senit.txt
Niggl, Karl-Heinz; Wunderlich, Henning
Certifying polynomial time and linear/polynomial space for imperative programs. - In: SIAM journal on computing : a publication of the Society for Industrial and Applied Mathematics. - Philadelphia, Pa : SIAM, ISSN 10957111, Bd. 35 (2006), 5, S. 1122-1147
http://dx.doi.org/10.1137/S0097539704445597
Wunderlich, Henning; Niggl, Karl-Heinz
Implicit characterizations of FPTIME and NC revisited. - In: / International Workshop on Proof, Computation, Complexity ; 5 (Ilmenau) : 2006.07.24-25. : ., ISBN 978-3-939473-01-5, (2006), S. 47-51

Eisterlehner, Folke; Niggl, Karl-Heinz
An alternative correctness proof of a certification method for FPTIME. - In: / International Workshop on Proof, Computation, Complexity ; 5 (Ilmenau) : 2006.07.24-25. : ., ISBN 978-3-939473-01-5, (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. - Online-Ressource (PDF-Datei: 57 S., 412,3 KB)
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.


http://www.gbv.de/dms/ilmenau/abs/51087116Xmehle.txt
Dietzfelbinger, Martin; Tamaki, Hisao
On the probability of rendezvous in graphs. - In: Random structures & algorithms. - New York, NY [u.a.] : Wiley, ISSN 10982418, 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.


http://dx.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 : 32nd international colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005 ; proceedings. - Berlin [u.a.] : Springer / ICALP 2005 ; 32 (Lisbon) : 2005.07.11-15., ISBN 978-3-540-27580-0, (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. - Amsterdam [u.a.] : Elsevier, ISSN 18732461, 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. - Online-Ressource (X, 147p. Also available online). - (Lecture notes in computer science. - 3000)

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://d-nb.info/968515630/04
Kristiansen, Lars; Niggl, Karl-Heinz
On the computational complexity of imperative programming languages. - In: Theoretical computer science : the journal of the EATCS. - Amsterdam [u.a.] : Elsevier, 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. - [S.l.] : Elsevier, Bd. 137 (2004), 2, S. 127-153
http://dx.doi.org/10.1016/S0166-218X(03)00257-9
Weidling, Christoph
Platzeffiziente Hashverfahren mit garantierter konstanter Zugriffszeit. - Online-Ressource (PDF-Datei: 136 S., 1336 KB)
Ilmenau : Techn. Univ., Diss., 2004

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 : ENTCS. - Amsterdam [u.a.] : Elsevier Science, ISSN 15710661, Bd. 90 (2003), S. 15-35
http://dx.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 computationIEEE transactions on evolutionary computation. - New York, NY : IEEE : . - New York, NY : IEEE, ISSN 1089778X, Bd. 7 (2003), 5, S. 417-423
Dietzfelbinger, Martin; Woelfel, Philipp
Almost random graphs with simple hash functions. - In: / Annual ACM Symposium on Theory of Computing ; 35 (San Diego, Calif.) : 2003.06.09-11., (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. - 27 S. - (Forschungsberichte des Max-Planck-Instituts für Informatik. - 2003-1-006)
Dietzfelbinger, Martin; Woelfel, Philipp
Almost random graphs with simple hash functions. - Saarbrücken : Max-Planck-Inst. für Informatik, Bibliothek & Dokumentation. - 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 : 13th international symposium ; proceedings. - Berlin [u.a.] : Springer / ISAAC 2002 ; 13 (Vancouver) : 2002.11.21-23., (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. - 6 Bl. - (Reihe computational intelligence. - 138)
Dietzfelbinger, Martin; Hagerup, Torben
Simple minimal perfect hashing in less space. - In: Algorithms - ESA 2001 : 9th Annual European Symposium, Århus, Denmark, August 28 - 31, 2001 ; proceedings. - Berlin : Springer / ESA ; 9 (Århus) : 2001.08.28-31., ISBN 978-3-540-44676-7, (2001), S. 109-120

http://dx.doi.org/10.1007/3-540-44676-1_9
Dietzfelbinger, Martin; Gambin, Anna; Lasota, S&lstrok;awomir
On different models for packet flow in multistage interconnection networks. - In: Fundamenta informaticaeFundamenta informaticae. - Amsterdam [u.a.] : IOS Press : . - Amsterdam [u.a.] : IOS Press, ISSN 01692968, 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. - Amsterdam [u.a.] : Elsevier, ISSN 18732461, Bd. 104 (2000), 1/3, S. 17-30
http://dx.doi.org/10.1016/S0168-0072(00)00006-3
Niggl, Karl-Heinz
Bellantoni, Stephen; Cook, Stephen : A new recursion-theoretic characterization of the polytime functions : Computational complexity, vol. 2 (1992), S. 97-110. - In: The bulletin of symbolic logic. - Cambridge : Cambridge Univ. Press, ISSN 10798986, 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 - Berlin : Springer, ISSN 09335846, 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 : a publication of the Society for Industrial and Applied Mathematics. - Philadelphia, Pa : SIAM, ISSN 10957111, Bd. 29 (1999), 2, S. 401-415
http://dx.doi.org/10.1137/S009753979528175X
Niggl, Karl-Heinz
M [omega] considered as a programming language. - In: Annals of pure and applied logic. - Amsterdam [u.a.] : Elsevier, ISSN 18732461, 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 : JACM. - New York, NY : ACM, ISSN 1557735X, Bd. 46 (1999), 5, S. 667-683
http://doi.acm.org/10.1145/324133.324179