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


INHALTE

Veröffentlichungen

Hochschulbibliographie der TU Ilmenau (UB)

Anzahl der Treffer: 112
Erstellt: Thu, 21 Sep 2017 23:01:28 +0200 in 0.0154 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