Erfolgreiche Unternehmen denken intensiv über den eigentlichen Nutzen ihres Unternehmens für Kunden nach. Diese versuchen, ihrer Konkurrenz voraus zu sein, und zwar durch gute Ideen, Innovationen und Kreativität. Dabei wird Erfolg anhand von Metriken gemessen, wie z.B. der Anzahl der loyalen Kunden oder der Anzahl der Käufer. Gegeben, dass der Wettbewerb durch die Globalisierung, Deregulierung und technologische Innovation in den letzten Jahren angewachsen ist, spielen die richtigen Entscheidungen für den Erfolg gerade im operativen Geschäft der sämtlichen Bereiche des Unternehmens eine zentrale Rolle. Vor diesem Hintergrund entstammen die in der vorliegenden Arbeit zur Evaluation der Methoden des maschinellen Lernens untersuchten Entscheidungsprobleme vornehmlich der Entscheidungsunterstützung. Hierzu gehören Klassifikationsprobleme wie die Kreditwürdigkeitsprüfung im Bereich Credit Scoring und die Effizienz der Marketing Campaigns im Bereich Direktmarketing. In diesem Kontext ergaben sich Fragestellungen für die korrelativen Modelle, nämlich die Untersuchung der Eignung der Verfahren des maschinellen Lernens für den Bereich des Credit Scoring, die Kalibrierung der Wahrscheinlichkeiten, welche mithilfe von Verfahren des maschinellen Lernens erzeugt werden sowie die Konzeption und Umsetzung einer Synergie-Heuristik zwischen den Methoden der klassischen Statistik und Verfahren des maschinellen Lernens. Desweiteren wurden kausale Modelle für den Bereich Direktmarketing (sog. Uplift-Effekte) angesprochen. Diese Themen wurden im Rahmen von breit angelegten empirischen Studien bearbeitet. Zusammenfassend ergibt sich, dass der Einsatz der untersuchten Verfahren beim derzeitigen Stand der Forschung zur Lösung praxisrelevanter Entscheidungsprobleme sowie spezifischer Fragestellungen, welche aus den besonderen Anforderungen der betrachteten Anwendungen abgeleitet wurden, einen wesentlichen Beitrag leistet. / Nowadays right decisions, being it strategic or operative, are important for every company, since these contribute directly to an overall success. This success can be measured based on quantitative metrics, for example, by the number of loyal customers or the number of incremental purchases. These decisions are typically made based on the historical data that relates to all functions of the company in general and to customers in particular. Thus, companies seek to analyze this data and apply obtained knowlegde in decision making. Classification problems represent an example of such decisions. Classification problems are best solved, when techniques of classical statistics and these of machine learning are applied, since both of them are able to analyze huge amount of data, to detect dependencies of the data patterns, and to produce probability, which represents the basis for the decision making. I apply these techniques and examine their suitability based on correlative models for decision making in credit scoring and further extend the work by causal predictive models for direct marketing. In detail, I analyze the suitability of techniques of machine learning for credit scoring alongside multiple dimensions, I examine the ability to produce calibrated probabilities and apply techniques to improve the probability estimations. I further develop and propose a synergy heuristic between the methods of classical statistics and techniques of machine learning to improve the prediction quality of the former, and finally apply conversion models to turn machine learning techqiques to account for causal relationship between marketing campaigns and customer behavior in direct marketing. The work has shown that the techniques of machine learning represent a suitable alternative to the methods of classical statistics for decision making and should be considered not only in research but also should find their practical application in real-world practices.

