COBAMOS: Endnutzerprogrammierung auf Basis nachrichtenbasierter Komponentenvernetzung

Die Aufgabenstellung, welche dieser Dissertation zugrunde liegt, l��sst sich kurz als die Untersuchung von komponentenbasierten Konzepten zum Einsatz in der Softwareentwicklung durch Endanwender beschreiben. In den letzten 20 bis 30 Jahren hat sich das technische Umfeld, in dem ein Gro��teil der Arbeitnehmer seine t��glichen Aufgaben verrichtet, grundlegend ver��ndert. Der Computer, fr��her in Form eines Gro��rechners ausschlie��lich die Dom��ne von Spezialisten, ist nun ein selbstverst��ndlicher Bestandteil der t��glichen Arbeit. Der Umgang mit Anwendungsprogrammen, die dem Nutzer erlauben in einem gewissen Rahmen neue, eigene Funktionalit��t zu definieren, ist in vielen Bereichen so selbstverst��ndlich, dass viele dieser T��tigkeiten nicht bewusst als Programmieren wahrgenommen werden. Da diese Nutzer nicht notwendigerweise in der Entwicklung von Software ausgebildet sind, ben��tigen sie entsprechende Unterst��tzung bei diesen T��tigkeiten. Dies macht deutlich, welche praktische Relevanz die Untersuchungen in diesem Bereich haben. Zur Erstellung eines Programmiersystems f��r Endanwender wird zun��chst ein flexibler Anwendungsrahmen entwickelt, welcher sich als Basis zur Erstellung solcher Systeme eignet. In Softwareprojekten sind sich ��ndernde Anforderungen und daraus resultierende Notwendigkeiten ein wichtiger Aspekt. Dies wird im Entwurf des Frameworks durch Konzepte zur Bereitstellung von wieder verwendbarer Funktionalit��t durch das Framework und M��glichkeiten zur Anpassung und Erweiterung der vorhandenen Funktionalit��t ber��cksichtigt. Hier ist zum einen der Einsatz einer serviceorientierten Architektur innerhalb der Anwendung und zum anderen eine komponentenorientierte Variante des Kommando-Musters zu nennen. Zum anderen wird ein Konzept zur Kapselung von Endnutzerprogrammiermodellen in Komponenten erarbeitet. Dieser Ansatz erm��glicht es, unterschiedliche Modelle als Grundlage der entworfenen Entwicklungsumgebung zu verwenden. Im weiteren Verlauf der Arbeit wird ein Programmiermodell entworfen und unter Verwendung des zuvor genannten Frameworks implementiert. Damit dieses zur Nutzung durch Endanwender geeignet ist, ist eine Anhebung der zur Beschreibung eines Softwaresystems verwendeten Abstraktionsebene notwendig. Dies wird durch die Verwendung von Komponenten und einem nachrichtenbasierten Kompositionsmechanismus erreicht. Die vorgenommene Realisierung ist dabei noch nicht auf konkrete Anwendungsfamilien bezogen, diese Anpassungen erfolgen in einem weiteren Schritt f��r zwei unterschiedliche Anwendungsbereiche.

Exact computation of the adjacency graph of an arrangement of quadrics

