Die Arbeit widmet sich der Rekonstruktion von Polygonzügen aus 2D-Punktwolkendaten. Die Daten wurden mittels Laser-Scannern erhoben und bilden Grundrisse von historischer Architektur ab. Die Arbeit beleuchtet die Arbeitsfähigkeit von GPU-parallelisierten genetischen Algorithmen, bei dem Versuch aus diesen Daten Polygone und Streckenzüge zu erheben die zu den ursprünglichen Daten kongruent sind.:1 Introduction 5 1.1 Point Cloud Reconstruction 5 1.2 Genetic Algorithms 7 1.3 Evaluation of Results 8 2 Evolutionary Algorithms 10 2.1 Metaheuristic Approaches 10 2.1.1 NPO-problems 11 2.1.2 Metaheuristics 11 2.2 Evolutionary Computing 12 2.2.1 Definition and Motivation 13 2.2.2 Fundamentals and Terminology 13 2.2.3 The Genetic Algorithm 14 2.2.4 Individuals in Genetic Algorithms 15 2.2.5 Components of Genetic Algorithms 15 2.3 Parallel Genetic Algorithms 20 2.3.1 Taxonomy for Parallel Genetic Algorithms 20 2.3.2 Global Parallel Genetic Algorithms 20 3 Hardware Accelerators 22 3.1 SIMD in Global Parallel Gentic Algorithms 22 3.2 OpenCL 23 4 Concepts and Implementation 25 4.1 Input Data and Pre-Proccesing 26 4.2 Genotype Construction 30 4.3 The Fitness Function 33 4.4 Mutation 35 4.5 The Genetic Algorithm 36 4.6 Global Parallelization and GPU-Usage 38 5 Results and Evaluation 40 5.1 Wall-Time and Fitness 40 5.2 Visual Observation 43 6 Conclusion 44 Appendices 47 A Terminology for Evolutionary Algorithms 48 B PC1 49 C PC2 50 D PC3 51 E PC1 Convergence 52 F PC2 Convergence 53 G PC3 Convergence 54 H Layout Reconstruction 1 55 I Layout Reconstruction 2 56 J t-test for implementation comparison 57