Time-of-Flight (ToF)-Kameras erzeugen Tiefenbilder (3D-Bilder), indem sie Infrarotlicht aussenden und die Zeit messen, bis die Reflexion des Lichtes wieder empfangen wird. Durch den Einsatz mehrerer ToF-Kameras können ihre vergleichsweise geringere Auflösungen überwunden, das Sichtfeld vergrößert und Verdeckungen reduziert werden. Der gleichzeitige Betrieb birgt jedoch die Möglichkeit von Störungen, die zu fehlerhaften Tiefenmessungen führen. Das Problem der gegenseitigen Störungen tritt nicht nur bei Mehrkamerasystemen auf, sondern auch wenn mehrere unabhängige ToF-Kameras eingesetzt werden. In dieser Arbeit wird eine neue optische Synchronisation vorgestellt, die keine zusätzliche Hardware oder Infrastruktur erfordert, um ein Zeitmultiplexverfahren (engl. Time-Division Multiple Access, TDMA) für die Anwendung mit ToF-Kameras zu nutzen, um so die Störungen zu vermeiden. Dies ermöglicht es einer Kamera, den Aufnahmeprozess anderer ToF-Kameras zu erkennen und ihre Aufnahmezeiten schnell zu synchronisieren, um störungsfrei zu arbeiten. Anstatt Kabel zur Synchronisation zu benötigen, wird nur die vorhandene Hardware genutzt, um eine optische Synchronisation zu erreichen. Dazu wird die Firmware der Kamera um das Synchronisationsverfahren erweitert. Die optische Synchronisation wurde konzipiert, implementiert und in einem Versuchsaufbau mit drei ToF-Kameras verifiziert. Die Messungen zeigen die Wirksamkeit der vorgeschlagenen optischen Synchronisation. Während der Experimente wurde die Bildrate durch das zusätzliche Synchronisationsverfahren lediglich um etwa 1 Prozent reduziert. / Time-of-Flight (ToF) cameras produce depth images (three-dimensional images) by measuring the time between the emission of infrared light and the reception of its reflection. A setup of multiple ToF cameras may be used to overcome their comparatively low resolution, increase the field of view, and reduce occlusion. However, the simultaneous operation of multiple ToF cameras introduces the possibility of interference resulting in erroneous depth measurements. The problem of interference is not only related to a collaborative multicamera setup but also to multiple ToF cameras operating independently. In this work, a new optical synchronization for ToF cameras is presented, requiring no additional hardware or infrastructure to utilize a time-division multiple access (TDMA) scheme to mitigate interference. It effectively enables a camera to sense the acquisition process of other ToF cameras and rapidly synchronizes its acquisition times to operate without interference. Instead of requiring cables to synchronize, only the existing hardware is utilized to enable an optical synchronization. To achieve this, the camera’s firmware is extended with the synchronization procedure. The optical synchronization has been conceptualized, implemented, and verified with an experimental setup deploying three ToF cameras. The measurements show the efficacy of the proposed optical synchronization. During the experiments, the frame rate was reduced by only about 1% due to the synchronization procedure.

Autismus-Spektrum-Störung (ASD) ist eine neurologische Entwicklungsstörung, die durch eine Reihe von Entwicklungsstörungen gekennzeichnet ist, die zu einem Mangel an sozialen, kommunikativen und kooperativen Fähigkeiten führen. Sozio-kommunikative Beeinträchtigungen können durch von Verhaltenstherapeuten konzipierte und durchgeführte Trainingsprogramme für soziale Kompetenzen verbessert werden. Computergestützte Therapien zur Lösung sozio-kommunikativer Schwierigkeiten bei Kindern, Jugendlichen und Erwachsenen mit ASD haben ermutigende Ergebnisse gezeigt. Das Serious-Game-Format ist eine Form der Intervention. Seriöse Spiele sind pädagogisch wertvoll, aber oft attraktiver als offensichtliche pädagogische Hilfsmittel. Zirkus Empathico 2.0 ist ein Serious Game für mehrere Spieler mit verschiedenen Levels und Bühnen in einer Zirkusumgebung. Die Auswertung erfolgte über einen Zeitraum von acht Wochen. Sechzig Kinder mit ASD im Alter von fünf bis elf Jahren wurden vor und nach der Behandlung untersucht. Zu den primären Ergebnissen gehörten die Empathiebewertung durch die Eltern und objektiv gemessene Fähigkeiten zur Emotionserkennung. Die Bewertung der Effektivität und Verwendbarkeit des Spiels für das Training sozialer Kompetenzen zeigte, dass es eine plausible Lernumgebung schuf, indem es das Bewusstsein der Studienteilnehmer für Fähigkeiten und neurotypisches Verhalten steigerte und ihre vorhergesagte Angst in zukünftigen sozialen Situationen verringerte. Nach der Behandlung wurden signifikante Behandlungseffekte festgestellt. Sowohl bei Kurz- als auch bei Langzeitbeurteilungen. Zirkus Empathico 2.0 ist erfolgreich bei der langfristigen Verbesserung der sozio-emotionalen Fähigkeiten in realen Situationen. Zukünftige Forschung sollte sich auf die spezifischen Prozesse konzentrieren, die den Übertragungs- und Aufrechterhaltungsvorteilen von Empathie und Emotionserkennung zugrunde liegen. / Autism spectrum disorder (ASD) is a neurodevelopmental disorder characterized by a spectrum of developmental abnormalities that result in a lack of social, communicative, and collaborative abilities. Socio-communicative impairments can be improved through behavioral therapist-designed and delivered social-skills training programs. Computer-based therapies to resolve socio-communicative difficulties in children, adolescents, and adults with ASD have demonstrated encouraging outcomes. The serious game format is one type of intervention. Serious games are educational but often appeal more than overt pedagogical tools. Zirkus Empathico 2.0 is a multi-player serious game set with various levels and stages in a circus environment. It was evaluated over eight weeks. Sixty children with ASD aged five to eleven years were evaluated before treatment and post-treatment. Primary outcomes included empathy rating by parents and objectively measured emotion recognition abilities. Secondary outcomes were assessed as emotional awareness, emotion management, well-being, and personal therapy goals. The assessment of the game's effectiveness and usability for social-skills training indicated that it established a plausible learning environment by boosting trial participants' awareness of abilities and neurotypical behavior and decreasing their predicted fear in future social situations. Following treatment, significant treatment effects were detected. In both short- and long-term assessments, moderate impacts were observed on emotional awareness, emotion management, and autistic social symptomatology. Parents reported that therapy goals were met, and that treatment was transferred well. Zirkus Empathico 2.0 is successful at improving long-term socio-emotional abilities in real-world situations. Future research should focus on the specific processes behind empathy and emotion recognition's transmission and maintenance benefits.

