Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26584
Titel: Matrix rounding, evolutionary algorithms, and hole detection
Verfasser: Klein, Christian
Sprache: Englisch
Erscheinungsjahr: 2013
SWD-Schlagwörter: Informatik
Evolutionärer Algorithmus
Algorithmische Geometrie
Rundung
Freie Schlagwörter: matrix rounding
evolutionary algorithms
hole detection
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: In this thesis we study three different topics from the field of algorithms and data structures. First, we investigate a problem from statistics. We give two randomised algorithms that can round matrices of fractional values to integer-valued matrices. These matrices will exhibit only small rounding errors for sums of initial row or column entries. Both algorithms also round each entry up with probability equal to its fractional value. We give a derandomisation of both algorithms. Next, we consider the analysis of evolutionary algorithms (EAs). First, we analyse an EA for the Single Source Shortest Path problem. We give tight upper and lower bounds on the optimisation time of the EA. For this, we develop some new techniques for such analyses. We also analyse an EA for the All-Pairs Shortest Path problem. We show that adding crossover to this algorithm provably decreases its optimisation time. This is the first time that the usefulness of crossover has been shown for a non-constructed combinatorial problem. Finally, we examine how to retrieve the implicit geometric information hidden in the communications graph of a wireless sensor network. We give an algorithm that is able to identify wireless nodes close to a hole in this network based on the connectivity information alone. If the input fulfils several preconditions, then the algorithm finds a node near each boundary point and never misclassifies a node.
Diese Dissertation befasst sich mit drei Bereichen aus dem Gebiet der Algorithmen und Datenstrukturen. Zuerst betrachten wir ein Problem aus der Statistik. Wir präsentieren zwei randomisierte Algorithmen, die Matrizen von Kommazahlen in ganzzahlige Matrizen runden. Die berechneten Matrizen haben einen kleinen Rundungsfehler in allen Summen zusammenhängender Zeilen- oder Spaltenelemente. Außerdem ist die Wahrscheinlichkeit, dass eine Zahl aufgerundet wird, gleich ihrem Nachkommawert. Für beide Algorithmen zeigen wir derandomisierte Varianten. Dann beschäftigen wir uns mit der Analyse Evolutionärer Algorithmen (EAs). Zuerst analysieren wir einen EA für das Single Source Shortest Path Problem. Wir zeigen scharfe obere und untere Schranken für die Optimierungszeit dieses EAs. Dazu entwickeln wir neue Techniken für solche Analysen. Außerdem untersuchen wir einen EA für das All-Pairs Shortest Path Problem. Wir zeigen, dass Rekombination die Optimierungszeit dieses EAs beweisbar beschleunigt. Dies ist das erste kombinatorische Problem, für das der Nutzen von Rekombination gezeigt werden konnte. Abschließend untersuchen wir, wie man implizite geometrische Informationen im Kommunikationsgraphen eines Sensornetzes finden kann. Wir entwickeln einen Algorithmus, der Knoten nahe eines Loches im Netzwerk anhand der Konnektivitätsinformation identifizieren kann. Unter gewissen Bedingungen findet der Algorithmus einen Knoten nahe aller Randpunkte und markiert auch nur solche Knoten.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-59164
hdl:20.500.11880/26640
http://dx.doi.org/10.22028/D291-26584
Erstgutachter: Doerr, Benjamin
Tag der mündlichen Prüfung: 23-Jun-2014
SciDok-Publikation: 4-Dez-2014
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
thesis.pdf1 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.