Literature list from the university bibliography

Results: 144
Created on: Wed, 27 Mar 2024 23:06:06 +0100 in 0.0370 sec


Dietzfelbinger, Martin; Goerdt, Andreas; Mitzenmacher, Michael; Montanari, Andrea; Pagh, Rasmus; Rink, Michael
Tight thresholds for cuckoo hashing via XORSAT. - In: Automata, languages and programming, (2010), S. 213-225

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

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

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



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

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



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

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

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



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

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



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

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



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

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



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

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



http://dx.doi.org/10.1007/978-3-642-04128-0_66