Die Objekterkennung ist ein natürlicher Prozess im Menschlichen Gehirn. Sie ndet im visuellen Kortex statt und nutzt die binokulare Eigenschaft der Augen, die eine drei- dimensionale Interpretation von Objekten in einer Szene erlaubt. Kameras ahmen das menschliche Auge nach. Bilder von zwei Kameras, in einem Stereokamerasystem, werden von Algorithmen für eine automatische, dreidimensionale Interpretation von Objekten in einer Szene benutzt. Die Entwicklung von Hard- und Software verbessern den maschinellen Prozess der Objek- terkennung und erreicht qualitativ immer mehr die Fähigkeiten des menschlichen Gehirns. Das Hauptziel dieses Forschungsfeldes ist die Entwicklung von robusten Algorithmen für die Szeneninterpretation. Sehr viel Aufwand wurde in den letzten Jahren in der zweidimen- sionale Objekterkennung betrieben, im Gegensatz zur Forschung zur dreidimensionalen Erkennung. Im Rahmen dieser Arbeit soll demnach die dreidimensionale Objekterkennung weiterent- wickelt werden: hin zu einer besseren Interpretation und einem besseren Verstehen von sichtbarer Realität wie auch der Beziehung zwischen Objekten in einer Szene. In den letzten Jahren aufkommende low-cost Verbrauchersensoren, wie die Microsoft Kinect, generieren Farb- und Tiefendaten einer Szene, um menschenähnliche visuelle Daten zu generieren. Das Ziel hier ist zu zeigen, wie diese Daten benutzt werden können, um eine neue Klasse von dreidimensionalen Objekterkennungsalgorithmen zu entwickeln - analog zur Verarbeitung im menschlichen Gehirn. / Object recognition is a natural process of the human brain performed in the visual cor- tex and relies on a binocular depth perception system that renders a three-dimensional representation of the objects in a scene. Hitherto, computer and software systems are been used to simulate the perception of three-dimensional environments with the aid of sensors to capture real-time images. In the process, such images are used as input data for further analysis and development of algorithms, an essential ingredient for simulating the complexity of human vision, so as to achieve scene interpretation for object recognition, similar to the way the human brain perceives it. The rapid pace of technological advancements in hardware and software, are continuously bringing the machine-based process for object recognition nearer to the inhuman vision prototype. The key in this eld, is the development of algorithms in order to achieve robust scene interpretation. A lot of recognisable and signi cant e ort has been successfully carried out over the years in 2D object recognition, as opposed to 3D. It is therefore, within this context and scope of this dissertation, to contribute towards the enhancement of 3D object recognition; a better interpretation and understanding of reality and the relationship between objects in a scene. Through the use and application of low-cost commodity sensors, such as Microsoft Kinect, RGB and depth data of a scene have been retrieved and manipulated in order to generate human-like visual perception data. The goal herein is to show how RGB and depth information can be utilised in order to develop a new class of 3D object recognition algorithms, analogous to the perception processed by the human brain.

