TY - THES A1 - Löffler, Sven T1 - Optimierung und Regularisierung von Constraint Satisfaction-Problemen (CSPs) T1 - Optimization and regularization of constraint satisfaction problems (CSPs) N2 - Mit Hilfe der Constraint-Programmierung können komplexe, häufig NP-vollständige Probleme, wie zum Beispiel Graphfärbungs-, Optimierungs-, Konfigurations- sowie Schichtplanungs-, Raum- und Zeitplanungsprobleme modelliert und gelöst werden. Im Vordergrund der Constraint-Programmierung steht dabei die deklarative Modellierung, also eine Beschreibung des eigentlichen Problems und nicht dessen Lösungsvorgangs. Während es Aufgabe des Entwicklers ist, das Problem zu modellieren, wird die Lösung einem separat implementierten Solver (Löser) überlassen. Im Idealfall löst dieser Solver das Problem, unabhängig von der konkreten Modellierung, immer schnellstmöglich. In der Praxis kann von diesem Idealfall in der Regel nicht ausgegangen werden und somit hat die Art und Weise der Modellierung ein und desselben Problems und dessen Remodellierung teilweise einen erheblichen Einfluss auf die Lösungsgeschwindigkeit. Bisher bestehende Remodellierungsverfahren transformieren entweder Constraint-Probleme im Ganzen (zum Beispiel beim Umwandeln in SAT- oder binäre Constraint-Probleme) oder erfordern eine präzise Angabe und Steuerung seitens des Nutzers der Constraint-Programmierung (zum Beispiel bei der Tabularisierung). Während die erste Variante in der Regel nur bei sehr speziellen Problemen zu einer Beschleunigung des Lösungsvorganges führt, benötigt die zweite Variante vom Constraint-Modellierer zusätzliches Expertenwissen über das Lösungsverfahren des verwendeten Solvers. Die bisherigen Verfahren erlauben somit keine (voll)-automatisierte Transformation von Constraint-Problemen, bei der Transformationen nur durchgeführt werden, wenn diese auch zu einer Beschleunigung führen. Für das dieser Arbeit übergeordnete Ziel der automatisierten Optimierung von Constraint-Problemen mittels Remodellierung, ohne dass dafür zusätzliches Expertenwissen notwendig ist, werden ausreichend viele verschiedene, gute und gut untersuchte Remodellierungen benötigt. In dieser Arbeit werden daher sowohl bestehende Verfahren für die Transformation von Constraint-Problemen weiterentwickelt, als auch völlig neue entworfen und deren Korrektheit nachgewiesen. Die in dieser Arbeit entwickelten Transformationen werden bezüglich ihrer beschleunigenden Wirkung auf Constraint-Probleme untersucht. Anhand von generierten und von realen Praxisbeispielen wird die Wirksamkeit der Transformationen evaluiert und es werden Schlussfolgerungen darüber gezogen, wann welche Substituierungen besonders vielversprechend sind. N2 - Constraint programming allows modeling and solving complex, often NP-complete problems, such as graph coloring, optimization, configuration, shift and room planning, and scheduling problems. The focus of constraint programming is declarative modeling, i.e. describing the problem rather than how to solve it. While it is up to the user to model the problem, its solution is left to a separately implemented solver. In a perfect declarative world, this solver always solves the problem as quickly as possible, regardless of its concrete modeling. Unfortunately, this is often not the case and the different ways one and the same problem can be modeled and remodeled can have a significant influence on its solution speed. Already existing remodeling procedures transform either the whole constraint problem (i.e. transformations into SAT- or binary constraint problems) or are applied only when the modeler explicitly controls the optimization process (i.e. by tabulation). While the first method improves the solution speed only for very specific problems, the second method requires a great deal of expert knowledge on the part of the modeler regarding the solution processes of a constraint problem. Therefore, the existing methods do not provide a fully automated transformation of constraint problems, in which transformations are only carried out if they also lead to an acceleration. For the higher goal of automatic optimization of constraint problems with remodeling methods without the necessity of extra expert knowledge, many different, well performing and well researched transformation methods are necessary. In this dissertation, existing methods for such model optimizations will be developed further and completely new ones will be designed, and their correctness proven. The transformations developed in the process of this dissertation will be investigated regarding their accelerating effect on constraint problems. Using both generated and real practical examples, the effectiveness of the transformations will be evaluated, and conclusions will be drawn at which time which substitutions are particularly promising. KW - Constraint Satisfaction-Problem KW - Constraint satisfaction problem KW - Optimierung KW - Optimization KW - Regularisierung KW - Regularization KW - CSP KW - SAT KW - Constraint-Erfüllung KW - Regularisierung KW - Optimierung Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-61490 ER - TY - THES A1 - Liu, Ke T1 - Parallel constraint solving for combinatorial problems T1 - Paralleles Constraint Solving für kombinatorische Probleme N2 - With parallelism becoming the standard in computer design, research on parallel constraint solving technique is of vital importance for enhancing the performance of constraint solving. In this dissertation, we reviewed the literature on exploiting parallelism in constraint solving to help gain insight into the rationale of different types of parallel constraint solving approaches. On this basis, we analyzed the effectiveness of parallel constraint solving, with the focus on obtaining a first solution when solving computationally hard combinatorial problems. We have shown that a well-designed search space splitting method and constraint programming model can enable the embarrassingly parallel search (EPS) to solve some open instances of the social golfer problem that have not been solved by a sequential algorithm. We also observed superlinear speedups when solving these instances, which confirms our theoretical analysis. Besides, we examined two practical constraint optimization problems, including the traveling tournament problem with predefined venues and the talent scheduling problem. Our proposed constraint models outperformed the existing models on the same instances, and the EPS approach could always attain better feasible solutions in terms of the optimal objective value by using more parallel processors. To explore the use of massively parallel processing, we proposed the parallel stochastic portfolio search, which is a simple and non-intrusive way to parallelize different incarnations of a sequential solver. When comparing the existing portfolio to our portfolio approach by solving the same constraint satisfaction problems using the same constraint models, our technique could solve harder and larger instances. The successes of our new parallel approaches are attributed to early diversity; i.e., some diversity early in the search introduced by parallelism can offset early mistakes caused by weak heuristic choices. Unlike the other techniques (e.g., limited discrepancy search) used to overcome early mistakes, the studied two parallel constraint solving approaches not only can explore more nodes simultaneously but also does not sacrifice the guarantee of completeness. We also presented a hypertree decomposition method that builds a degenerate decomposition tree for a given constraint network, in which each node of the decomposition tree possesses and executes a subset of constraints of the given constraint network. The usefulness of our proposed parallel techniquedepends on whether we can find an efficient way to join the results of each node. N2 - Da Parallelität zum Standard im Computerdesign geworden ist, ist die Erforschung paralleler Constraint-Solving-Techniken von entscheidender Bedeutung, um die Leistung des Constraint-Solving zu verbessern. In dieser Dissertation wurde die Literatur zur Ausnutzung der Parallelität bei der Lösung von Nebenbedingungen durchgesehen, um einen Einblick in die Gründe für die verschiedenen Arten von parallelen Lösungsansätzen für Nebenbedingungen zu erhalten. Auf dieser Grundlage haben wir die Effektivität des parallelen Lösens von Nebenbedingungen analysiert, wobei der Schwerpunkt auf der Erlangung einer ersten Lösung beim Lösen rechenintensiver kombinatorischer Probleme lag. Wir haben gezeigt, dass eine gut konzipierte Suchraumaufteilungsmethode und ein Constraint-Programmiermodell die peinlich parallele Suche (EPS) in die Lage versetzen kann, einige offene Instanzen des sozialen Golferproblems zu lösen, die von einem sequentiellen Algorithmus nicht gelöst werden konnten. Wir beobachteten auch superlineare Beschleunigungen beim Lösen dieser Instanzen, was unsere theoretische Analyse bestätigt. Außerdem untersuchten wir zwei praktische Constraint-Optimierungsprobleme, darunter das Traveling-Turnier-Problem mit vordefinierten Austragungsorten und das Talentplanungsproblem. Die von uns vorgeschlagenen Constraint-Modelle übertrafen die bestehenden Modelle bei denselben Instanzen, und der EPS-Ansatz konnte durch die Verwendung von mehr parallelen Prozessoren immer bessere machbare Lösungen in Bezug auf den optimalen Zielwert erzielen. Um die Verwendung von massiv paralleler Verarbeitung zu erforschen, haben wir die parallele stochastische Portfoliosuche vorgeschlagen, die eine einfache und nicht-intrusive Methode zur Parallelisierung verschiedener Inkarnationen eines sequentiellen Solvers ist. Beim Vergleich des existierenden Portfolios mit unserem Portfolio-Ansatz durch Lösen der gleichen Constraint-Satisfaction-Probleme unter Verwendung der gleichen Constraint-Modelle konnte unsere Technik schwierigere und größere Instanzen lösen. Die Erfolge unserer neuen parallelen Ansätze werden auf die frühe Diversität zurückgeführt, d. h. eine gewisse Diversität zu Beginn der Suche, die durch die Parallelität eingeführt wird, kann frühe Fehler ausgleichen, die durch schwache heuristische Entscheidungen verursacht werden. Im Gegensatz zu anderen Techniken (z. B. begrenzte Diskrepanzsuche), die zur Überwindung früher Fehler verwendet werden, können die beiden untersuchten parallelen Ansätze zum Lösen von Beschränkungen nicht nur mehr Knoten gleichzeitig untersuchen, sondern opfern auch nicht die Garantie der Vollständigkeit. Wir haben auch eine Hypertree-Dekompositionsmethode vorgestellt, die einen degenerierten Dekompositionsbaum für ein gegebenes Constraint-Netzwerk aufbaut, bei dem jeder Knoten des Dekompositionsbaums eine Teilmenge von Constraints des gegebenen Constraint-Netzwerks besitzt und ausführt. Die Nützlichkeit der von uns vorgeschlagenen parallelen Technik hängt davon ab, ob wir einen effizienten Weg finden können, die Ergebnisse der einzelnen Knoten zu verbinden. KW - Parallel constraint solving KW - Parallel computing KW - Constraint programing KW - Constraint-Programmierung KW - Lösen von Zwangsbedingungen KW - Paralleles Rechnen KW - SGP KW - Constraint-Programmierung KW - Parallelverarbeitung Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-54375 ER - TY - THES A1 - Liu, Ke T1 - Parallel constraint solving for combinatorial problems T1 - Paralleles Constraint Solving für kombinatorische Probleme N2 - With parallelism becoming the standard in computer design, research on parallel constraint solving technique is of vital importance for enhancing the performance of constraint solving. In this dissertation, we reviewed the literature on exploiting parallelism in constraint solving to help gain insight into the rationale of different types of parallel constraint solving approaches. On this basis, we analyzed the effectiveness of parallel constraint solving, with the focus on obtaining a first solution when solving computationally hard combinatorial problems. We have shown that a well-designed search space splitting method and constraint programming model can enable the embarrassingly parallel search (EPS) to solve some open instances of the social golfer problem that have not been solved by a sequential algorithm. We also observed superlinear speedups when solving these instances, which confirms our theoretical analysis. Besides, we examined two practical constraint optimization problems, including the traveling tournament problem with predefined venues and the talent scheduling problem. Our proposed constraint models outperformed the existing models on the same instances, and the EPS approach could always attain better feasible solutions in terms of the optimal objective value by using more parallel processors. To explore the use of massively parallel processing, we proposed the parallel stochastic portfolio search, which is a simple and non-intrusive way to parallelize different incarnations of a sequential solver. When comparing the existing portfolio to our portfolio approach by solving the same constraint satisfaction problems using the same constraint models, our technique could solve harder and larger instances. The successes of our new parallel approaches are attributed to early diversity; i.e., some diversity early in the search introduced by parallelism can offset early mistakes caused by weak heuristic choices. Unlike the other techniques (e.g., limited discrepancy search) used to overcome early mistakes, the studied two parallel constraint solving approaches not only can explore more nodes simultaneously but also does not sacrifice the guarantee of completeness. We also presented a hypertree decomposition method that builds a degenerate decomposition tree for a given constraint network, in which each node of the decomposition tree possesses and executes a subset of constraints of the given constraint network. The usefulness of our proposed parallel techniquedepends on whether we can find an efficient way to join the results of each node. N2 - Da Parallelität zum Standard im Computerdesign geworden ist, ist die Erforschung paralleler Constraint-Solving-Techniken von entscheidender Bedeutung, um die Leistung des Constraint-Solving zu verbessern. In dieser Dissertation wurde die Literatur zur Ausnutzung der Parallelität bei der Lösung von Nebenbedingungen durchgesehen, um einen Einblick in die Gründe für die verschiedenen Arten von parallelen Lösungsansätzen für Nebenbedingungen zu erhalten. Auf dieser Grundlage haben wir die Effektivität des parallelen Lösens von Nebenbedingungen analysiert, wobei der Schwerpunkt auf der Erlangung einer ersten Lösung beim Lösen rechenintensiver kombinatorischer Probleme lag. Wir haben gezeigt, dass eine gut konzipierte Suchraumaufteilungsmethode und ein Constraint-Programmiermodell die peinlich parallele Suche (EPS) in die Lage versetzen kann, einige offene Instanzen des sozialen Golferproblems zu lösen, die von einem sequentiellen Algorithmus nicht gelöst werden konnten. Wir beobachteten auch superlineare Beschleunigungen beim Lösen dieser Instanzen, was unsere theoretische Analyse bestätigt. Außerdem untersuchten wir zwei praktische Constraint-Optimierungsprobleme, darunter das Traveling-Turnier-Problem mit vordefinierten Austragungsorten und das Talentplanungsproblem. Die von uns vorgeschlagenen Constraint-Modelle übertrafen die bestehenden Modelle bei denselben Instanzen, und der EPS-Ansatz konnte durch die Verwendung von mehr parallelen Prozessoren immer bessere machbare Lösungen in Bezug auf den optimalen Zielwert erzielen. Um die Verwendung von massiv paralleler Verarbeitung zu erforschen, haben wir die parallele stochastische Portfoliosuche vorgeschlagen, die eine einfache und nicht-intrusive Methode zur Parallelisierung verschiedener Inkarnationen eines sequentiellen Solvers ist. Beim Vergleich des existierenden Portfolios mit unserem Portfolio-Ansatz durch Lösen der gleichen Constraint-Satisfaction-Probleme unter Verwendung der gleichen Constraint-Modelle konnte unsere Technik schwierigere und größere Instanzen lösen. Die Erfolge unserer neuen parallelen Ansätze werden auf die frühe Diversität zurückgeführt, d. h. eine gewisse Diversität zu Beginn der Suche, die durch die Parallelität eingeführt wird, kann frühe Fehler ausgleichen, die durch schwache heuristische Entscheidungen verursacht werden. Im Gegensatz zu anderen Techniken (z. B. begrenzte Diskrepanzsuche), die zur Überwindung früher Fehler verwendet werden, können die beiden untersuchten parallelen Ansätze zum Lösen von Beschränkungen nicht nur mehr Knoten gleichzeitig untersuchen, sondern opfern auch nicht die Garantie der Vollständigkeit. Wir haben auch eine Hypertree-Dekompositionsmethode vorgestellt, die einen degenerierten Dekompositionsbaum für ein gegebenes Constraint-Netzwerk aufbaut, bei dem jeder Knoten des Dekompositionsbaums eine Teilmenge von Constraints des gegebenen Constraint-Netzwerks besitzt und ausführt. Die Nützlichkeit der von uns vorgeschlagenen parallelen Technik hängt davon ab, ob wir einen effizienten Weg finden können, die Ergebnisse der einzelnen Knoten zu verbinden. KW - Parallel constraint solving KW - Parallel computing KW - Constraint programing KW - Constraint-Programmierung KW - Lösen von Zwangsbedingungen KW - Paralleles Rechnen KW - SGP KW - Constraint-Programmierung KW - Parallelverarbeitung Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-53999 ER - TY - THES A1 - Prenzel, Anna T1 - Gestaltung der Mensch-Computer-Interaktion zur Entscheidungsunterstützung in Planungssystemen T1 - Design of human computer interaction for decision support in scheduling systems N2 - Mit Hilfe von modernen Feinplanungssystemen kann die Produktions-, Flotten- oder Personaleinsatzplanung nahezu vollständig automatisiert werden. Für den Disponenten wird dadurch der Planungsaufwand erheblich reduziert. Gleichzeitig bieten diese Systeme dem Disponenten jedoch häufig nur unzureichende Interaktionsmöglichkeiten, um sein eigenes Expertenwissen in die Planerstellung einfließen zu lassen. Das Finden und Umsetzen von passenden Planungsentscheidungen ist häufig ein aufwändiger und fehleranfälliger Prozess, der vom Computer nicht unterstützt wird. Dieser Mangel kann die Brauchbarkeit der Pläne und damit den Nutzen des Planungssystems erheblich beeinträchtigen. In dieser Arbeit wird ein Konzept für die Gestaltung der Mensch-Computer-Interaktion in Feinplanungssystemen entwickelt, mit dem eine effektive Einbeziehung des Disponenten abgesichert werden kann. Im Gegensatz zu herkömmlichen Interaktionskonzepten baut es auf wissenschaftlichen Erkenntnissen über menschliche Entscheidungs- und Entwurfsprozesse auf. Dadurch ist es möglich, eine Computerunterstützung sowohl für die Ermittlung als auch für die Umsetzung von Planungsentscheidungen durch den Disponenten zu definieren. Zudem ist das Konzept auf beliebige Feinplanungsprobleme anwendbar. Es setzt sich aus 9 Interaktionsrichtlinien zusammen, deren Effektivität in einem Anwendertest nachgewiesen wird. N2 - With the help of modern detailed planning systems, production, fleet or personal resource planning can be automated nearly completely. By this, the planning effort for the scheduler is reduced significantly. However, these systems often provide insufficient interaction possibilities for the scheduler to incorporate his own expert knowledge in the creation of the schedule. Finding and implementing suitable planning decisions is often a time-consuming and error-prone process that is not supported by the computer. This deficiency can impair the practicability of the schedules and hence the benefit of the planning system considerably. In this work, a concept for the design of the human-computer-interaction in detailed planning systems is developed. It helps to ensure an effective incorporation of the human scheduler. Unlike conventional interaction concepts the concept is built on scientific research about human decision-making and design processes. This makes it possible to define computer support for both the formation and the implementation of planning decisions by the scheduler. Furthermore the concept can be applied to any detailed scheduling problem. It is composed of 9 interaction guidelines. Their effectiveness is proven by a user test. KW - Mensch-Computer-Interaktion KW - Feinplanung KW - Planungssysteme KW - Disponent KW - Entscheidungsprozesse KW - Human-computer-interaction KW - Detailed scheduling KW - Scheduling systems KW - Scheduler KW - Decision making processes KW - Mensch-Maschine-Kommunikation KW - Planungssystem KW - Planungsmodell Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-45278 ER - TY - THES A1 - Vörtler, Thilo T1 - Verification of software for Contiki-based low-power embedded systems using software model checking T1 - Verifikation von Anwendungen für Contiki basierende low-power eingebettete Systeme mit Hilfe von Software Model Checking N2 - The main building blocks for the internet of things are connected embedded systems. Often these systems are also used in safety critical applications. Therefore, it is particularly important that these devices work according to their specification i.e. they behave as intended. Nowadays, even for simple devices embedded operating systems as Contiki are used to simplify application development and to increase portability between different hardware platforms. The main objective of this thesis is to present a methodology for the verification of software applications written for the operation system Contiki, taking the system hardware into account. Therefore, software model checking and especially bounded model checking [BCC⁺03] is used as a technique, which allows to formally verify software for embedded systems. For verifying the software against its specification, it is also necessary to build a model of the system hardware. Thereby, the difficulty is to create a model which is detailed enough to capture the hardware behavior so that the software performs correctly, while keeping the computation effort for the verification process manageable. In this work, the drivers which communicate with the hardware are therefore replaced with abstract models during the verification process. This enables the verification based on an abstract hardware platform independent of specific hardware. A special role within embedded systems play interrupts. Interrupts are used to save power and can also be used to react on external events. Current methods for verification of interrupt driven software are based on the interleaving model and partial order reduction to reduce the size of the verification problem. This thesis argues that this method is not sufficient for software, whose behavior relies on periodically occurring interrupts. Therefore, in this thesis, a new approach called periodic interrupt modeling is introduced. This approach can be applied automatically and reduces the number of incorrect verification results due to inaccurate modeling. In addition, properties can be proven that depend on the number of occurring interrupts. Using applications for the Contiki operating system, and based on a verification flow, the approaches toward interrupt modeling are compared. N2 - Vernetzte eingebettete Systeme bilden die Grundlage für das Internet of Things (IoT). Sie arbeiten häufig autark und in sicherheitskritischen Bereichen. Deshalb ist es wichtig sicherzustellen, dass die Systeme sich korrekt, also gemäß ihrer Spezifikation, verhalten. Zur Erstellung von Software für solche Systeme werden Betriebssysteme wie Contiki verwendet, welche die Programmierung von Anwendungen vereinfachen und die Portabilität zwischen verschiedenen Hardware-Plattformen ermöglichen. In dieser Dissertation wird eine Methodik zur Verifikation von Software-Anwendungen, unter Berücksichtigung der Hardwareumgebung, für eingebettete Systeme anhand des Betriebssystems Contiki vorgestellt. Es wird die Technik des Software Model Checking [CGP00] - und dabei insbesondere Bounded Model Checking [BCC⁺03] - verwendet, welche es ermöglicht die Software eines eingebetteten Systems formal zu verifizieren. Um die Verifikation durchzuführen, muss auch die Hardware des Systems modelliert werden. Die Herausforderung hierbei ist es, die Interaktionen der Software mit der Hardware hinreichend genau abzubilden und gleichzeitig den Aufwand für die Verifikation hinsichtlich des benötigten Rechenaufwands beherrschbar zu halten. In dieser Arbeit wird deshalb ein Ansatz verwendet, der die Treiber, die auf die Hardware zu- greifen durch Softwaremodelle für die Verifikation ersetzt. Dies ermöglicht es Anwendungen für Contiki mit Hilfe einer abstrakten Verifikationsumgebung zu überprüfen. Ein besonderer Aspekt bei eingebetteten Systemen ist die Verwendung von Interrupts, welche es ermöglichen Energie, einzusparen und auf externe Ereignisse zu reagieren. In bisherigen Ansätzen zur Verifikation werden Interrupts mit dem Interleaving Modell modelliert und das Verifikationsproblem mit Hilfe von Partial Order Reduction [CGP00, BK08] reduziert. Diese Arbeit zeigt, dass dieser Ansatz für die Verifikation von Anwendungen, welche periodische Interrupts verwenden, nicht ausreichend ist. Deshalb wird mit Periodic Interrupt Modelling ein neuer Ansatz zur Modellierung von Interrupts vorgestellt. Dieser Ansatz kann automatisiert angewendet werden und verringert die Anzahl von falschen Verifikationsergebnissen aufgrund ungenauer Modellierung. Zusätzlich ist es möglich Eigenschaften zu überprüfen, die von der Häufigkeit von Interrupt-Aufrufen abhängen. Anhand des in der Arbeit entwickelten Verifikationsablaufs werden Beispielprogramme für Contiki untersucht und die Ansätze zur Interruptmodellierung verglichen. KW - Embedded Systems KW - Interrupts KW - Model Checking KW - Contiki KW - Software KW - Contiki KW - Eingebettete Systeme KW - Unterbrechungen KW - Modellprüfung KW - Software KW - Eingebettetes System KW - Interrupt KW - Bounded Model Checking KW - Software Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-44080 ER - TY - THES A1 - Höch, Florian T1 - Statistische Analyse pseudonymisierter Krankenkassenpatientendaten nach geografischen Gesichtspunkten T1 - Statistical analysis of healthy insurance data from pseudonymous patients with emphasis on geographical aspects N2 - Die zentrale Aufgabe dieser Arbeit besteht in der deskriptiven Auswertung eines von der AOK-Sachsen-Anhalt zur Verfügung gestellten Datenbestandes unter Anwendung unterschiedlicher Methoden und Analysen. Dabei liegt der Schwerpunkt der Untersuchungen in der Identifizierung statistischer Auffälligkeiten, deren Entstehungsgründe in ihren geografischen Lagen zu suchen sind. Das Datenmaterial enthält für das Bundesland Sachsen-Anhalt pseudonymisierte personenbezogene Informationen von ca. 600.000 AOK-Versicherten sowie zusätzliche Angaben über ihre ambulanten Behandlungen und verordneten Medikationen aus dem Jahr 2012. Die Auswertung der mehreren Millionen Datensätze wird mit Hilfe der freien Statistik-Software R realisiert. Die Programmiersprache R zeichnet sich durch eine Vielzahl an vordefinierten statistischen und grafischen Funktionen, sowie durch die effiziente Verarbeitung von Massendaten für die visuelle Aufbereitung aus. Zu Beginn werden innerhalb der Einleitung einzelne Fragestellungen formuliert, deren Beantwortung das Hauptziel dieser Arbeit darstellt. Des Weiteren werden in den nachfolgenden Kapiteln einfache statistische Grundlagen vermittelt, sowie eine Einführung in die wichtigsten Befehle und Datenstrukturen der Programmiersprache R gegeben. Anschließend folgt eine detaillierte Beschreibung und Voranalyse des Datenmaterials, bevor mit den auswertenden und explorativen Studien begonnen wird. KW - Statistische Analyse KW - Krankenkassenpatientendaten KW - Auswertung KW - Statistiksoftware R KW - Statistical analysis KW - Healthy insurance data KW - Geographical aspects KW - Sachsen-Anhalt KW - Statistische Analyse KW - Krankenkasse KW - Krankenunterlagen KW - R Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-40454 ER - TY - THES A1 - Jeltsch, Wolfgang T1 - Strongly typed and efficient functional reactive programming T1 - Stark typisierte und effiziente Funktionale Reaktive Programmierung N2 - Functional Reactive Programming (FRP) is a declarative approach to programming reactive and interactive systems. We develop a common interface and a common semantics for FRP and discuss existing implementation approaches. Afterwards, we develop a technique for ensuring start time consistency as well as an efficient implementation of discrete signals. Finally, we present a novel record system, which makes FRP more usable in practice. Our system offers generic record combinators that are statically typed. N2 - Funktionale Reaktive Programmierung (FRP) ist ein deklarativer Ansatz zur Programmierung reaktiver und interaktiver Systeme. Wir entwickeln eine einheitliche Schnittstelle und eine einheitliche Semantik für FRP und diskutieren existierende Implementierungsansätze. Danach entwickeln wir eine Technik zur Sicherung von Startzeitkonsistenz sowie eine effiziente Implementierung diskreter Signale. Schließlich präsentieren wir ein neuartiges Record-System, welches FRP besser nutzbar in der Praxis macht. Unser System bietet generische Record-Kombinatoren, die statisch typisiert sind. KW - Haskell KW - Funktionale Programmierung KW - Funktionale Reaktive Programmierung KW - funktionale Programmierung KW - Haskell KW - Records KW - Kind-System KW - Functional reactive programming KW - Functional programming KW - Haskell KW - Records KW - Kind system Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus-24369 ER - TY - THES A1 - ELssaedi, Mosbah Mohamed T1 - A new approach to Event-Driven Programming T1 - Ein neuer Ansatz zur ereignisgesteuerten Programmierung N2 - In many applications, like embedded systems or systems with a strong user interaction, the program is mainly controlled by events. An event handler waits for any event to occur, and then processes that event by ignoring it or calling a corresponding action, a procedure declared in the program. In this way, events are coupled with actions and can influence the global state of the whole program. In order to design a well structured program, event handling and corresponding actions should be clearly separated. However, this aim is not always ensured. In this thesis, an approach is introduced, which enforces to design event-driven systems into two main parts: - An event-handling part, also called specification part, and - An action part, also called hand-built program part (hbp). The specification part is defined as a declarative specification of the event-handling in a special language. It is separated from the hand-built program part. Every event can only influence the state of this part, which contains the implementation of control functions, which calls the several actions defined in the hand-built program part and so connects both parts together. The prototype of a framework was implemented which allows to specify the eventhandling part by means of a special editor and generates from it some classes and templates. In order to complete the implementation, the programmer has to fill into the templates program code by hand (therefore called hand-built program part), which describe the actions. N2 - In vielen Anwendungen, wie z.B. eingebetteten Systemen oder Systemen mit starker Nutzerinteraktion, wird das Programm hauptsächlich von Ereignissen gesteuert. Eine Ereignisbehandlungsroutine wartet auf das Auftreten eines beliebigen Ereignisses und verarbeitet dann dieses Ereignis, indem sie es ignoriert oder eine entsprechende Aktion aufruft, eine Prozedur, die im Programm deklariert ist. In dieser Weise sind Ereignisse mit Aktionen gekoppelt und können den globalen Zustand des gesamten Programms beeinflussen. Um ein wohl strukturiertes Programm zu entwerfen, sollten die Ereignisbehandlung und die entsprechenden Aktionen klar getrennt werden. Allerdings wird dieses Ziel nicht immer erreicht. In dieser Arbeit wird ein Ansatz eingeführt, welcher die Beschreibung ereignisgesteuerter Systeme in Form von zwei Teilen erzwingt: - einem Ereignisbehandlungsteil, welcher auch Spezifikationsteil genannt wird. - einem Aktionsteil, welcher auch als handgeschriebener Programmteil bezeichnet wird. Der Spezifikationsteil ist als eine deklarative Spezifikation der Ereignisbehandlung in einer Spezialsprache definiert. Er ist vom handgeschriebenen Programmteil getrennt. Jedes Ereignis kann nur den Zustand dieses Teils beeinflussen, welcher die Implementierung von Steuerfunktionen enthält und die verschiedenen Aktionen aufruft, die im handgeschriebenen Programmteil definiert sind, und dadurch beide Teile miteinander verbindet. Es wurde der Prototyp eines Frameworks implementiert, welches es erlaubt, den Ereignisbehandlungsteil mittels eines speziellen Editors zu spezifizieren und daraus verschiedene Klassen und Templates zu generieren. Um die Implementierung zu vervollständigen, muss der Programmierer Programmcode von Hand in die Templates einfügen (daher die Bezeichnung "handgeschriebener Programmteil"), welcher die Aktionen beschreibt. KW - Ereignisgesteuerte Programmierung KW - Event-Driven Programming KW - Spezifizierung KW - Event-Driven Programming KW - Specification Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus-4574 ER - TY - THES A1 - Schölzel, Mario T1 - Automatisierter Entwurf anwendungsspezifischer VLIW-Prozessoren T1 - Automated design of application specific VLIW-Processors N2 - In einigen Einsatzbereichen digitaler Systeme sind die Anforderungen an die Verarbeitungsgeschwindigkeit bei gleichzeitig niedrigem Platz- und Stromverbrauch so hoch, dass sie nur durch die Verwendung spezialisierter Hardware erfüllt werden können. Zugleich sind bereits vor Beginn des Entwurfs solcher Systeme die von ihnen besonders effizient abzuarbeitenden zeitkritischen Algorithmen fest vorgegeben. Eine Hardwarelösung für jeden Algorithmus bietet daher im Allgemeinen die höchste Ausführungsgeschwindigkeit, ist aber unflexibel und sehr zeitintensiv in der Realisierung. Das steht im Widerspruch zu den geforderten kurzen Entwicklungszeiten. Zudem sind bei einer Hardwarelösung kleinere Modifikationen an den Algorithmen in einer späteren Entwurfsphase des Systems kaum noch möglich. Anwendungsspezifische Prozessoren (ASPs) bieten in dieser Hinsicht einen guten Kompromiss zwischen Flexibilität und Ausführungsgeschwindigkeit, da sie durch eine Anpassung an die zeitkritischen Algorithmen diese sehr effizient abarbeiten können und gleichzeitig in der Lage sind, leicht modifizierte Varianten und andere zeitunkritische Teile der Anwendung abzuarbeiten. In dieser Arbeit wird ein methodisches Vorgehen (DESCOMP - Design By Compilation) und die dafür benötigten Techniken vorgestellt, so dass für ein fest vorgegebenes Spektrum an Algorithmen und zugehörigen Zeitschranken die Anpassung der Parameter eines konfigurierbaren ASPs vollständig automatisiert durchgeführt werden kann und der angepasste Prozessor die Algorithmen innerhalb der Zeitschranken abarbeiten kann. Dabei wird der Platz- und Stromverbrauch des Prozessors minimiert. Schwerpunkt bildet die Anpassung an datenflussdominierte Algorithmen. Daher wird während der Design-Space-Exploration (DSE) insbesondere die verfügbare Parallelität auf Instruktionsebene optimiert. Als Basisarchitektur dient ein heterogener geclusterter VLIW-Prozessor. Dessen anzupassende Parameter umfassen die Clusteranzahl, die Art und Anzahl der funktionalen Einheiten (FUs) in jedem Cluster sowie die Kapazität des Verbindungsnetzwerkes zwischen den Clustern. Bereits bekannte Verfahren zur DSE weisen eine hohe Komplexität bei der Anpassung dieser Parameter auf, da die gegebene Anwendung mit einem Compiler für eine Architektur mit festen Parametern übersetzt wird. Die Parameter der Architektur sowie der Compiler werden bei diesen Ansätzen in einem iterativen Prozess modifiziert, weswegen eine große Anzahl von Konfigurationen zu untersuchen ist. Bei DESCOMP dagegen, werden die Algorithmen wie mit einem Compiler übersetzt, jedoch ohne dass die genauen Parameter der Zielarchitektur bekannt sind. Aus dem so erzeugten Zielcode, der hinsichtlich des Platz- und Stromverbrauchs der für seine Abarbeitung erforderlichen Hardware optimiert wurde, werden dann die Parameter des ASPs abgeleitet. Grundlage von DESCOMP bildet die Einteilung der DSE in eine lokale und globale Optimierungsphase. Für die lokale Optimierungsphase wurden zeitbeschränkte heuristische Planungstechniken aus der High-Level-Synthese modifiziert, um optimierte geclusterte Ablaufpläne unterschiedlicher Länge für dieselben Basisblöcke zu erzeugen. Dabei wird die Kombination verschiedener Operatoren in derselben FU bereits berücksichtigt. Das trägt neben der Clusterung zur Reduzierung der erforderlichen Parallelität in den Clustern bei. Ein neu entwickelter Clusterungsalgorithmus, der mit der Planung gekoppelt ist, erlaubt es, in einem iterativen Vorgehen die gegenseitigen Wechselwirkungen von Clusterung und Ablaufplanung zu berücksichtigen sowie vollständig automatisch eine geeignete Clusteranzahl zu bestimmen. Aus den verschiedenen geclusterten Ablaufplänen, die zu einem Basisblock erzeugt wurden, wird in der globalen Optimierungsphase jeweils ein Ablaufplan für jeden Basisblock ausgewählt, so dass die ausgewählten Ablaufpläne ähnliche Anforderungen an den Prozessor stellen und dieser in der Lage ist, die zuvor festgelegten Zeitschranken bei der Abarbeitung einzuhalten. Für die Auswahl werden Informationen aus der lokalen Optimierungsphase genutzt. Es wird berücksichtigt, dass mit steigender Parallelität in den Clustern die maximal mögliche Taktfrequenz des Prozessors sinkt. Mit den vorgestellten Verfahren zur lokalen Optimierung wurden Architekturen für verschiedene Benchmarkprogramme erzeugt und mit den Ergebnissen aus der Dissertation von Victor Lapinskii hinsichtlich der erforderlichen Parallelität verglichen. Es zeigte sich, dass bei gleicher Abarbeitungsgeschwindigkeit mit dem DESCOMP-Ansatz im Durchschnitt ca. 20 Prozent weniger Parallelität in den Architekturen erforderlich ist, was zu einer deutlichen Verringerung des Platz- bzw. Stromverbrauchs führt und gleichzeitig eine höhere Taktfrequenz zulässt. Die Anwendbarkeit der globalen Optimierungsstrategie wurde anhand der Kombination kleinerer Signalverarbeitungsalgorithmen demonstriert. N2 - In many areas of application of digital systems high performance is required. At the same time area and power consumption of the system must be very low. These requirements may only be met by specialized hardware. Furthermore, the algorithms that should be executed by such a digital system are often fixed at the beginning of the development process. Therefore, an application specific integrated circuit (ASIC) for each algorithm may provide the best performance per are/power ratio. However, developing such an ASIC is time consuming and using an ASIC makes it impossible to make little changes in the algorithm at a later development stage. Application Specific Processors (ASPs) provide a good trade-off between performance and flexibility. On the one hand, by adapting them the given algorithm can be executed very fast. On the other hand slightly modified versions of the algorithm and other parts of the application can be executed by the adapted processor, too.This thesis introduces a new methodology (DESCOMP - Design By Compilation) for adapting automatically a configurable ASP to given algorithms, so that the adapted processor executes the given algorithms within given time constraints. The processor is optimized regarding to area and power consumption. The algorithms are data-flow-dominated. Therefore, instruction level parallelism is carefully considered during Design-Space-Exploration (DSE). The adapted base architecture is a configurable clustered VLIW-processor. Its adaptable parameters include number of clusters, number and type of each functional unit in each cluster as well as capacity of inter-cluster-communication network. Already existing approaches for DSE have a large run time for adapting these parameters, due to their iterative proceeding. This means, the given algorithms are compiled for a certain target architecture. The target architecture and the compiler are modified in each iteration, until a well adapted architecture is found. This leads to a large number of architectures that must be considered. DESCOMP avoids this iterative proceeding by compiling the given algorithms like a compiler but without knowing the parameters of the target architecture. Rather the parameters of the target architecture are derived from the produced target code, which is optimized regarding to area and power consumption of the architecture necessary to execute it. By this, a repetitive compilation is not necessary. The separation of the DSE into a local and global optimization stage forms basis for the DESCOMP approach. The local optimization stage uses modified time constrained scheduling techniques from the High-Level-Synthesis in order to produce optimized clustered schedules of different length for each basic block of the given algorithms. In this step the combination of different operators in the same functional unit is already considered. That contributes next to the clustering to the reduction of the required instruction level parallelism in each cluster. A new developed clustering algorithm, which is coupled with the scheduling in an iterative way, allows to consider the mutual dependencies of clustering and scheduling. Moreover, a suitable number of clusters is determined completely automatically.During the local optimization stage information are gained over those architectures that are necessary for executing individual basic blocks with different performance. These information are used in the subsequent global optimization stage for selecting a clustered schedule from all the schedules that were produced for a particular basic block so that the selected schedules of all basic blocks have similar requirements to the processor and the processor is able to execute them within the previously defined time constraints. It is also considered at the selection, that with increasing instruction level parallelism the highest possible clock rate of the processor is reduced.Architectures were produced with the presented approach for different benchmark programs and compared with the architectures that are given in Victor Lapinskii's dissertation with regard to the necessary instruction level parallelism. The results show, that benchmark programs could be executed at the same performance with the DESCOMP architectures while instruction level parallelism could be reduced on average of 20 percent. This leads to a clear decrease of area and power consumption and approves a higher clock rate. The applicability of the global optimization strategy was demonstrated by means of combination of smaller signal processing algorithms into a single benchmark program. KW - Entwurfsautomation KW - Hardwareentwurf KW - VLIW-Architektur KW - Design-Space-Exploration KW - VLIW KW - Prozessorentwurf KW - Design-space-exploration KW - VLIW KW - Processor design Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus-397 ER -