In der vorliegenden Arbeit geht es um die Vorstellung eines assistierenden Algorithmus, welche passende Termine für einen einzelnen Auftrag vorschlagen kann. Das Generieren einer vollständigen Terminplanung ist auch ein Teil dieser Arbeit. Als Erstes wird die Struktur, welche die Algorithmen als Grundlagen benötigen, kurz vorgestellt und erklärt. Dann wird auf die Grundlagen der Mengenlehre eingegangen sowie Anforderung solcher Algorithmen in Hinsicht auf Laufzeit und Komplexität. Zusätzlich werden noch Optimierungsvorschläge auf Basis von parallelisierter Rechnung vorgestellt. Das Ergebnis ist ein Algorithmus, welcher implementiert ist und korrekte Terminvorschläge generieren kann. Hierbei benötigt der Algorithmus für einen Suchraum von sechs Monaten weniger als eine Sekunde Rechenzeit. Die optimierten Versionen benötigen für größere Suchräume (größer als sechs Monate) wenig Zeit und sind langsamer bei kleineren Suchräumen (weniger als zwei Monate). Danach werden mögliche Algorithmen zur Erzeugung eines Terminvorschlags erklärt und gegenübergestellt. Dabei wird ein Ansatz auf evolutionärer Basis vorgestellt sowie ein Algorithmus welcher die Terminplanung als Erfüllbarkeitsproblem behandelt. Dabei werden bei beiden Ansätzen mögliche Probleme sowie deren Lösung vorgestellt. Zuletzt werden diese Algorithmen mit Hauptaugenmerk auf Laufzeit und Komplexität miteinander verglichen. Das Ergebnis resultiert in zwei Algorithmen, welche vom Vorgehen her definiert sind. Eine Implementierung der Algorithmen fehlt hierbei. Abschließend wird ein Ausblick für weiter folgende Aufgaben gegeben.:1 Einleitung 1.1 Thematische Abgrenzung 1.2 Zielsetzung 1.3 Aufbau der Arbeit 2 Definition der zugrundeliegenden Daten 2.1 Struktur der vorliegende Daten 2.2 Anforderung an die Problemlösung 2.3 Beschreibung der Problemlösung 2.4 Definition der Programmumgebung 3 Generierung von Terminvorschlägen 3.1 Mengentheoretischer Ansatz 3.1.1 Die Definition der Grundmengen 3.1.2 Formeln für die Zeitblock-Berechnung 3.1.3 Formeln der Randbedingung 3.2 Unparallelisierter Ansatz 3.2.1 Ladeprozess der Daten 3.2.2 Funktionsweise des Algorithmus 3.2.3 Ergebnis 3.3 Parallelisierter Ansatz 3.3.1 Möglichkeiten der Parallelisierung 3.3.2 Ergebnis der Parallelisierung 3.4 Laufzeitanalyse und Vergleich 4 Zusammenstellung eines Terminplans 4.1 Evolutionäre Ansätze zur Laufzeitoptimierung 4.1.1 Möglicher Ansatz einer Lösung 4.1.2 Problematik von lokalen Optima 4.2 Erfüllbarkeitproblem - SAT-SOLVING 4.2.1 Das Erfüllbarkeitsproblem 4.2.2 Modellierung der Terminplanung 4.2.3 Probleme bei der Modellierung der Zeit 4.2.4 Ansatz einer Lösung 4.3 Vergleich der Ansätze 4.3.1 Auswahl eines Ansatzes 4.3.2 Laufzeitanalyse 5 Zusammenfassung und Ausblick 5.1 Zusammenfassung 5.2 Ausblick Literaturverzeichnis Abbildungsverzeichnis Tabellenverzeichnis Anhang A.1 Quellcode des Projektes A.1.1 Klasse zum Laden und verarbeiten der Daten A.1.2 Klasse für die Generierung von Terminvorschlägen B.2 JSON Datei / In the present thesis, the idea of an assisting algorithm is presented, which can suggest suitable dates for an individual order. The generation of a complete schedule is also a part of this thesis. First, the structure that the algorithms need as a basis is briefly introduced and explained. Then the basics of set theory are discussed and the requirements of such algorithms in terms of run-time and complexity are discussed. Additionally, optimization proposals based on parallelized computation are presented. The result is an algorithm, which is implemented and can generate correct timing proposals. The algorithm needs less than one second of computing time for a search space of six months. The optimized versions need little time for larger search spaces (larger than six months) and are slower for smaller search spaces (less than two months). Afterwards, possible algorithms for generating a date proposal are explained and compared. An evolutionary approach is presented as well as an algorithm that treats scheduling as a fulfillment problem. For both approaches possible problems and their solutions are presented. Finally, these algorithms are compared with each other with a focus on runtime and complexity. The result results in two algorithms, which are defined by the procedure. An implementation of the algorithms is missing here. Finally, an outlook for further tasks is given.:1 Einleitung 1.1 Thematische Abgrenzung 1.2 Zielsetzung 1.3 Aufbau der Arbeit 2 Definition der zugrundeliegenden Daten 2.1 Struktur der vorliegende Daten 2.2 Anforderung an die Problemlösung 2.3 Beschreibung der Problemlösung 2.4 Definition der Programmumgebung 3 Generierung von Terminvorschlägen 3.1 Mengentheoretischer Ansatz 3.1.1 Die Definition der Grundmengen 3.1.2 Formeln für die Zeitblock-Berechnung 3.1.3 Formeln der Randbedingung 3.2 Unparallelisierter Ansatz 3.2.1 Ladeprozess der Daten 3.2.2 Funktionsweise des Algorithmus 3.2.3 Ergebnis 3.3 Parallelisierter Ansatz 3.3.1 Möglichkeiten der Parallelisierung 3.3.2 Ergebnis der Parallelisierung 3.4 Laufzeitanalyse und Vergleich 4 Zusammenstellung eines Terminplans 4.1 Evolutionäre Ansätze zur Laufzeitoptimierung 4.1.1 Möglicher Ansatz einer Lösung 4.1.2 Problematik von lokalen Optima 4.2 Erfüllbarkeitproblem - SAT-SOLVING 4.2.1 Das Erfüllbarkeitsproblem 4.2.2 Modellierung der Terminplanung 4.2.3 Probleme bei der Modellierung der Zeit 4.2.4 Ansatz einer Lösung 4.3 Vergleich der Ansätze 4.3.1 Auswahl eines Ansatzes 4.3.2 Laufzeitanalyse 5 Zusammenfassung und Ausblick 5.1 Zusammenfassung 5.2 Ausblick Literaturverzeichnis Abbildungsverzeichnis Tabellenverzeichnis Anhang A.1 Quellcode des Projektes A.1.1 Klasse zum Laden und verarbeiten der Daten A.1.2 Klasse für die Generierung von Terminvorschlägen B.2 JSON Datei

In this paper, we present a parallel method to evaluate functions on pairs of elements. It is a challenge to partition the Cartesian product of a set with itself in order to parallelize the function evaluation on all pairs. Our solution uses (a) replication of set elements to allow for partitioning and (b) aggregation of the results gathered for different copies of an element. Based on an execution model with nodes that execute tasks on local data without online communication, we present a generic algorithm and show how it can be implemented with MapReduce. Three different distribution schemes that define the partitioning of the Cartesian product are introduced, compared, and evaluated. Any one of the distribution schemes can be used to derive and implement a specific algorithm for parallel pairwise element computation.