Die motorischen Fähigkeiten humanoider Roboter werden häufig von antriebsbedingten Nichtlinearitäten und Reibungseffekten negativ beeinflusst. Zur deren Kompensation werden üblicherweise modellbasierte Regelkreise genutzt, die i.d.R. von einer hochfrequenten Signalverarbeitung und mehreren Sensorqualitäten abhängen. Entgegen solch modellbasierten Techniken werden in der vorliegenden Arbeit modellfreie Steuerungsmethoden auf Basis parallel gekoppelter Antriebe entwickelt. Zur Entwicklung und Untersuchung dieser Steuerungsmethoden wird nach der von Pfeifer in seinem Werk “How the body shapes the way we think” beschriebenen synthetischen Methodik vorgegangen. Entgegen modellbasierten Untersuchungen auf Basis von Simulationen stehen bei der synthetischen Methodik empirische Untersuchungen am realen System im Vordergrund. Als Ausgangspunkt dienen konventionelle elektromechanische Antriebe mit deren bekannten leistungseinschränkenden Nichtlinearitäten und Reibungseffekten. Durch die parallele Kopplung mehrerer Antriebe an einem einzelnen Gelenk wird das Spektrum der Steuerungsmöglichkeiten deutlich erweitert. Es zeigt sich, dass (1) durch eine konstante antagonistische Vorspannung das Arbeitsverhalten von konventionellen Proportionalreglern optimiert werden kann, (2) durch dynamische asymmetrische Änderung der Vorspannung Nichtlinearitäten bei niedrigen Geschwindigkeiten ausgeglichen werden können und (3) getriebebedingte Reibungseffekte mit einer phasenverschobenen Pulsmodulation der Steuersignale kompensiert werden können. Weiterhin wird gezeigt, wie die erarbeiteten Steuerungsmethoden auf beliebig viele parallel gekoppelte Antriebe übertragen werden können. Für den praktischen Einsatz der Steuerungsmethoden werden diese in einer hybriden Steuerung zusammengeführt. Diese wird durch eine weitere Funktion, den Energiesparmodus beim Halten statischer Positionen, ergänzt und am humanoiden Roboter Myon implementiert und experimentell evaluiert. / Motor functions of humanoid robots are often negatively influenced by nonlinearities and friction effects of the actuators. The popular means of compensation are control circuits based on modelling, which rely on powerful HF Signal processing and various sensor qualities. In contrast, this thesis develops non-modelling control methods based on parallel coupled actuators. Development and exploration of these control methods follow Pfeifer’s synthetic methodology as described in his work “How the body shapes the way we think”. In contrast to the analysis based on emulation as used in modelling, the synthetic methodology focuses rather on empirical tests within the real system. The present work explores control methods for parallel coupled actuators for use in robot points. It starts from conventional electromechanical actuators with their known power limiting nonlinearities and frictional effects. Linking several parallel coupled actuators to a single joint significantly expands the spectrum of control capabilities. Using two parallel coupled actuators as an example, it is examined to which extent undesirable properties of single actuators can be compensated. The results show that (1) the Performance of conventional proportional controllers can be optimized by a constant antagonistic bias voltage, (2) nonlinearities at low velocities can be balanced out by a dynamic asymmetrical adjustment of the bias, and that (3) gear related frictional effects can be compensated by a phase shifted pulse modulation of the control signals. In addition, it is shown how the developed control methods can be applied to a random number of parallel coupled actuators. For practical use, the various control methods are combined in a hybrid control, which is supplemented by an energy saving mode when maintaining static positions. The hybrid control is being implemented into the humanoid robot Myon and evaluated by experiment.