Pr��sentiert wird ein vollst��ndiger, exakter und effizienter Algorithmus zur Berechnung des Nachbarschaftsgraphen eines Arrangements von Quadriken (Algebraische Fl��chen vom Grad 2). Dies ist ein wichtiger Schritt auf dem Weg zur Berechnung des vollen 3D Arrangements. Dabei greifen wir auf eine bereits existierende Implementierung zur Berechnung der exakten Parametrisierung der Schnittkurve von zwei Quadriken zur��ck. Somit ist es m��glich, die exakten Parameterwerte der Schnittpunkte zu bestimmen, diese entlang der Kurven zu sortieren und den Nachbarschaftsgraphen zu berechnen. Wir bezeichnen unsere Implementierung als vollst��ndig, da sie auch die Behandlung aller Sonderf��lle wie singul��rer oder tangentialer Schnittpunkte einschlie��t. Sie ist exakt, da immer das mathematisch korrekte Ergebnis berechnet wird. Und schlie��lich bezeichnen wir unsere Implementierung als effizient, da sie im Vergleich mit dem einzigen bisher implementierten Ansatz gut abschneidet. Implementiert wurde unser Ansatz im Rahmen des Projektes EXACUS. Das zentrale Ziel von EXACUS ist es, einen Prototypen eines zuverl��ssigen und leistungsf��higen CAD Geometriekerns zu entwickeln. Obwohl wir das Design unserer Bibliothek als prototypisch bezeichnen, legen wir dennoch gr����ten Wert auf Vollst��ndigkeit, Exaktheit, Effizienz, Dokumentation und Wiederverwendbarkeit. ��ber den eigentlich Beitrag zu EXACUS hinaus, hatte der hier vorgestellte Ansatz durch seine besonderen Anforderungen auch wesentlichen Einfluss auf grundlegende Teile von EXACUS. Im Besonderen hat diese Arbeit zur generischen Unterst��tzung der Zahlentypen und der Verwendung modularer Methoden innerhalb von EXACUS beigetragen. Im Rahmen der derzeitigen Integration von EXACUS in CGAL wurden diese Teile bereits erfolgreich in ausgereifte CGAL Pakete weiterentwickelt.

Lernen mit einer Hybride aus Lernendem Klassifizierendem System und Selbstorganisierender Karte

Im Forschungsgebiet der K��nstlichen Intelligenz, insbesondere im Bereich des maschinellen Lernens, hat sich eine ganze Reihe von Verfahren etabliert, die von biologischen Vorbildern inspiriert sind. Die prominentesten Vertreter derartiger Verfahren sind zum einen Evolution��re Algorithmen, zum anderen K��nstliche Neuronale Netze. Die vorliegende Arbeit befasst sich mit der Entwicklung eines Systems zum maschinellen Lernen, das Charakteristika beider Paradigmen in sich vereint: Das Hybride Lernende Klassifizierende System (HCS) wird basierend auf dem reellwertig kodierten eXtended Learning Classifier System (XCS), das als Lernmechanismus einen Genetischen Algorithmus enth��lt, und dem Wachsenden Neuralen Gas (GNG) entwickelt. Wie das XCS evolviert auch das HCS mit Hilfe eines Genetischen Algorithmus eine Population von Klassifizierern - das sind Regeln der Form [WENN Bedingung DANN Aktion], wobei die Bedingung angibt, in welchem Bereich des Zustandsraumes eines Lernproblems ein Klassifizierer anwendbar ist. Beim XCS spezifiziert die Bedingung in der Regel einen achsenparallelen Hyperquader, was oftmals keine angemessene Unterteilung des Zustandsraumes erlaubt. Beim HCS hingegen werden die Bedingungen der Klassifizierer durch Gewichtsvektoren beschrieben, wie die Neuronen des GNG sie besitzen. Jeder Klassifizierer ist anwendbar in seiner Zelle der durch die Population des HCS induzierten Voronoizerlegung des Zustandsraumes, dieser kann also flexibler unterteilt werden als beim XCS. Die Verwendung von Gewichtsvektoren erm��glicht ferner, einen vom Neuronenadaptationsverfahren des GNG abgeleiteten Mechanismus als zweites Lernverfahren neben dem Genetischen Algorithmus einzusetzen. W��hrend das Lernen beim XCS rein evolution��r erfolgt, also nur durch Erzeugen neuer Klassifizierer, erm��glicht dies dem HCS, bereits vorhandene Klassifizierer anzupassen und zu verbessern. Zur Evaluation des HCS werden mit diesem verschiedene Lern-Experimente durchgef��hrt. Die Leistungsf��higkeit des Ansatzes wird in einer Reihe von Lernproblemen aus den Bereichen der Klassifikation, der Funktionsapproximation und des Lernens von Aktionen in einer interaktiven Lernumgebung unter Beweis gestellt.