Univ., Diss.--Karlsruhe, 2003.

Die vorliegende Arbeit befasst sich mit der Erfassung von Oberflächen mittels Streifenprojektionsverfahren. Dabei wird ein Berechnungsmodell erarbeitet, welches den durch eine Aufnahme erfassten Bereich der Objektoberfläche berechnet und bewertet. Mithilfe einer optimalen Positionierung von Einzelaufnahmen ist es möglich, ein Objekt bei festgelegten Randbedingungen zeitsparend zu erfassen.

Eine Herausforderung der Softwareentwicklung ist, die Korrektheit einer Software sicherzustellen. Testen bietet es keine mathematische Korrektheit. Formale Verifikation ist jedoch oft zu aufwändig. Laufzeitverifikation steht zwischen den beiden Methoden. Laufzeitverifikation beantwortet die Frage, ob ein Eingabe-Ausgabe-Paar korrekt ist. Ein zertifizierender Algorithmus überzeugt seinen Nutzer durch ein Korrektheitsargument zur Laufzeit. Dafür berechnet ein zertifizierender Algorithmus für eine Eingabe zusätzlich zur Ausgabe noch einen Zeugen – ein Korrektheitsargument. Jeder zertifizierende Algorithmus besitzt ein Zeugenprädikat: Ist dieses erfüllt für eine Eingabe, eine Ausgabe und einen Zeugen, so ist das Eingabe-Ausgabe-Paar korrekt. Ein simpler Algorithmus, der das Zeugenprädikat für den Nutzer entscheidet, ist ein Checker. Die Korrektheit des Checkers ist folglich notwendig für den Ansatz und die formale Instanzverifikation, bei der wir Checker verifizieren und einen maschinen-geprüften Beweis für die Korrektheit eines Eingabe-Ausgabe-Paars zur Laufzeit gewinnen. Zertifizierende sequentielle Algorithmen sind gut untersucht. Verteilte Algorithmen, die auf verteilten Systemen laufen, unterscheiden sich grundlegend von sequentiellen Algorithmen: die Ausgabe ist über das System verteilt oder der Algorithmus läuft fortwährend. Wir untersuchen zertifizierende verteilte Algorithmen. Unsere Forschungsfrage ist: Wie können wir das Konzept zertifizierender sequentieller Algorithmen so auf verteilte Algorithmen übertragen, dass wir einerseits nah am ursprünglichen Konzept bleiben und andererseits die Gegebenheiten verteilter Systeme berücksichtigen? Wir stellen eine Methode der Übertragung vor. Die beiden Ziele abwägend entwickeln wir eine Klasse zertifizierender verteilter Algorithmen, die verteilte Zeugen berechnen und verteilte Checker besitzen. Wir präsentieren Fallstudien, Entwurfsmuster und ein Framework zur formalen Instanzverifikation. / A major problem in software engineering is to ensure the correctness of software. Testing offers no mathematical correctness. Formal verification is often too costly. Runtime verification stands between the two methods. Runtime verification answers the question whether an input-output pair is correct. A certifying algorithm convinces its user at runtime by offering a correctness argument. For each input, a certifying algorithm computes an output and additionally a witness. Each certifying algorithm has a witness predicate – a predicate with the property: being satisfied for an input, output and witness implies the input-output pair is correct. A simple algorithm deciding the witness predicate for the user is a checker. Hence, the checker’s correctness is crucial to the approach and motivates formal instance verification where we verify checkers and obtain machine-checked proofs for the correctness of an input-output pair at runtime. Certifying sequential algorithms are well-established. Distributed algorithms, designed to run on distributed systems, behave fundamentally different from sequential algorithms: their output is distributed over the system or they even run continuously. We investigate certifying distributed algorithms. Our research question is: How can we transfer the concept of certifying sequential algorithms to distributed algorithms such that we are in line with the original concept but also adapt to the conditions of distributed systems? In this thesis, we present a method to transfer the concept: Weighing up both sometimes conflicting goals, we develop a class of certifying distributed algorithms that compute distributed witnesses and have distributed checkers. We offer case studies, design patterns and a framework for formal instance verification. Additionally, we investigate other methods to transfer the concept of certifying algorithms to distributed algorithms.