Experimentieren in der vorliegenden Arbeit bedeutet, Experimente auf der Basis von computerbasierten Modellen durchzuführen, wobei diese Modelle Struktur, Verhalten und Umgebung eines Systems abstrahiert beschreiben. Aus verschiedenen Gründen untersucht man stellvertretend für das System ein Modell dieses Systems. Systematisches Experimentieren bei Variation der Modelleingabeparameterbelegung führt in der Regel zu sehr vielen, potentiell lang andauernden Experimenten, die geplant, dokumentiert, automatisiert ausgeführt, überwacht und ausgewertet werden müssen. Häufig besteht dabei das Problem, dass dem Experimentator (der üblicherweise kein Informatiker ist) adäquate Ausdrucksmittel fehlen, um seine Experimentier-Prozesse formal zu beschreiben, so dass sie von einem Computersystem automatisiert ausgeführt werden können. Dabei müssen Verständlichkeit, Nachnutzbarkeit und Reproduzierbarkeit gewahrt werden. Der neue Ansatz besteht darin, generelle Experimentier-Workflow-Konzepte als Spezialisierung von Scientific-Workflows zu identifizieren und diese als eine metamodellbasierte Domain-Specific-Language (DSL) zu formalisieren, die hier als Experimentation-Language (ExpL) bezeichnet wird. ExpL beinhaltet allgemeine Workflow-Konzepte und erlaubt das Modellieren von Experimentier-Workflows auf einer frameworkunabhängigen, konzeptuellen Ebene. Dadurch werden die Nachnutzbarkeit und das Publizieren von Experimentier-Workflows nicht mehr durch die Gebundenheit an ein spezielles Framework behindert. ExpL wird immer in einer konkreten Experimentierdomäne benutzt, die spezifische Anforderungen an Konfigurations- und Auswertemethoden aufweist. Um mit dieser Domänenspezifik umzugehen, wird in dieser Arbeit gezeigt, diese beiden Aspekte separat in zwei weiteren, abhängigen Domain-Specific-Languages (DSLs) zu behandeln: für Konfiguration und Auswertung. / Experimentation in my work means performing experiments based on computer-based models, which describe system structure and behaviour abstractly. Instead of the system itself models of the system will be explored due to several reasons. Systematic experimentation using model input parameter variation assignments leads to lots of possibly long-running experiments that must be planned, documented, automated executed, monitored and evaluated. The problem is, that experimenters (who are usually not computer scientists) miss the proper means of expressions (e. g., to express variations of parameter assignments) to describe experimentation processes formally in a way, that allows their automatic execution by a computer system while preserving reproducibility, re-usability and comprehension. My approach is to identify general experimentation workflow concepts as a specialization of a scientific workflow and formalize them as a meta-model-based domain-specific language (DSL) that I call experimentation language (ExpL). experimentation language (ExpL) includes general workflow concepts like control flow and the composition of activities, and some new declarative language elements. It allows modeling of experimentation workflows on a framework-independent, conceptional level. Hence, re-using and sharing the experimentation workflow with other scientists is not limited to a particular framework anymore. ExpL is always being used in a specific experimentation domain that has certain specifics in configuration and evaluation methods. Addressing this, I propose to separate the concerns and use two other, dependent domain-specific languages (DSLs) additionally for configuration and evaluation.