Efficient certification of feasibility and objective value of linear programs and its applications

The use of linear programming in various areas has increased with the significant improvement of specialized solvers. Linear programs are used as such to model practical problems, or as subroutines in algorithms such as formal proofs or branch-and-cut frameworks. In many situations a certified answer is needed, for example the guarantee that the linear program is feasible or infeasible, or a provably safe bound on its objective value. Most of the available solvers work with floating-point arithmetic and are thus subject to its shortcomings such as rounding errors or underflow, therefore they can deliver incorrect answers. While adequate for some applications, this is unacceptable for critical applications like flight controlling or nuclear plant management due to the potential catastrophic consequences. We propose a method that gives a certified answer whether a linear program is feasible or infeasible, or returns unknown'. The advantage of our method is that it is reasonably fast and rarely answers unknown'. It works by computing a safe solution that is in some way the best possible in the relative interior of the feasible set. To certify the relative interior, we employ exact arithmetic, whose use is nevertheless limited in general to critical places, allowing us to rnremain computationally efficient. Moreover, when certain conditions are fulfilled, our method is able to deliver a provable bound on the objective value of the linear program. We test our algorithm on typical benchmark sets and obtain higher rates of success compared to previous approaches for this problem, while keeping the running times acceptably small. The computed objective value bounds are in most of the cases very close to the known exact objective values. We prove the usability of the method we developed by additionally employing a variant of it in a different scenario, namely to improve the results of a Satisfiability Modulo Theories solver. Our method is used as a black box in the nodes of a branch-and-bound tree to implement conflict learning based on the certificate of infeasibility for linear programs consisting of subsets of linear constraints. The generated conflict clauses are in general small and give good rnprospects for reducing the search space. Compared to other methods we obtain significant improvements in the running time, especially on the large instances.

Optimized scheduling in real-time environments with column generation

Im Bereich sicherheitsrelevanter eingebetteter Systeme stellt sich der Designprozess von Anwendungen als sehr komplex dar. Entsprechend einer gegebenen Hardwarearchitektur lassen sich Steuerger��te aufr��sten, um alle bestehenden Prozesse und Signale p��nktlich auszuf��hren. Die zeitlichen Anforderungen sind strikt und m��ssen in jeder periodischen Wiederkehr der Prozesse erf��llt sein, da die Sicherstellung der parallelen Ausf��hrung von gr����ter Bedeutung ist. Existierende Ans��tze k��nnen schnell Designalternativen berechnen, aber sie gew��hrleisten nicht, dass die Kosten f��r die n��tigen Hardware��nderungen minimal sind. Wir stellen einen Ansatz vor, der kostenminimale L��sungen f��r das Problem berechnet, die alle zeitlichen Bedingungen erf��llen. Unser Algorithmus verwendet Lineare Programmierung mit Spaltengenerierung, eingebettet in eine Baumstruktur, um untere und obere Schranken w��hrend des Optimierungsprozesses bereitzustellen. Die komplexen Randbedingungen zur Gew��hrleistung der periodischen Ausf��hrung verlagern sich durch eine Zerlegung des Hauptproblems in unabh��ngige Unterprobleme, die als ganzzahlige lineare Programme formuliert sind. Sowohl die Analysen zur Prozessausf��hrung als auch die Methoden zur Signal��bertragung werden untersucht und linearisierte Darstellungen angegeben. Des Weiteren pr��sentieren wir eine neue Formulierung f��r die Ausf��hrung mit fixierten Priorit��ten, die zus��tzlich Prozessantwortzeiten im schlimmsten anzunehmenden Fall berechnet, welche f��r Szenarien n��tig sind, in denen zeitliche Bedingungen an Teilmengen von Prozessen und Signalen gegeben sind. Wir weisen die Anwendbarkeit unserer Methoden durch die Analyse von Instanzen nach, welche Prozessstrukturen aus realen Anwendungen enthalten. Unsere Ergebnisse zeigen, dass untere Schranken schnell berechnet werden k��nnen, um die Optimalit��t von heuristischen L��sungen zu beweisen. Wenn wir optimale L��sungen mit Antwortzeiten liefern, stellt sich unsere neue Formulierung in der Laufzeitanalyse vorteilhaft gegen��ber anderen Ans��tzen dar. Die besten Resultate werden mit einem hybriden Ansatz erzielt, der heuristische Startl��sungen, eine Vorverarbeitung und eine heuristische mit einer kurzen nachfolgenden exakten Berechnungsphase verbindet.