In der klassischen Komplexitätstheorie werden worst-case Laufzeiten von Algorithmen typischerweise einzig abhängig von der Eingabegröße angegeben. In dem Kontext der parametrisierten Komplexitätstheorie versucht man die Analyse der Laufzeit dahingehend zu verfeinern, dass man zusätzlich zu der Eingabengröße noch einen Parameter berücksichtigt, welcher angibt, wie strukturiert die Eingabe bezüglich einer gewissen Eigenschaft ist. Ein parametrisierter Algorithmus nutzt dann diese beschriebene Struktur aus und erreicht so eine Laufzeit, welche schneller ist als die eines besten unparametrisierten Algorithmus, falls der Parameter klein ist. Der erste Hauptteil dieser Arbeit führt die Forschung in diese Richtung weiter aus und untersucht den Einfluss von verschieden Parametern auf die Laufzeit von bekannten effizient lösbaren Problemen. Einige vorgestellte Algorithmen sind dabei adaptive Algorithmen, was bedeutet, dass die Laufzeit von diesen Algorithmen mit der Laufzeit des besten unparametrisierten Algorithm für den größtmöglichen Parameterwert übereinstimmt und damit theoretisch niemals schlechter als die besten unparametrisierten Algorithmen und übertreffen diese bereits für leicht nichttriviale Parameterwerte. Motiviert durch den allgemeinen Erfolg und der Vielzahl solcher parametrisierten Algorithmen, welche eine vielzahl verschiedener Strukturen ausnutzen, untersuchen wir im zweiten Hauptteil dieser Arbeit, wie man solche unterschiedliche homogene Strukturen zu mehr heterogenen Strukturen vereinen kann. Ausgehend von algebraischen Ausdrücken, welche benutzt werden können, um von Parametern beschriebene Strukturen zu definieren, charakterisieren wir klar und robust heterogene Strukturen und zeigen exemplarisch, wie sich die Parameter tree-depth und modular-width heterogen verbinden lassen. Wir beschreiben dazu effiziente Algorithmen auf heterogenen Strukturen mit Laufzeiten, welche im Spezialfall mit den homogenen Algorithmen übereinstimmen. / In classical complexity theory, the worst-case running times of algorithms depend solely on the size of the input. In parameterized complexity the goal is to refine the analysis of the running time of an algorithm by additionally considering a parameter that measures some kind of structure in the input. A parameterized algorithm then utilizes the structure described by the parameter and achieves a running time that is faster than the best general (unparameterized) algorithm for instances of low parameter value. In the first part of this thesis, we carry forward in this direction and investigate the influence of several parameters on the running times of well-known tractable problems. Several presented algorithms are adaptive algorithms, meaning that they match the running time of a best unparameterized algorithm for worst-case parameter values. Thus, an adaptive parameterized algorithm is asymptotically never worse than the best unparameterized algorithm, while it outperforms the best general algorithm already for slightly non-trivial parameter values. As illustrated in the first part of this thesis, for many problems there exist efficient parameterized algorithms regarding multiple parameters, each describing a different kind of structure. In the second part of this thesis, we explore how to combine such homogeneous structures to more general and heterogeneous structures. Using algebraic expressions, we define new combined graph classes of heterogeneous structure in a clean and robust way, and we showcase this for the heterogeneous merge of the parameters tree-depth and modular-width, by presenting parameterized algorithms on such heterogeneous graph classes and getting running times that match the homogeneous cases throughout.

Im Rahmen des 180jährigen Jubiläums der technischen Universität Chemnitz fand am 28. April 2016 das zweite Studierendensymposium der Fakultät Informatik statt. Das Studierendensymposium Informatik richtete sich inhaltlich an alle Themen rund um die Informatik und ihre Anwendungen: Ob Hardware oder Software, ob technische Lösungen oder Anwenderstudien, ob Programmierung oder Verwendung, ob Hardcore-Technik oder gesellschaftliche Fragestellungen – alles, was mit informatischen Lösungen zu tun hat, war willkommen. Das Studierendensymposium Informatik war dabei weder auf die Fakultät Informatik noch auf die TU Chemnitz begrenzt. Es wurden explizit Einreichungen aus thematisch angrenzenden Fächern beworben und Hochschulen der Region in die Planung und Organisation eingebunden. Der Tagungsband enthält die 21 Beitrage, die auf dem Symposium vorgestellt wurden. / In the course of the 180 year anniversary of the Technische Universität Chemnitz the Department of Computer Science held the second Students Symposium on April 18, 2016. The symposium addressed topics related to computer science and its applications: Whether hardware or software, whether technical solutions or user studies, whether programming or use, whether hardcore technology or social issues - everything concerned with computational solutions was welcomed. The Students Symposium included explicitly submissions from thematically adjacent departments and involved universities in the region in planning and organization. The proceedings contain the 21 papers (full and short), which were presented at the symposium.

Im Rahmen des FACETS-Projektes ist die optimierte Abbildung neuronaler Netzwerke durch spezielle Algorithmen auf dafür konzipierte Hardware notwendig, um die Simulation plastischer und pulsierender Modelle zu ermöglichen. Die Erstellung der biologischen und Hardware- Modelle sowie die Konzeptionierung und Analyse der Algorithmen werden in dieser Arbeit vorgestellt.

Univ., Diss.--Augsburg, 2001. / Literaturverz. S. [285] - 311.