Diese Arbeit leistet Beiträge zu drei Gebieten der deskriptiven Komplexitätstheorie. Zunächst adaptieren wir einen repräsentationsinvarianten Graphkanonisierungsalgorithmus mit einfach exponentieller Laufzeit von Corneil und Goldberg (1984) und folgern, dass die Logik "Choiceless Polynomial Time with Counting" auf Strukturen, deren Relationen höchstens Stelligkeit 2 haben, gerade die Polynomialzeit-Eigenschaften (PTIME) von Fragmenten logarithmischer Größe charakterisiert. Der zweite Beitrag untersucht die deskriptive Komplexität von PTIME-Berechnungen auf eingeschränkten Graphklassen. Wir stellen eine neuartige Normalform von Intervallgraphen vor, die sich in Fixpunktlogik mit Zählen (FP+C) definieren lässt, was bedeutet, dass FP+C auf dieser Graphklasse PTIME charakterisiert. Wir adaptieren außerdem unsere Methoden, um einen kanonischen Beschriftungsalgorithmus für Intervallgraphen zu erhalten, der sich mit logarithmischer Platzbeschränkung (LOGSPACE) berechnen lässt. Im dritten Teil der Arbeit beschäftigt uns die ungelöste Frage, ob es eine Logik gibt, die alle Polynomialzeit-Berechnungen charakterisiert. Wir führen eine Reihe von Ranglogiken ein, die die Fähigkeit besitzen, den Rang von Matrizen über Primkörpern zu berechnen. Wir zeigen, dass diese Ergänzung um lineare Algebra robuste Logiken hervor bringt, deren Ausdrucksstärke die von FP+C übertrifft. Außerdem beweisen wir, dass Ranglogiken strikt an Ausdrucksstärke gewinnen, wenn wir die Zahl an Variablen erhöhen, die die betrachteten Matrizen indizieren. Dann bauen wir eine Brücke zur klassischen Komplexitätstheorie, indem wir über geordneten Strukturen eine Reihe von Komplexitätsklassen zwischen LOGSPACE und PTIME durch Ranglogiken charakterisieren. Die Arbeit etabliert die stärkste der Ranglogiken als Kandidat für die Charakterisierung von PTIME und legt nahe, dass Ranglogiken genauer erforscht werden müssen, um weitere Fortschritte im Hinblick auf eine Logik für Polynomialzeit zu erzielen. / This thesis is making contributions to three strands of descriptive complexity theory. First, we adapt a representation-invariant, singly exponential-time graph canonization algorithm of Corneil and Goldberg (1984) and conclude that on structures whose relations are of arity at most 2, the logic "Choiceless Polynomial Time with Counting" precisely characterizes the polynomial-time (PTIME) properties of logarithmic-size fragments. The second contribution investigates the descriptive complexity of PTIME computations on restricted classes of graphs. We present a novel canonical form for the class of interval graphs which is definable in fixed-point logic with counting (FP+C), which shows that FP+C captures PTIME on this graph class. We also adapt our methods to obtain a canonical labeling algorithm for interval graphs which is computable in logarithmic space (LOGSPACE). The final part of this thesis takes aim at the open question whether there exists a logic which generally captures polynomial-time computations. We introduce a variety of rank logics with the ability to compute the ranks of matrices over (finite) prime fields. We argue that this introduction of linear algebra results in robust logics whose expressiveness surpasses that of FP+C. Additionally, we establish that rank logics strictly gain in expressiveness when increasing the number of variables that index the matrices we consider. Then we establish a direct connection to standard complexity theory by showing that in the presence of orders, a variety of complexity classes between LOGSPACE and PTIME can be characterized by suitable rank logics. Our exposition provides evidence that rank logics are a natural object to study and establishes the most expressive of our rank logics as a viable candidate for capturing PTIME, suggesting that rank logics need to be better understood if progress is to be made towards a logic for polynomial time.

Serviceevolution erlaubt es, einen Service durch einen anderen Service zu verfeinern oder zu ersetzen. Der Austausch durch einen anderen Service sollte garantieren, dass alle oder ausgewählte Partner des Originalservices erhalten bleiben. In dieser Arbeit entwickeln wir einen Ansatz welcher einem Serviceentwickler helfen soll, Analyse- und Syntheseaufgaben für den Serviceaustausch so durchzuführen, dass jeder Partner eines gegebenen Services beim Austausch erhalten bleibt. Wir modellieren einen Kontrollfluss eines Services als Beschreibung der Reihenfolge von asynchron kommunizierenden Ereignissen mittels eines impliziten ungeordneten Nachrichtenspeichers. Weiterhin studieren wir den Verhaltensaspekt von korrekter Interaktion zwischen Services und konzentrieren uns auf zwei Varianten von Verklemmungsfreiheit als Korrektheitskriterien von Serviceersetzung. Der wichtigste Beitrag ist ein Ansatz zur Charakterisierung jedes möglichen Austausches eines gegebenen Services. Die zentrale Idee dieses Ansatzes ist eine systematische Untersuchung der Verbindung zwischen einem Service und all seiner Partner bzgl. eines gegebenen Korrektheitskriteriums. Wir nutzen diese Verbindung um von einem gegebenen Service einen kanonischen Partner und einen kanonischen Austausch bzgl. aller Partner zu synthetisieren. Ein Service welcher den kanonischen Austausch eines gegebenen Services verfeinert wird als Austausch des gegebenen Services angesehen, wenn die Menge all seiner Partner jeden Partner des gegebenen Services enthält. Mit dem kanonischen Austausch eines gegebenen Services identifizieren wir die Menge der möglichen austauschenden Services eines gegebenen Services bei der jeder exakt die gleichen Partner wie der gegebene Service hat. Einige Ergebnisse dieser Arbeit fundieren auf früheren Arbeiten zu Austausch und Korrektheit von Services und können daher mit diesen verbunden werden um schwierigere Analyse- und Syntheseaufgaben für den Serviceaustausch durchzuführen. / Service evolution allows one service to be refined into or substituted by another service. Substituting one service by another service should guarantee to preserve all or selected partners of the original service. In this thesis, we develop an approach that shall assist a service designer, such as a domain expert, to perform analysis and synthesis tasks on service substitution. We model a control flow of services that describes the ordering of asynchronously communicating events over an implicit unordered message buffer. We study the behavioral aspect of correct interaction between services and concentrate on two variants of deadlock freedom as correctness criteria of service substitution. The major contribution of this thesis is an approach for characterizing the set of all substitutes for a given service. We systematically investigate the relationship between a service and all its partners under a given correctness criterion and employ this relationship to synthesize from a given service its canonical partner and its canonical substitute with respect to all partners. A service that refines the canonical substitute for a given service is regarded as a substitute for the given service if the set of all its partners includes every partner of the given service. With the canonical substitute of a given service, we identify a specific subset of the set of all substitutes for the given service, each of which has exactly the same set of partners as that of the given service. Parts of the results in this thesis have been established upon previous works on service substitution and correctness of services. Consequently, we can also combine our results with the related existing techniques to perform more sophisticated analysis and synthesis tasks on service substitution.