Data dissemination over complex networks through gossip

This thesis offers a practical and theoretical evaluations about gossip-epidemic algorithms, comparing those most common in the literature with new proposed algorithms and analyzing their behavior. Tests have been executed using one hundred graphs that has been randomly generated by Large Unstructured NEtwork Simulator (LUNES), a simulation software provided by Parallel and Distributed Simulation Research Group (PADS), of the Department of Computer Science, Universit�� di Bologna and simulated using Advanced RTI System (ART��S), based on the High Level Architecture standard. Literatures algorithms have been analyzed and taken as base for new algorithms.

Efficient subsequence alignment of time series

Zeitreihen sind allgegenw��rtig. Die Erfassung und Verarbeitung kontinuierlich gemessener Daten ist in allen Bereichen der Naturwissenschaften, Medizin und Finanzwelt vertreten. Das enorme Anwachsen aufgezeichneter Datenmengen, sei es durch automatisierte Monitoring-Systeme oder integrierte Sensoren, bedarf au��erordentlich schneller Algorithmen in Theorie und Praxis. Infolgedessen besch��ftigt sich diese Arbeit mit der effizienten Berechnung von Teilsequenzalignments. Komplexe Algorithmen wie z.B. Anomaliedetektion, Motivfabfrage oder die un��berwachte Extraktion von prototypischen Bausteinen in Zeitreihen machen exzessiven Gebrauch von diesen Alignments. Darin begr��ndet sich der Bedarf nach schnellen Implementierungen. Diese Arbeit untergliedert sich in drei Ans��tze, die sich dieser Herausforderung widmen. Das umfasst vier Alignierungsalgorithmen und ihre Parallelisierung auf CUDA-f��higer Hardware, einen Algorithmus zur Segmentierung von Datenstr��men und eine einheitliche Behandlung von Liegruppen-wertigen Zeitreihen.rnrnDer erste Beitrag ist eine vollst��ndige CUDA-Portierung der UCR-Suite, die weltf��hrende Implementierung von Teilsequenzalignierung. Das umfasst ein neues Berechnungsschema zur Ermittlung lokaler Alignierungsg��ten unter Verwendung z-normierten euklidischen Abstands, welches auf jeder parallelen Hardware mit Unterst��tzung f��r schnelle Fouriertransformation einsetzbar ist. Des Weiteren geben wir eine SIMT-vertr��gliche Umsetzung der Lower-Bound-Kaskade der UCR-Suite zur effizienten Berechnung lokaler Alignierungsg��ten unter Dynamic Time Warping an. Beide CUDA-Implementierungen erm��glichen eine um ein bis zwei Gr����enordnungen schnellere Berechnung als etablierte Methoden.rnrnAls zweites untersuchen wir zwei Linearzeit-Approximierungen f��r das elastische Alignment von Teilsequenzen. Auf der einen Seite behandeln wir ein SIMT-vertr��gliches Relaxierungschema f��r Greedy DTW und seine effiziente CUDA-Parallelisierung. Auf der anderen Seite f��hren wir ein neues lokales Abstandsma�� ein, den Gliding Elastic Match (GEM), welches mit der gleichen asymptotischen Zeitkomplexit��t wie Greedy DTW berechnet werden kann, jedoch eine vollst��ndige Relaxierung der Penalty-Matrix bietet. Weitere Verbesserungen umfassen Invarianz gegen Trends auf der Messachse und uniforme Skalierung auf der Zeitachse. Des Weiteren wird eine Erweiterung von GEM zur Multi-Shape-Segmentierung diskutiert und auf Bewegungsdaten evaluiert. Beide CUDA-Parallelisierung verzeichnen Laufzeitverbesserungen um bis zu zwei Gr����enordnungen.rnrnDie Behandlung von Zeitreihen beschr��nkt sich in der Literatur in der Regel auf reellwertige Messdaten. Der dritte Beitrag umfasst eine einheitliche Methode zur Behandlung von Liegruppen-wertigen Zeitreihen. Darauf aufbauend werden Distanzma��e auf der Rotationsgruppe SO(3) und auf der euklidischen Gruppe SE(3) behandelt. Des Weiteren werden speichereffiziente Darstellungen und gruppenkompatible Erweiterungen elastischer Ma��e diskutiert.