Diese Arbeit beschäftigt sich mit Scheduling von Tasks in Computersystemen. Wir untersuchen sowohl die in neueren Arbeiten betrachtete Zielfunktion zur Energieminimierung als auch die klassische Zielfunktion zur Lastbalancierung auf mehreren Prozessoren. Beim Speed-Scaling mit Sleep-State darf ein Prozessor, der zu jedem Zeitpunkt seine Geschwindigkeit anpassen kann, auch in einen Schlafmodus übergehen. Unser Ziel ist es, den Energieverbrauch zu minimieren. Wir zeigen die NP-Härte des Problems und klären somit den Komplexitätsstatus. Wir beweisen eine untere Schranke für die Approximationsgüte für eine spezielle natürliche Klasse von Schedules. Ferner entwickeln wir eine Familie von Algorithmen, die gute Approximationsfaktoren liefert, und zeigen, dass diese sogar Lösungen liefert, die optimal für die zuvor erwähnte Klasse von Schedules sind. Anschließend widmen wir unsere Aufmerksamkeit dem folgenden Termin-basierten Scheduling-Problem. Es seien mehrere Prozessoren gegeben, wobei jeder einzelne Prozessor zu jedem Zeitpunkt seine Geschwindigkeit anpassen kann. Ziel ist es wie zuvor, den Energieverbrauch des erzeugten Schedules zu minimieren. Für den Offline-Fall entwickeln wir einen optimalen Polynomialzeit-Algorithmus. Für das Online-Problem erweitern wir die zwei bekannten Ein-Prozessor-Algorithmen Optimal Available und Average Rate. Wir zeigen, dass diese den gleichen bzw. einen um die additive Konstante von eins vergrößerten kompetiven Faktor haben. Bei der Lastbalancierung auf mehreren Prozessoren betrachten wir Offline-Load-Balancing auf identischen Maschinen. Unser Ziel ist es, die Current-Load für temporäre Tasks mit identischem Gewicht zu minimieren. Wir zeigen, dass eine Lösung mit maximaler Imbalance von eins immer existiert und entwickeln einen effizienten Algorithmus, der solche Lösungen liefert. Zum Schluss beweisen wir die NP-Härte von zwei Verallgemeinerungen des Problems. / This thesis studies problems of scheduling tasks in computing environments. We consider both the modern objective function of minimizing energy consumption, and the classical objective of balancing load across machines. We first investigate offline deadline-based scheduling in the setting of a single variable-speed processor that is equipped with a sleep state. The objective is that of minimizing the total energy consumption. Apart from settling the complexity of the problem by showing its NP-hardness, we provide a lower bound of 2 for general convex power functions, and a particular natural class of schedules. We also present an algorithmic framework for designing good approximation algorithms. Furthermore, we give tight bounds for the aforementioned particular class of schedules. We then focus on the multiprocessor setting where each processor has the ability to vary its speed. We first study the offline problem and show that optimal schedules can be computed efficiently in polynomial time. Regarding the online problem and a natural class of power functions, we extend the two well-known single-processor algorithms Optimal Available and Average Rate. We prove that Optimal Available has the same competitive ratio as in the single-processor case. For Average Rate we show a competitive factor that increases by an additive constant of one compared to the single-processor result. With respect to load balancing, we consider offline load balancing on identical machines, with the objective of minimizing the current load, for temporary unit-weight jobs. The problem can be seen as coloring n intervals with k colors, such that for each point on the line, the maximal difference between the number of intervals of any two colors is minimal. We prove that a coloring with maximal difference at most one is always possible, and develop a fast polynomial-time algorithm for generating such a coloring. Lastly, we prove that two generalizations of the problem are NP-hard.

Auf dem Gebiet der drahtlosen Kommunikation und insbesondere auf den tieferen Netzwerkschichten sind gewaltige Fortschritte zu verzeichnen. Innovative Konzepte und Technologien auf der physikalischen Schicht (PHY) gehen dabei zeitnah in zelluläre Netze ein. Drahtlose Maschennetzwerke (WMNs) können mit diesem Innovationstempo nicht mithalten. Die Mehrnutzer-Kommunikation ist ein Grundpfeiler vieler angewandter PHY Technologien, die sich in WMNs nur ungenügend auf die etablierte Schichtenarchitektur abbilden lässt. Insbesondere ist das Problem des Scheduling in WMNs inhärent komplex. Erstaunlicherweise ist der Mehrfachzugriff mit Trägerprüfung (CSMA) in WMNs asymptotisch optimal obwohl das Verfahren eine geringe Durchführungskomplexität aufweist. Daher stellt sich die Frage, in welcher Weise das dem CSMA zugrunde liegende Konzept des konkurrierenden Wettbewerbs (engl. Contention) für die Integration innovativer PHY Technologien verwendet werden kann. Opportunistische Kommunikation ist eine Technik, die die inhärenten Besonderheiten des drahtlosen Kanals ausnutzt. In der vorliegenden Dissertation werden CSMA-basierte Protokolle für die opportunistische Kommunikation in WMNs entwickelt und evaluiert. Es werden dabei opportunistisches Routing (OR) im zustandslosen Kanal und opportunistisches Scheduling (OS) im zustandsbehafteten Kanal betrachtet. Ziel ist es, den Durchsatz von elastischen Paketflüssen gerecht zu maximieren. Es werden Modelle für Überlastkontrolle, Routing und konkurrenzbasierte opportunistische Kommunikation vorgestellt. Am Beispiel von IEEE 802.11 wird illustriert, wie der schichtübergreifende Entwurf in einem Netzwerksimulator prototypisch implementiert werden kann. Auf Grundlage der Evaluationsresultate kann der Schluss gezogen werden, dass die opportunistische Kommunikation konkurrenzbasiert realisierbar ist. Darüber hinaus steigern die vorgestellten Protokolle den Durchsatz im Vergleich zu etablierten Lösungen wie etwa DCF, DSR, ExOR, RBAR und ETT. / In the field of wireless communication, a tremendous progress can be observed especially at the lower layers. Innovative physical layer (PHY) concepts and technologies can be rapidly assimilated in cellular networks. Wireless mesh networks (WMNs), on the other hand, cannot keep up with the speed of innovation at the PHY due to their flat and decentralized architecture. Many innovative PHY technologies rely on multi-user communication, so that the established abstraction of the network stack does not work well for WMNs. The scheduling problem in WMNs is inherent complex. Surprisingly, carrier sense multiple access (CSMA) in WMNs is asymptotically utility-optimal even though it has a low computational complexity and does not involve message exchange. Hence, the question arises whether CSMA and the underlying concept of contention allows for the assimilation of advanced PHY technologies into WMNs. In this thesis, we design and evaluate contention protocols based on CSMA for opportunistic communication in WMNs. Opportunistic communication is a technique that relies on multi-user diversity in order to exploit the inherent characteristics of the wireless channel. In particular, we consider opportunistic routing (OR) and opportunistic scheduling (OS) in memoryless and slow fading channels, respectively. We present models for congestion control, routing and contention-based opportunistic communication in WMNs in order to maximize both throughput and fairness of elastic unicast traffic flows. At the instance of IEEE 802.11, we illustrate how the cross-layer algorithms can be implemented within a network simulator prototype. Our evaluation results lead to the conclusion that contention-based opportunistic communication is feasible. Furthermore, the proposed protocols increase both throughput and fairness in comparison to state-of-the-art approaches like DCF, DSR, ExOR, RBAR and ETT.