Embedding Languages Without Breaking Tools

Domain-specific languages (DSLs) are increasingly used as embedded languages within general-purpose host languages. DSLs provide a compact, dedicated syntax for specifying parts of an application related to specialized domains. Unfortunately, such language extensions typically do not integrate well with the development tools of the host language. Editors, compilers and debuggers are either unaware of the extensions, or must be adapted at a non-trivial cost. We present a novel approach to embed DSLs into an existing host language by leveraging the underlying representation of the host language used by these tools. Helvetia is an extensible system that intercepts the compilation pipeline of the Smalltalk host language to seamlessly integrate language extensions. We validate our approach by case studies that demonstrate three fundamentally different ways to extend or adapt the host language syntax and semantics.

INTEGRATION D���UN OBSERVATOIRE URBAIN SUR GOOGLE MAPS : Cas des infrastructures de la sant�� de la ville de Douala Cameroun

The spectacular advances computer science applied to geographic information systems (GIS) in recent times has favored the emergence of several technological solutions. These developments have given rise to enormous opportunities for digital management of the territory. Among the technological solutions, the most famous Google Maps offers free online mapping dynamic exhaustive of the Maps. In addition to meet the enormous needs of urban indicators geotagged information, we did work on this project ���Integration of an urban observatory on Google Maps.��� The problem of geolocation in the urban observatory is particularly relevant in the sense that there is currently no data (descriptive and geographical) reliable on the urban sector; we must stick to extrapolate from data old and obsolete. This helps to curb the effectiveness of urban management to make difficult investment programming and to prevent the acquisition of knowledge to make cities engines of growth. The use of a geolocation tool coupled to the data would allow better monitoring of indicators Our project's objective is to develop an interactive map server (WebMapping) which map layer is formed from the resources of the Google Maps servers and match information from the field to produce maps of urban equipment and infrastructure of a city data to the client's request To achieve this goal, we will participate in a study of a GPS location of strategic sites in our core sector (health facilities), on the other hand, using information from the field, we will build a postgresql database that will link the information from the field to map from Google Maps via KML scripts and PHP appropriate. We will limit ourselves in our work to the city of Douala Cameroon with the sectors of health facilities with the possibility of extension to other areas and other cities. Keywords: Geographic Information System (GIS), Thematic Mapping, Web Mapping, data mining, Google API.

CONVERSION OF DOMAIN TYPE ENFORCEMENT LANGUAGE TO THE JAVA SECURITY MANAGER

With today's prevalence of Internet-connected systems storing sensitive data and the omnipresent threat of technically skilled malicious users, computer security remains a critically important field. Because of today's multitude of vulnerable systems and security threats, it is vital that computer science students be taught techniques for programming secure systems, especially since many of them will work on systems with sensitive data after graduation. Teaching computer science students proper design, implementation, and maintenance of secure systems is a challenging task that calls for the use of novel pedagogical tools. This report describes the implementation of a compiler that converts mandatory access control specification Domain-Type Enforcement Language to the Java Security Manager, primarily for pedagogical purposes. The implementation of the Java Security Manager was explored in depth, and various techniques to work around its inherent limitations were explored and partially implemented, although some of these workarounds do not appear in the current version of the compiler because they would have compromised cross-platform compatibility. The current version of the compiler and implementation details of the Java Security Manager are discussed in depth.