TY - THES A1 - Hanning, Tobias T1 - Vektorielle Mehrniveaupassung. Anwendungen in der Bildsegmentierung N2 - Die Anwendungen der vektoriellen Mehrniveaupassung in der Bildsegmentierung stehen in unmittelbarer Nachbarschaft zum verbreiteten Ansatz, Bilder mit Methoden der Variationsrechnung über einen Energieterm zu segmentieren. Beiden Verfahren ist gemeinsam, daß sie versuchen, das gegebene Bild durch stückweise stetige Funktionen zu approximieren. Die maximalen Teilmengen des Definitionsbereichs, auf denen die approximierende Funktion stetig ist, bilden dann die Segmente. Im Gegensatz zu dem in der Literatur häufig unter dem Schlagwort Mumford-Shah-Modell bekannten Energieminimierungsverfahren ist der Raum der Funktionen, mit denen das Bild approximiert wird, bei der vektoriellen Mehrniveaupassung ein endlicher Vektorraum. Ein weiterer Unterschied zu diesem Ansatz ist das System der erlaubten Mengen. Es werden nur Segmentierungen erlaubt, deren Segmente aus diesem Mengensystem sind. Die durch diese Einschränkung schlankere Theorie führt zu einer gesicherten Existenz einer optimalen Lösung des Segmentierungsproblems, die der gängigen Vorstellung einer Segmentierung genügt. Die Berechnung lokaler Optima ist algorithmisch innerhalb der Theorie umsetzbar. KW - Bildsegmentierung KW - Mumford-Shah-Funktional KW - Approximation KW - Vektorielle Mehrniveaupassung KW - Energieminimierung KW - stückweise stetige Approximation Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-295 ER - TY - THES A1 - Fischer, Bernd T1 - Deduction-Based Software Component Retrieval T1 - Deduction-Based Software Component Retrieval N2 - Deduction-based software component retrieval is a software reuse technique that uses formal specifications as component descriptors and as search keys; matching components are identified using an automated theorem prover. This dissertation contains a detailed theoretical investigation of the concept as well as the first substantial experimental evaluation of its technical feasibility. N2 - Deduktionsbasiertes Kompenentenretrieval ist eine Softwarereusetechnik, in der formale Spezifikationen zur Beschreibung von Komponenten sowie als Anfragen verwendet werden; passende Komponenten werden mit Hilfe eines automatischen Theorembeweisers ermittelt. Diese Arbeit enthält eine detaillierte theoretische Untersuchung dieses Konzeptes und die erste ausführliche experimentelle Evaluierung seiner technischen Realisierbarkeit. KW - Software engineering KW - Komponente KW - Softwarewiederverwendung KW - Formale Spezifikationstechnik KW - Information Retrieval KW - Automatisches Beweis KW - software reuse KW - software component retrieval KW - automated theorem provingvng Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-231 ER - TY - THES A1 - Braumandl, Reinhard T1 - Quality of Service and Optimization in Data Integration Systems N2 - This work presents techniques for the construction of a global data integrations system. Similar to distributed databases this system allows declarative queries in order to express user-specific information needs. Scalability towards global data integration systems and openness were major design goals for the architecture and techniques developed in this work. It is shown how service composition, extensibility and quality of service can be supported in an open system of providers for data, functionality for query processing operations, and computing power. N2 - Diese Arbeit präsentiert Techniken für den Aufbau eines globalen Datenintegrationssystems. Analog zu verteilten Datenbanken unterstützt dieses System deklarative Anfragen, mit denen Benutzer die gesuchte Information beschreiben können. Die Skalierbarkeit in einem globalen Kontext und die Offenheit waren hauptsächliche Entwicklungsziele der Architektur und der Techniken, die in dieser Arbeit entstanden sind. Es wird gezeigt wie Dienstekomposition, Erweiterbarkeit und Dienstgüte in einem offenen System von Anbietern für Daten, Anfrageverarbeitungsfunktionalität und Rechenleistung unterstützt werden können. KW - Dienstgüte KW - Datenintegration KW - QoS KW - Anfrageauswertung KW - verteilte Systeme KW - mobiler Code KW - Java KW - verteilte Datenbanken KW - Anfrageoptimierung KW - offene Systeme KW - Skalierbarkeit Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-279 ER - TY - THES A1 - Mian Syed, Alexandra T1 - Engineering wissensbasierter Navigation und Steuerung autonom-mobiler Systeme N2 - Die autonome Steuerung mobiler, technischer Systeme in nicht exakt vorherbestimmbaren Situationen erfordert Methoden der autonomen Entscheidungsfindung, um ein planvolles, zielgerichtetes Agieren und Reagieren unter Echtzeitbedingungen realisieren zu können. Während mittels mathematischer Formeln Basisverhalten, wie beispielsweise in einer Geradeausbewegung, einer Drehung, bei einem Abbremsen, und in Gefahrenmomenten schnelle Reaktionen, berechnet werden, benötigt man auf der anderen Seite ein Regelsystem, um darüber hinaus "intelligentes", d.h. situationsangepaßtes Verhalten zu produzieren und gleichzeitig im Hinblick auf ein Missionsziel planvoll agieren zu können. Derartige Regelsysteme müssen sich auf einer abstrakten Ebene formulieren lassen, sollen sie vom Menschen problemlos entwickelbar, leicht modifizierbarund gut verifizierbar bleiben. Eine aufgrund ihres Konzeptes geeignete Programmierwelt ist die Logikprogrammierung. Ziel der Logikprogrammierung ist es weniger, Arbeitsabläufe zu beschreiben, als vielmehr Wissen in Form von Fakten zu spezifizieren und mit Hilfe von Regeln Schlußfolgerungen aus diesen Fakten ziehen zu können. Die klassische Logikprogrammierung ist jedoch aufgrund ihres Auswertungsmechanismus der SLD-Resolution (linear resolution with selected function for definite clauses) zu langsam für die Anwendung bei Echtzeitsystemen. Auch parallele Sprachformen, die ebenfalls mit SLD-Resolution arbeiten, erreichen beim Einsatz auf (von Neumann-) Mehrprozessorsystemen bislang nicht die notwendige Effizienz. Das Anwendungsgebiet der deduktiven Datenbanken hat im Vergleich dazu durch Bottom-Up Techniken einen anderen Auswertungsansatz mit deutlich höherer Effizienz geliefert. Viele dort auftretenden Probleme können jedoch nur durch die Integration anforderungsgetriebener Abarbeitung gelöst werden. Auf der anderen Seite stellen Datenflußrechnerarchitekturen aufgrund der automatisierten Ausbeutung feinkörniger Parallelität einen hervorragenden Ansatz der Parallelverarbeitung dar. Bei Datenflußrechnerarchitekturen handelt es sich um (Mehrprozessor-) Systeme, deren datengetriebener Abarbeitungsmechanismus sich grundlegend vom weit verbreiteten kontrollflußgesteuerten von Neumann-Prinzip unterscheidet.Überlegungen zur Struktur von Steuerungssystemen werden ergeben, daß es mittels Ansätzen aus dem Gebiet der deduktiven Datenbanken möglich ist, ein für diese Aufgabenstellung neuartiges, ausschließlich datengetriebenes Auswertungsmodell zu generieren. Dabei vermeidet es Probleme, die bei Bottom-Up Verfahren auftreten können, wie z.B. das Auftreten unendlicher Wertemengen und die späte Einschränkung auf relevante Werte, ohne gleichzeitig die Stratifizierung von Programmen zu gefährden. Ergebnis der Arbeit ist eine anwendungsbezogene, problemorientierte Entwicklungsumgebung, die einerseits die Entwicklung und Verifikation der Spezifikation mit existierenden Werkzeugen erlaubt und andererseits die effiziente, parallele Ausführung auf geeigneten Rechensystemen ermöglicht. Zusätzlich wird die Voraussetzung geschaffen, verschiedene weitere, für die Steuerung autonomer Systeme unverzichtbare Komponenten in das Abarbeitungsmodell zu integrieren. Simulationsergebnisse werden belegen, daß das vorgestellte Berechnungsmodell bezüglich realer Anwendungsbeispiele bereits in einer Monoprozessorversion Echtzeitbedingungen genügt. Damit ist die Voraussetzung für die Ausführung zukünftiger, weitaus komplexerer Steuerungsprobleme, ggf. auf Mehrprozessorsystemen, in Echtzeit geschaffen. KW - Autonomer Roboter KW - Navigation KW - Bahnsteuerung KW - Wissensbasiertes System KW - Echtzeitverarbeitung Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-159 ER - TY - THES A1 - Bachl, Sabine T1 - Isomorphe Subgraphen und deren Anwendung beim Zeichnen von Graphen N2 - In der Arbeit wird der Begriff der Isomorphen Subgraphen definiert. Anschließend werden theoretische und praktische Ergebnisse bei der Erkennung Isomorpher Graphen erörtert. N2 - In this theses, we introduce Isomophic Subgraphs and discuss the theoretical and practical issues of the detection of Isomophic Subgraphs and their use in graph drawing algorithms. KW - Isomorpher Teilgraph KW - Matching KW - NP-vollständiges Problem KW - Graphenzeichnen KW - Graph KW - Teilgraph KW - Isomorphie KW - Zeichnen KW - Isomorphism KW - Layout KW - Drawing Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-149 ER - TY - THES A1 - Zukowski, Ulrich T1 - Flexible Computation of the Well-Founded Semantics of Normal Logic Programs T1 - Flexible Computation of the Well-Founded Semantics of Normal Logic Programs N2 - The well-founded semantics has been accepted as the most relevant semantics for logic-based information systems. In this dissertation a framework based on a set of program transformations is presented that generalizes all major computation approaches for the well-founded semantics using a common data structure and provides a common language to describe their evaluation strategy. This rewriting system gives the formal background to analyze and combine different evaluation strategies in a common framework, or to design new algorithms and prove the correctness of its implementations at a high level just by changing the order of program transformations. N2 - Die wohlfundierte Semantik hat sich als eine der wichtigsten Semantiken für logische Regelsprachen herausgestellt. In dieser Dissertation wird ein Framework vorgestellt, das, basierend auf Programmtransformationen, eine einheitliche Datenstruktur und eine einheitliche Sprache zur Beschreibung von Auswertungsstrategien definiert und dadurch alle wichtigen Auswertungsverfahren für die wohlfundierte Semantik verallgemeinert. Das in dieser Dissertation vorgestellte Transformationssystem liefert die formalen Mittel, um unterschiedliche Auswertungsstrategien für die wohlfundierte Semantik analysieren und kombinieren zu können, oder um neue Algorithmen auf einem hohen Abstraktionsniveau durch Angabe regulärer Ausdrücke zu spezifizieren und deren Korrektheit beweisen zu können. KW - Logische Programmierung KW - Programmtransformation KW - Wohlfundierte Semantik KW - Logische Programme KW - Programmtransformation KW - Auswertungsstrategien KW - well-founded semantics KW - program transformations KW - Wohlfundierte Semantik Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-226 ER - TY - THES A1 - Börncke, Frank T1 - Modellierung syntaktischer Strukturen natürlicher Sprachen mit Graphgrammatiken N2 - Die vorliegende Arbeit erschließt durch die Formalisierung einer linguistischen Theorie Möglichkeiten zum Entwurf generischer Verfahren zur Verarbeitung natürlicher Sprachen. Zu diesem Zweck setzen wir Graphsprachen für die Modellierung syntaktischer Strukturen ein. Damit lassen sich Ergebnisse der linguistischen Forschung mit Begriffen der Graphentheorie beschreiben und bewerten. Zu diesem Ansatz motiviert der Umstand, daß in der Linguistik im Rahmen der Syntax jedem Satz einer natürlichen Sprache eine nichtsequentielle Struktur zugesprochen wird. Diese Struktur überlagert die lineare Wortfolge, die wir als Satz kennen. Eine Menge solcher syntaktischen Strukturen die wir mit Graphen modellieren können betrachten wir als Graphsprache. Die Arbeit zeigt, wie sich solche Graphsprachen mit Hilfe von Graphgrammatiken beschreiben lassen. Wie alle formalen Sprachen zeichnen sich auch Graphgrammatiken dadurch aus, daß sie mathematisch wohldefniert sind. Dies stellt eine notwendige Voraussetzung dar, um Aussagen über eine Sprache zu beweisen. Von Interesse ist dabei vor allem die Untersuchung unendlicher Mengen. Das Ziel besteht dann darin, für sie eine endliche Beschreibung zu finden. Diese Aufgabe wird in der Regel von einer Grammatik erfüllt. Darüber hinaus ist man an erkennenden Algorithmen für Sprachen interessiert, die das Wortproblem effizient lösen. Bezüglich natürlicher Sprachen werden beide Aufgabenstellungen in dieser Arbeit mit Hilfe von Graphgrammatiken gelöst. KW - Graphensprache KW - Syntaxbaum KW - Natürliche Sprache KW - Graph-Grammatik Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-28 ER - TY - THES A1 - Wichert, Carl-Alexander T1 - ULTRA - A Logic Transaction Programming Language N2 - Rule-based language for the specification of complex database updates and transactions. Formal treatment of the syntax and the declarative semantics N2 - Regelbasierte Sprache zur Spezifikation komplexer Datenbank-Operationen und Transaktionen. Formle Behandlung von Syntax und deklarativer Semantik. KW - Programmierlogik KW - Logische Programmiersprache KW - Datenbanksystem KW - Logikprogrammierung KW - ULTRA KW - logic programming KW - databases Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-105 ER - TY - THES A1 - Dolzmann, Andreas T1 - Algorithmic strategies for applicable real quantifier elimination N2 - One of the most important algorithms for real quantifier elimination is the quantifier elimination by virtual substitution introduced by Weispfenning in 1988. In this thesis we present numerous algorithmic approaches for optimizing this quantifier elimination algorithm. Optimization goals are the actual running time of the implementation of the algorithm and the size of the output formula. Strategies for obtaining these goals include simplification of first-order formulas,reduction of the size of the computed elimination set, and condensing a new replacement for the virtual substitution. Local quantifier elimination computes formulas that are equivalent to the input formula only nearby a given point. We can make use of this restriction for further optimizing the quantifier elimination by virtual substitution. Finally we discuss how to solve a large class of scheduling problems by real quantifier elimination. To optimize our algorithm for solving scheduling problems we make use of the special form of the input formula and of additional information given by the description of the scheduling problem N2 - Eines der bedeutendsten Verfahren zur reellen Quantorenelimination ist die Quantorenelimination mittels virtueller Substitution, die von Weispfenning 1988 eingeführt wurde. In der vorliegenden Arbeit werden zahlreiche algorithmische Strategien zur Optimierung dieses Verfahrens präsentiert. Optimierungsziele der Arbeit waren dabei die tatsächliche Laufzeit der Implementierung des Algorithmus sowie die Größe der Ausgabeformel. Zur Optimierung werden dabei die Simplifikation vonFormeln erster Stufe, die Reduktion der Größe der Eliminationsmenge sowie das Condensing, ein Ersatz für die virtuelle Substitution,untersucht. Lokale Quantorenelimination berechnet Formeln, die nur inder Nähe eines gegebenen Punktes äquivalent zur Eingabeformel ist. Diese Einschränkung erlaubt es, das Verfahren weiter zu verbessern.Als Anwendung des Eliminationsverfahren diskutieren wir abschließend, wie man eine große Klasse von Schedulingproblemen mittels reeller Quantorenelimination lösen kann. In diesem Fall benutzen wir die spezielle Struktur der Eingabeformel und zusätzliche Informationen über das Schedulingproblem, um die Quantorenelimination mittels virtueller Substitution problemspezifisch zu optimieren. KW - Quantorenelimination KW - Scheduling KW - Formeln erster Stufe KW - Quantifier elimination KW - scheduling KW - simplification KW - first-order formulas Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-64 ER - TY - THES A1 - Urban, Christoph T1 - Das Referenzmodell PECS - Agentenbasierte Modellierung menschlichen Handelns, Entscheidens und Verhaltens N2 - Die Agententechnologie hat in den letzten Jahren eine rasante Entwicklung erfahren und mittlerweile großen Einfluss auf verschiedene Bereiche in Wissenschaft und Technik genommen. Insbesondere wurde die agentenbasierte Modellbildung und Simulation als wirkungsvolles Mittel für die Untersuchung realer oder hypothetischer Systeme erkannt. Im Vordergrund stehen hierbei ganz besonders Systeme, die durch menschliches Handeln, Entscheiden und Verhalten beeinflusst werden, oder der Mensch selbst, um seine Eigenschaften und Fähigkeiten aus den Blickwinkeln unterschiedlicher wissenschaftlicher Disziplinen heraus weiterführend zu erforschen. Das primäre Ziel der vorliegenden Arbeit besteht darin, den Entwurf agenten-basierter Simulationsmodelle, in denen menschliches Handeln, Entscheiden und Verhalten von ausschlaggebender Bedeutung sind, auf konzeptioneller Ebene zu unterstützen. Um dieses Ziel zu erreichen, wird das domänen- und theorieunabhängige Referenzmodell PECS vorgestellt, das Strukturierungsprinzipien aus der Informatik mit systemtheoretischen Ansätzen verbindet, um das Wechselspiel vielfältiger Einflussbereiche auf das menschliche Handeln im Rahmen einer integrativen und umfassenden Agentenarchitektur abzubilden. Auf Grundlage des Referenzmodells werden insgesamt vier charakteristische Fallstudien aus der Psychologie, der Sozialpsychologie, der Soziologie und der experimentellen Ökonomie entwickelt, um den Einsatz des Referenzmodells in der Praxis zu demonstrieren. KW - Agent KW - Agent KW - Modellbildung KW - Computersimulation KW - Referenzmodell KW - Handlungstheorie KW - Agentenbasierte Simulation KW - Architekturmuster Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-471 ER - TY - THES A1 - Robschink, Torsten T1 - Pfadbedingungen in Abhängigkeitsgraphen und ihre Anwendung in der Softwaresicherheitstechnik N2 - Diese Arbeit präsentiert eine neue Methode zur Sicherheitsanalyse von Software im Bereich der Manipulationsprüfung und der Einhaltung von Informationsflüssen zwischen verschiedenen Sicherheitsniveaus. Program-Slicing und Constraint-Solving sind eigenständige Verfahren, die sowohl zur Abhängigkeitsbestimmung als auch zur Berechnung arithmetischer Eigenschaften verwendet werden. Die erstmalige Kombination dieser beiden Verfahren mittels Pfadbedingungen liefert nicht nur binäre Abhängigkeitsinformationen wie Slicing, sondern exakte notwendige Bedingungen über die Informationsflüsse zwischen zwei Programmpunkten. Neben der Definition der Grundlagen von Abhängigkeitsgraphen und einfachen Pfadbedingungen werden neue Erweiterungen für kontextsensitive interprozedurale Pfadbedingungen gezeigt und die Integration von domänenspezifischen Verfahren für Arrayfelder und abstrakten Datentypen demonstriert. Der Schwerpunkt der Arbeit liegt in der Realisierung von Pfadbedingungen für echte Programme in echten Programmiersprachen. Hierfür werden Verfahren vorgeschlagen, realisiert und empirisch untersucht, wie Pfadbedingungen für große Programme skalieren. Die zum Einsatz kommenden Techniken sind u.a. Intervallanalyse und Binäre Entscheidungsgraphen, mit denen die generelle exponentielle Komplexität von Pfadbedingungen beherrschbar wird. Fallstudien für den Einsatz von Pfadbedingungen und die empirische Untersuchung mehrerer Verfahren zur Intervallanalyse zeigen, dass Pfadbedingungen für die praktische Programmanalyse und das Programmverstehen geeignet und empfehlenswert sind. KW - Programmanalyse KW - Software Engineering KW - Reengineering / Software KW - Softwarewartung KW - Qualitätssicherung KW - Program-Slicing KW - Manipulationsprüfung KW - Informationsfluss KW - program analysis KW - program slicing KW - software reengineering KW - safety analysis KW - information flow Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-469 ER - TY - THES A1 - Seidl, Andreas T1 - Cylindrical Decomposition Under Application-Oriented Paradigms T1 - Zylindrische Dekomposition unter anwendungsorientierten Paradigmen N2 - Quantifier elimination (QE) is a powerful tool for problem solving. Once a problem is expressed as a formula, such a method converts it to a simpler, quantifier-free equivalent, thus solving the problem. Particularly many problems live in the domain of real numbers, which makes real QE very interesting. Among the so far implemented methods, QE by cylindrical algebraic decomposition (CAD) is the most important complete method. The aim of this thesis is to develop CAD-based algorithms, which can solve more problems in practice and/or provide more interesting information as output. An algorithm that satisfies these standards would concentrate on generic cases and postpone special and degenerated ones to be treated separately or to be abandoned completely. It would give a solution, which is locally correct for a region the user is interested in. It would give answers, which can provide much valuable information in particular for decision problems. It would combine these methods with more specialized ones, for subcases that allow for. It would exploit degrees of freedom in the algorithms by deciding to proceed in a way that promises to be efficient. It is the focus of this dissertation to treat these challenges. Algorithms described here are implemented in the computer logic system REDLOG and ship with the computer algebra system REDUCE. KW - Quantorenelimination KW - cylindrical algebraic decomposition KW - CAD KW - cylindrical subdecomposition KW - SCAD KW - quantifier elimination KW - QE Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-816 ER - TY - THES A1 - Ellmenreich, Nils T1 - PolyAPM: Comparative Parallel Programming with Abstract Parallel Machines T1 - PolyAPM: Vergleichende Parallelprogrammierung mit Abstrakten Parallelen Maschinen N2 - A parallelising compilation consists of many translation and optimisation stages. The programmer may steer the compiler through these stages by supplying directives with the source code or setting compiler switches. However, for an evaluation of the effects of individual stages, their selection and their best order, this approach is not optimal. To solve this problem, we propose the following method. The compilation is cast as a sequence of program transformations. Each intermediate program runs on an Abstract Parallel Machine (APM), while the program generated by the final transformation runs on the target architecture. Our intermediate programs are all in the same language, Haskell. Thus, each program is executable and still abstract enough to be legible, which enables the evaluation of the transformation that generated it. This evaluation is supported by a cost model, which makes a performance prediction of the abstract program for a real machine. Our project, PolyAPM, provides an acyclic directed graph -- usually a tree -- of APMs whose traversal specifies different combinations and orders of transformations. From one source program, several target programs can be constructed. Their run time characteristics can be evaluated and compared. The goal of PolyAPM is not to support the one-off construction of parallel application programs. For the method's overhead to pay off, the project aims rather at supporting the construction and comparison of many similar variations of a parallel program and a comparative evaluation of parallelisation techniques. With the automation of transformations, PolyAPM can also be used to construct semi-automatic compilation systems. N2 - Eine parallelisierende Compilation besteht aus vielen Übersetzungs- und Optimierungsstufen. Der Programmierer kann den Compiler in diesen Stufen steuern, in dem er im Quellcode Anweisungen einfügt oder Compileroptionen verwendet. Für eine Bewertung der Auswirkungen der einzelnen Stufen, der Auswahl der Stufen und ihrer besten Reihenfolge ist der Ansatz aber nicht geeignet. Um dieses Problem zu lösen, schlagen wir folgende Methode vor. Eine Compilation wird als Abfolge von Programmtransformationen betrachtet. Jedes Zwischenprogramm gehört jeweils zu einer Abstrakten Parallelen Maschine (APM), während das durch die letzte Transformation erzeugte Program für die Zielarchitektur bestimmt ist. Alle Zwischenprogramme sind in der Sprache Haskell geschrieben. Dadurch ist jedes Programm ausführbar und trotzdem abstrakt genug, um gut lesbar zu sein. Durch diese Ausführbarkeit kann die Transformation, durch die das Programm erzeugt wird, bewertet werden. Diese Bewertung wird durch ein Kostenmodell unterstützt, das eine Performance-Vorhersage des abstrakten Programms, bezogen auf eine reale Maschine, ermöglicht. Unser Projekt PolyAPM liefert einen azyklischen, gerichteten Graphen - in der Regel einen Baum - aus APMs, dessen Traversierungen jeweils bestimmte Kombinationen und Reihenfolgen von Transformationen definieren. Aus einem Quellprogramm können verschiedene Zielprogramme erzeugt werden, deren Laufzeitverhalten bewert- und vergleichbar ist. Das Ziel von PolyAPM liegt nicht in der Erzeugung eines einzelnen, parallelen Programms. Damit sich der zusätzliche Aufwand der Methode auszahlt, richtet sich das Projekt eher auf die Entwicklung und den Vergleich vieler, ähnlicher Variationen eines parallelen Programms und der vergleichenden Bewertung von Parallelisierungstechniken. Mit der Automatisierung von Transformationen kann PolyAPM dazu benutzt werden, halbautomatische Compilations-Systeme zu bauen. KW - Parallelverarbeitung KW - Funktionale Programmierung KW - Software Engineering KW - Schrittweise Verfeinerung KW - Parallelprogrammierung KW - Kostenmodell KW - parallel programming KW - software engineering KW - stepwise refinement KW - cost model Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-447 ER - TY - THES A1 - Forster, Michael T1 - Crossings in Clustered Level Graphs T1 - Kreuzungen in Cluster-Level-Graphen N2 - Clustered graphs are an enhanced graph model with a recursive clustering of the vertices according to a given nesting relation. This prime technique for expressing coherence of certain parts of the graph is used in many applications, such as biochemical pathways and UML class diagrams. For directed clustered graphs usually level drawings are used, leading to clustered level graphs. In this thesis we analyze the interrelation of clusters and levels and their influence on edge crossings and cluster/edge crossings. N2 - Cluster-Graphen sind ein erweitertes Graph-Modell mit einem rekursiven Clustering der Knoten entsprechend einer gegebenen Inklusionsrelation. Diese bedeutende Technik um Zusammengehörigkeit bestimmter Teile des Graphen auszudrücken wird in vielen Anwendungen benutzt, etwa biochemischen Reaktionsnetzen oder UML Klassendiagrammen. Für gerichtete Cluster-Graphen werden üblicherweise Level-Zeichnungen verwendet, was zu Cluster-Level-Graphen führt. Diese Arbeit analysiert den Zusammenhang zwischen Clustern und Level und deren Auswirkungen auf Kantenkreuzungen und Cluster/Kanten-Kreuzungen. KW - Graphenzeichnen KW - Azyklischer gerichteter Graph KW - Cluster KW - Kreuzung KW - Minimierung KW - Planarer Graph KW - Constraint-Erfüllung KW - Kreuzungszahl KW - graph drawing KW - directed acyclic graph KW - cluster KW - crossing KW - minimization KW - planar graph KW - constraint KW - crossing number Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-481 ER - TY - THES A1 - Schreiber, Falk T1 - Visualisierung biochemischer Reaktionsnetze N2 - In dieser Arbeit werden Anforderungen an die Darstellung biochemischer Reaktionsnetze untersucht und die Netze unter dem Gesichtspunkt der Visualisierung modelliert. Anschliessend wird ein Algorithmus zum Zeichnen biochemischer Reaktionsnetze entwickelt und analysiert. N2 - In this dissertation we investigate the requirements for the visualisation of biochemical reaction networks. We compose a model for these networks that lends itself to visualisation and develop and analyse an algorithm to create drawings of the networks. KW - Biochemie KW - Reaktionssystem KW - Graph KW - Visualisierung KW - Biochemische Reaktion KW - Computergraphik Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-215 ER - TY - THES A1 - Hofmeier, Andreas T1 - Vergleichen und Aggregieren von partiellen Ordnungen N2 - Das Vergleichen und Aggregieren von Informationen ist ein zentraler Bereich in der Analyse von Wahlsystemen. In diesen müssen die verschiedenen Meinungen von Wählern über eine Menge von Kandidaten zu einem möglichst gerechten Wahlergebnis aggregiert werden. In den meisten politischen Wahlen entscheidet sich jeder Wähler durch Ankreuzen für einen einzigen Kandidaten. Daneben werden aber auch Rangordnungsprobleme als eine Variante von Wahlsystemen untersucht. Bei diesen bringt jeder Wähler seine Meinung in Form einer totalen Ordnung über der Menge der Kandidaten zum Ausdruck, wodurch seine oftmals komplexe Meinung exakter repräsentiert werden kann als durch die Auswahl eines einzigen, favorisierten Kandidaten. Das Wahlergebnis eines Rangordnungsproblems ist dann eine ebenfalls totale Ordnung der Kandidaten, welche die geringste Distanz zu den Meinungen der Wähler aufweist. Als Distanzmaße zwischen zwei totalen Ordnungen haben sich neben anderen Kendalls Tau-Distanz und Spearmans Footrule-Distanz etabliert. Durch moderne Anwendungsmöglichkeiten von Rangordnungsproblemen im maschinellen Lernen, in der künstlichen Intelligenz, in der Bioinformatik und vor allem in verschiedenen Bereichen des World Wide Web rücken bereits bekannte, jedoch bislang eher wenig studierte Aspekte in den Fokus der Forschung. Zum einen gewinnt die algorithmische Komplexität von Rangordnungsproblemen an Bedeutung. Zum anderen existieren in vielen dieser Anwendungen unvollständige „Wählermeinungen“ mit unentschiedenen oder unvergleichbaren Kandidaten, so dass totale Ordnungen zu deren Repräsentation nicht länger geeignet sind. Die vorliegende Arbeit greift diese beiden Aspekte auf und betrachtet die algorithmische Komplexität von Rangordnungsproblemen, in denen Wählermeinungen anstatt durch totale Ordnungen durch schwache oder partielle Ordnungen repräsentiert werden. Dazu werden Kendalls Tau-Distanz und Spearmans Footrule-Distanz auf verschiedene nahe liegende Arten verallgemeinert. Es zeigt sich dabei, dass nun bereits die Distanzberechnung zwischen zwei Ordnungen ein algorithmisch komplexes Problem darstellt. So ist die Berechnung der verallgemeinerten Versionen von Kendalls Tau-Distanz oder Spearmans Footrule-Distanz für schwache Ordnungen noch effizient möglich. Sobald jedoch partielle Ordnungen betrachtet werden, sind die Probleme NP-vollständig, also vermutlich nicht mehr effizient lösbar. In diesem Fall werden Resultate zur Approximierbarkeit und zur parametrisierten Komplexität der Probleme vorgestellt. Auch die Komplexität der Rangordnungsprobleme selbst erhöht sich. Für totale Ordnungen effizient lösbare Varianten werden für schwache Ordnungen NP-vollständig, für totale Ordnungen NP-vollständige Varianten hingegen liegen für partielle Ordnungen teilweise außerhalb der Komplexitätsklasse NP. Die Arbeit schließt mit einem Ausblick auf offene Problemstellungen. KW - Rangordnungsproblem KW - Distanzproblem KW - Kendalls Tau-Distanz KW - Spearmans Footrule-Distanz KW - partielle Ordnung KW - rank aggregation problem KW - distance problem KW - Kendall tau distance KW - Spearman footrule distance KW - partial order Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-26858 ER - TY - THES A1 - Matzeder, Marco T1 - Zeichnen von Bäumen auf Gittern T1 - Drawing Trees on Grids N2 - Das Zeichnen von Graphen beschäftigt sich mit der Frage, wie die durch einen Graphen repräsentierten Informationen für einen Betrachter übersichtlich und verständlich dargestellt werden können. Die Graphklasse der Bäume dient insbesondere zur Repräsentation von hierarchischen Strukturen. Neben den hierarchisch und radial darstellenden Verfahren werden Bäume auch auf dem orthogonalen Gitter gezeichnet, in welchem die Knoten auf ganzzahligen Koordinaten liegen und die Kanten entlang der horizontalen und vertikalen Gitterlinien verlaufen. Gewünscht wird eine gute Lesbarkeit der Zeichnungen und deren effiziente Berechnung. Für die formale Bewertung der Lesbarkeit existieren speziell für das Zeichnen von Bäumen definierte Ästhetikkriterien, wie eine ebenenweise Darstellung, die Ordnungserhaltung und Kriterien zur Darstellung von Subgraphisomorphien und Symmetrien. Die vorliegende Arbeit befasst sich mit einer bislang wenig studierten Erweiterung des orthogonalen Gitters auf das hexagonale und oktagonale Gitter durch das Hinzunehmen von einer bzw. beider diagonalen Gitterrichtungen, und der Problemstellung, wie Bäume darauf gezeichnet werden. Dadurch können auch Bäume mit einem höheren Grad gezeichnet werden als auf dem orthogonalen Gitter. Die Einschränkung, dass nur Bäume gezeichnet werden können, deren Grad kleiner ist als die Anzahl der Gitterrichtungen des verwendeten Gitters, besteht jedoch weiterhin. Als Ästhetikkriterien werden die lokale Uniformität, die die Länge der ausgehenden Kanten eines Knotens festlegt, und Pattern, die deren Richtungen festlegen, eingeführt. Gegenüber dem bekannten linearen Flächenverbrauch von geradlinigen Zeichnungen von vollständigen Binärbäumen auf dem orthogonalen Gitter, werden für Zeichnungen von vollständigen d-nären Bäumen mit d > 2 nicht-lineare untere Schranken für die benötigte Fläche auf dem hexagonalen und dem oktagonalen Gitter gezeigt. Insgesamt werden für vollständige und beliebige, geordnete und ungeordnete Bäume obere und untere Flächenschranken für Zeichnungen auf dem hexagonalen und oktagonalen Gitter präsentiert. Dabei zeigt sich, dass bei nicht-ordnungserhaltenden Zeichnungen zwar mehr als lineare, aber deutlich weniger als quadratische Fläche benötigt wird. Im Gegensatz dazu gibt es geordnete Bäume, deren ordnungserhaltende Zeichnungen exponentielle Fläche benötigen. Des Weiteren wird die Ermittlung der minimalen Zeichenfläche für geordnete d-näre Bäume ebenso als NP-vollständig bewiesen, wie das Zeichnen von ungeordneten d-nären Bäumen mit einheitlichen Kantenlängen. Schließlich werden zwei Linearzeitalgorithmen vorgestellt, die geordnete d-näre Bäume unter Einhaltung der genannten Ästhetikkriterien zeichnen. KW - Baum KW - Wald KW - Graph KW - Gittereinbettung KW - Graphenzeichnen KW - Gitter KW - Sweep-Algorithmus KW - Rekursiver Algorithmus KW - Baumzeichnung KW - Orthogonales Gitter KW - Hexagonales Gitter KW - Oktagonales Gitter KW - ordnungserhaltend KW - lokale Uniformität KW - Tree Drawing KW - Grid KW - ordered KW - unordered Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-26923 ER - TY - THES A1 - EL-Khoury, Vanessa T1 - Semantic Protection and Personalization of Video Content. PIAF: MPEG Compliant Adaptation Framework Preserving the User Perceived Quality T1 - Semantischer Schutz und Personalisierung von Videoinhalten. PIAF: MPEG-kompatibles Multimedia-Adaptierungs-Framework zur Bewahrung der vom Nutzer wahrgenommenen Qualität. N2 - UME is the notion that a user should receive informative adapted content anytime and anywhere. Personalization of videos, which adapts their content according to user preferences, is a vital aspect of achieving the UME vision. User preferences can be translated into several types of constraints that must be considered by the adaptation process, including semantic constraints directly related to the content of the video. To deal with these semantic constraints, a fine-grained adaptation, which can go down to the level of video objects, is necessary. The overall goal of this adaptation process is to provide users with adapted content that maximizes their Quality of Experience (QoE). This QoE depends at the same time on the level of the user's satisfaction in perceiving the adapted content, the amount of knowledge assimilated by the user, and the adaptation execution time. In video adaptation frameworks, the Adaptation Decision Taking Engine (ADTE), which can be considered as the "brain" of the adaptation engine, is responsible for achieving this goal. The task of the ADTE is challenging as many adaptation operations can satisfy the same semantic constraint, and thus arising in several feasible adaptation plans. Indeed, for each entity undergoing the adaptation process, the ADTE must decide on the adequate adaptation operator that satisfies the user's preferences while maximizing his/her quality of experience. The first challenge to achieve in this is to objectively measure the quality of the adapted video, taking into consideration the multiple aspects of the QoE. The second challenge is to assess beforehand this quality in order to choose the most appropriate adaptation plan among all possible plans. The third challenge is to resolve conflicting or overlapping semantic constraints, in particular conflicts arising from constraints expressed by owner's intellectual property rights about the modification of the content. In this thesis, we tackled the aforementioned challenges by proposing a Utility Function (UF), which integrates semantic concerns with user's perceptual considerations. This UF models the relationships among adaptation operations, user preferences, and the quality of the video content. We integrated this UF into an ADTE. This ADTE performs a multi-level piecewise reasoning to choose the adaptation plan that maximizes the user-perceived quality. Furthermore, we included intellectual property rights in the adaptation process. Thereby, we modeled content owner constraints. We dealt with the problem of conflicting user and owner constraints by mapping it to a known optimization problem. Moreover, we developed the SVCAT, which produces structural and high-level semantic annotation according to an original object-based video content model. We modeled as well the user's preferences proposing extensions to MPEG-7 and MPEG-21. All the developed contributions were carried out as part of a coherent framework called PIAF. PIAF is a complete modular MPEG standard compliant framework that covers the whole process of semantic video adaptation. We validated this research with qualitative and quantitative evaluations, which assess the performance and the efficiency of the proposed adaptation decision-taking engine within PIAF. The experimental results show that the proposed UF has a high correlation with subjective video quality evaluation. N2 - Der Begriff "Universal Multimedia Experience" (UME) beschreibt die Vision, dass ein Nutzer nach seinen individuellen Vorlieben zugeschnittene Videoinhalte konsumieren kann. In dieser Dissertation werden im UME nun auch semantische Constraints berücksichtigt, welche direkt mit der Konsumierung der Videoinhalte verbunden sind. Dabei soll die Qualität der Videoerfahrung für den Nutzer maximiert werden. Diese Qualität ist in der Dissertation durch die Benutzerzufriedenheit bei der Wahrnehmung der Veränderung der Videos repräsentiert. Die Veränderung der Videos wird durch eine Videoadaptierung erzeugt, z.B. durch die Löschung oder Veränderung von Szenen, Objekten, welche einem semantischen Constraints nicht entsprechen. Kern der Videoadaptierung ist die "Adaptation Decision Taking Engine" (ADTE). Sie bestimmt die Operatoren, welche die semantischen Constraints auflösen, und berechnet dann mögliche Adaptierungspläne, die auf dem Video angewandt werden sollen. Weiterhin muss die ADTE für jeden Adaptierungsschritt anhand der Operatoren bestimmen, wie die Vorlieben des Nutzers berücksichtigt werden können. Die zweite Herausforderung ist die Beurteilung und Maximierung der Qualität eines adaptierten Videos. Die dritte Herausforderung ist die Berücksichtigung sich widersprechender semantischer Constraints. Dies betrifft insbesondere solche, die mit Urheberrechten in Verbindung stehen. In dieser Dissertation werden die oben genannten Herausforderungen mit Hilfe eines "Personalized video Adaptation Framework" (PIAF) gelöst, welche auf den "Moving Picture Expert Group" (MPEG)-Standard MPEG-7 und MPEG-21 basieren. PIAF ist ein Framework, welches den gesamten Prozess der Videoadaptierung umfasst. Es modelliert den Zusammenhang zwischen den Adaptierungsoperatoren, den Vorlieben der Nutzer und der Qualität der Videos. Weiterhin wird das Problem der optimalen Auswahl eines Adaptierungsplans für die maximale Qualität der Videos untersucht. Dafür wird eine Utility Funktion (UF) definiert und in der ADTE eingesetzt, welche die semantischen Constraints mit den vom Nutzer ausgedrückten Vorlieben vereint. Weiterhin ist das "Semantic Video Content Annotation Tool" (SVCAT) entwickelt worden, um strukturelle und semantische Annotationen durchzuführen. Ebenso sind die Vorlieben der Nutzer mit MPEG-7 und MPEG-21 Deskriptoren berücksichtigt worden. Die Entwicklung dieser Software-Werkzeuge und Algorithmen ist notwendig, um ein vollständiges und modulares Framework zu erhalten. Dadurch deckt PIAF den kompletten Bereich der semantischen Videoadaptierung ab. Das ADTE ist in qualitativen und quantitativen Evaluationen validiert worden. Die Ergebnisse der Evaluation zeigen unter anderem, dass die UF im Bereich Qualität eine hohe Korrelation mit der subjektiven Wahrnehmung von ausgewählten Nutzern aufweist. KW - MPEG-Standard KW - Multimedia KW - Wahrnehmung KW - Personalisierung von Videos KW - semantische Adaptierung KW - Inhaltsadaptierung KW - Quality of Experience KW - Universal Multimedia Experience KW - Personalization of Videos KW - Semantic Content Adaptation KW - Quality of Experience KW - User Perception KW - Utility Functon Model Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-27360 ER - TY - THES A1 - Mian Syed, Ahmed T1 - Eine ökonomische statische Analysemethode zur Berechnung von Relational Attributes mittels regulärer Pfadbedingungen und ihre Anwendung auf Zeigeranalyse N2 - Ziel der Arbeit ist es, eine neue Programmanalysetechnik für Zeigeranalyse zu entwickeln. Diese soll exakt in dem Sinne sein, daß sie nur Ergebnisse berechnet, die tatsächlich in realen Programmläufen vorkommen können, Ebenso soll diese Analysetechnik ökonomisch sein, d.h. nur den minimal für eine exakte Lösung benötigten Berechnungsaufwand investieren müssen. KW - Softwareproduktion KW - Programmanalyse KW - CASHE Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-333 ER - TY - THES A1 - Weitl, Franz T1 - Document Verification with Temporal Description Logics T1 - Dokumentverifikation mit Temporaler Beschreibungslogik N2 - The thesis proposes a new formal framework for checking the content of web documents along individual reading paths. It is vital for the readability of web documents that their content is consistent and coherent along the possible browsing paths through the document. Manually ensuring the coherence of content along the possibly huge number of different browsing paths in a web document is time-consuming and error-prone. Existing methods for document validation and verification are not sufficiently expressive and efficient. The innovative core idea of this thesis is to combine the temporal logic CTL and description logic ALC for the representation of consistency criteria. The resulting new temporal description logics ALCCTL can - in contrast to existing specification formalisms - compactly represent coherence criteria on documents. Verification of web documents is modelled as a model checking problem of ALCCTL. The decidability and polynomial complexity of the ALCCTL model checking problem is proven and a sound, complete, and optimal model checking algorithm is presented. Case studies on real and realistic web documents demonstrate the performance and adequacy of the proposed methods. Existing methods such as symbolic model checking or XML-based document validation are outperformed in both expressiveness and speed. N2 - Die Dissertation stellt ein neues formales Framework für die automatische Prüfung inhaltlich-struktureller Konsistenzkriterien an Web-Dokumente vor. Viele Informationen werden heute in Form von Web-Dokumenten zugänglich gemacht. Komplexe Dokumente wie Lerndokumente oder technische Dokumentationen müssen dabei vielfältige Qualitätskriterien erfüllen. Der Informationsgehalt des Dokuments muss aktuell, vollständig und in sich stimmig sein. Die Präsentationsstruktur muss unterschiedlichen Zielgruppen mit unterschiedlichen Informationsbedürfnissen genügen. Die Sicherstellung grundlegender Konsistenzeigenschaften von Dokumenten ist angesichts der Vielzahl der Anforderungen und Nutzungskontexte eines elektronischen Dokuments nicht trivial. In dieser Arbeit werden aus der Hard-/Softwareverifikation bekannte Model-Checking-Verfahren mit Methoden zur Repräsentation von Ontologien kombiniert, um sowohl die Struktur des Dokuments als auch inhaltliche Zusammenhänge bei der Prüfung von Konsistenzkriterien berücksichtigen zu können. Als Spezifikationssprache für Konsistenzkriterien wird die neue temporale Beschreibungslogik ALCCTL vorgeschlagen. Grundlegende Eigenschaften wie Entscheidbarkeit, Ausdruckskraft und Komplexität werden untersucht. Die Adäquatheit und Praxistauglichkeit des Ansatzes werden in Fallstudien mit eLearning-Dokumenten evaluiert. Die Ergebnisse übertreffen bekannte Ansätze wie symbolisches Model-Checking oder Methoden zur Validierung von XML-Dokumenten in Performanz, Ausdruckskraft hinsichtlich der prüfbaren Kriterien und Flexibilität hinsichtlich des Dokumenttyps und -formats. KW - Verifikation KW - Model Checking KW - Temporale Logik KW - Terminologische Logik KW - Schlussfolgern KW - Formale Ontologie KW - Konsistenz KW - Widerspruchsf KW - Dokumentprüfung KW - Dokumentvalidierung KW - Dokumentverifikation KW - CTL KW - computation tree logic KW - Dokumentmodell KW - pfadbasierte Konsistenz KW - document verification KW - path-based consistency KW - coherence KW - temporal description logic KW - model checking Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-12528 ER - TY - THES A1 - Schwaiger, Petra T1 - Ein Bedingungsmodell für Planungsprobleme in strukturierten Domänen N2 - Computerunterstützte Beratungssysteme finden sowohl in der Industrie als auch im akademischen Bereich eine zunehmende Bedeutung. Die Anforderungen an solche Systeme sind hinsichtlich der abbildbaren Strukturen, der Flexibilität der Anfragen und der Vollständigkeit und Korrektheit der Antworten hoch. Dies gilt insbesondere für Planungsprobleme in strukturierten Domänen. Derartige Probleme treten beispielsweise bei der Erstellung von Tests auf der Grundlage einer Menge von Fragen und gewissen Anforderungen an den Test, bei der Konsistenzprüfung von Studienordnungen und bei der computerunterstützten Studienberatung auf. In der vorliegenden Arbeit wird ein Framework zur Behandlung eben genannter Probleme präsentiert. Die vorgestellte Lösung bietet durch den modellbasierten Ansatz und die entwickelte anwendungsnahe Modellierungssprache – gerade auch im Vergleich zu existierenden Ansätzen – einen sehr hohen Grad an Abstraktion, Allgemeingültigkeit, Ausdrucksstärke, Flexibilität und Integrierbarkeit. Im Rahmen des entwickelten Modells wird eine geeignete Verzahnung von strukturellen und constraintbasierten Aspekten erreicht. Der hierbei in Syntax und Semantik definierte Constraintbegriff kann darüber hinaus als Formalisierung und Verallgemeinerung von Pfadconstraints bzw. Pfadanfragen in hierarchischen Datenmodellen aufgefasst werden. Für die interne Repräsentation erweist sich ein logikbasierter Ansatz mit Constraints, nämlich Answer Set Programming mit Gewichten, als eine ausgezeichnete Methode bezüglich der Ausdrucksstärke, Mächtigkeit und Adäquatheit. Die Praxistauglichkeit des verfolgten Ansatzes im Hinblick auf Performanz und Skalierbarkeit wird in verschiedenen realen Anwendungsfällen demonstriert. KW - Logik KW - Beratungssystem KW - Modellierung KW - Answer Set Programming KW - Baumconstraint KW - Pfadconstraint KW - strukturierte Domäne KW - Answer Set Programming KW - structured domain KW - tree constraint KW - path constraint KW - recommender system Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-12497 ER - TY - THES A1 - Graf, Simone T1 - Kamerakalibrierung mit radialer Verzeichnung – die radiale essentielle Matrix T1 - Camera Calibration with Radial Distortion - the Radial Essential Matrix N2 - In der Bildverarbeitung wird die beobachtende Kamera meist als Lochkamera modelliert: ein Modell, das zahlreiche theoretische Vorteile bietet. So kann etwa das Abbildungsverhalten als projektive Abbildung aufgefasst werden. In einem Stereokamerasystem dieses Modells stehen korrespondierende Punkte – das sind Bildpunkte desselben 3D-Punktes – in einem linearen Zusammenhang, der auch ohne Kenntnis der Kameraparameter aus beobachteten Korrespondenzen geschätzt werden kann. Für die meisten Kameras, insbesondere für solche mit Weitwinkelobjektiven, ist die Modellannahme einer Lochkamera allerdings sichtbar unzureichend. Deshalb müssen zusätzlich zur Lochkamera noch Verzeichnungsabbildungen ins Modell integriert werden. In dieser Arbeit wird gezeigt, dass bei polynomialer radialer Verzeichnung die Parameter der Projektionsabbildung die Verzeichnungsparameter bestimmen. Dieses theoretische Ergebnis fließt in Algorithmen zur Kamerakalibrierung, d.h. zur Bestimmung der Parameter eines Kameramodells, ein. Diese wurden experimentell getestet und mit bestehenden Verfahren verglichen. Weiterhin wird die radiale essentielle Matrix eingeführt, die die Beziehung von korrespondierenden Punkten im Stereokamerafall bei radialer Verzeichnung beschreibt. Es werden vier Algorithmen vorgestellt, die diese theoretische Beziehung verwerten. Sie geben an, wie aus korrespondierenden Punkten die radiale essentielle Matrix geschätzt werden kann und welche Kameraparameter daraus gewonnen werden können. Damit ist beispielsweise eine Nachkalibrierung möglich. Auch diese Verfahren wurden implementiert und evaluiert. Umgekehrt ist bei bekannter radialer essentieller Matrix eine Einschränkung des Suchraums für korrespondierende Punkte möglich, die für die Rekonstruktion benötigt werden. KW - Optische Messtechnik KW - Kalibrieren KW - Stereokamera KW - Kamera KW - Korrespondenzproblem KW - Bildverarbeitung KW - Bildkorrelatio KW - Kamerakalibrierung KW - radiale Verzeichnung KW - epipolare Einschränkung KW - camera calibration KW - radial distortion KW - epipolar constraint Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-12711 ER - TY - INPR A1 - Kreitmeier, Wolfgang T1 - Optimal quantization for uniform distributions on Cantor-like sets N2 - In this paper, the problem of optimal quantization is solved for uniform distributions on some higher dimensional, not necessarily self-similar $N-$adic Cantor-like sets. The optimal codebooks are determined and the optimal quantization error is calculated. The existence of the quantization dimension is characterized and it is shown that the quantization coefficient does not exist. The special case of self-similarity is also discussed. The conditions imposed are a separation property of the distribution and strict monotonicity of the first $N$ quantization error differences. Criteria for these conditions are proved and as special examples modified versions of classical fractal distributions are discussed. KW - Maßtheorie KW - Quantisierung KW - Iteriertes Funktionensystem KW - Fraktale Dimension KW - optimal quantization KW - quantization dimension KW - quantization coefficient KW - self-similar probabilities Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-12449 ER - TY - THES A1 - Guppenberger, Michael T1 - Enhancing Information Systems with Event-Handling - A Non-Invasive Approach T1 - Erweiterung von Informationssystemen um Event-Handling - Ein Nicht-Invasiver Ansatz N2 - Due to the immense advance of widely accessible information systems in industrial applications, science, education and every day use, it becomes more and more difficult for users of those information systems to keep track with new and updated information. An approach to cope with this problem is to go beyond traditional search facilities and instead use the users' profiles to monitor data changes and to actively inform them about these updates - an aspect that has to be explicitly developed and integrated into a variety of information systems. This is traditionally done in an individual way, depending on the application and its platform. In this dissertation, we present a novel approach to model the semantic interrelations that specify which users to inform about which updates, based on the underlying model of the respective information system. For the first time, a meta-model that allows information system designers to tag an arbitrary data model and thus specify the event-handling semantics is presented. A formal specification of how to interpret meta-models to determine the receivers of the events completes the presented concept. For the practical realization of this new concept, model driven architecture (MDA) shows to be an ideal technical means. Using our newly developed UML profile based on data-modelling standards, an implementation of the event-handling specification can automatically be generated for a variety of different target platforms, like e.g. relational databases, using triggers. This meta-approach makes the proposed solution ideal with respect to maintainability and genericity. Our solution significantly reduces the overall development efforts for an event-handling facility. In addition, the enhanced model of the information system can be used to generate an implementation that also fulfils non-functional requirements like high performance and extensibility. The overall framework, consisting of the domain specific language (i.e. the meta-model), formal and technical transformations of how to interpret the enhanced information system model and a cost-based optimizing strategy, constitutes an integrated approach, offering several advantages over traditional implementation techniques: our framework can be applied to new information systems as well as to legacy applications without having to modify existing systems; it offers an extensible, easy-to-use, generic and thus re-usable solution and it can be tailored to and optimized for many use cases, as the practical evaluation presented in this dissertation verifies. N2 - Bedingt durch die immer stärkere Durchdringung rechnergestützter Informationssysteme in Industrie, Forschung, Ausbildung und anderen Bereichen des täglichen Lebens wird es für Anwender immer schwieriger, für sie relevante Änderungen an den dort gespeicherten Datenbeständen nachzuverfolgen. Dem wird häufig dadurch begegnet, dass über die Fähigkeiten traditioneller Suchmöglichkeiten hinaus gegangen wird und Profile der Anwender verwendet werden, um sie aktiv über relevante Änderungen zu informieren. Dieser Aspekt muss für unterschiedlichste Informationssysteme explizit entwickelt und integriert werden, zudem meist abhängig von der fachlichen Domäne der Anwendung und deren Plattform. In dieser Dissertation präsentieren wir einen neuartigen Ansatz, mit dessen Hilfe die semantischen Vorgaben, welche Anwender über welche Änderungen informiert werden sollen, ausgehend vom zugrunde liegenden Datenmodell der Anwendung des jeweiligen Systems modelliert werden können. Erstmalig wird ein Meta-Modell vorgestellt, das Entwicklern und Architekten ermöglicht, ein beliebiges Modell eines Informationssystems mit zusätzlichen Informationen auszuzeichnen und damit die Semantik der Event-Handling-Komponente vorzugeben. Zudem wird ein formales Konzept präsentiert, das spezifiziert wie diese Auszeichnungen für die Bestimmung der Informationsempfänger zu interpretieren sind. Im Hinblick auf die Realisierung dieses Konzepts erweist sich Model Driven Architecture (MDA) als ideales technisches Mittel. Mit Hilfe eines eigens entwickelten UML Profils, das sich auf existierende Standards zur Datenmodellierung stützt, kann automatisch eine Implementierung der Event-Handling-Komponenten für eine Vielzahl unterschiedlichster Zielplattformen generiert werden. Als Beispiel wäre die Verwendung relationaler Datenbanken zusammen mit Datenbanktriggern zu nennen. Dieser Ansatz stellt eine ideale Lösung im Hinblick auf Wartbarkeit und Allgemeingültigkeit dar, wodurch auch der Entwicklungsaufwand minimiert wird. Zudem bietet unser Ansatz auch die Möglichkeit, bei der Implementierung dieser Komponente auch nicht-funktionale Anforderungen - wie beispielsweise möglichst optimale Performanz und Erweiterbarkeit - zu erfüllen. Das hier präsentierte Framework, bestehend aus der domänen-spezifischen Sprache (in Form des Meta-Modells), den formalen und technischen Transformationsvorschriften für die Interpretation der Spezifikation sowie einer kostenbasierten Optimierungsstrategie, stellt einen integrierten Ansatz dar, der im Vergleich zu traditionellen Ansätzen einige Vorteile bietet: so kann dieser Ansatz ohne Modifikation existierender Systeme verwendet werden, stellt eine erweiterbare, einfach benutzbare, und zugleich wiederverwendbare Lösung dar und kann für beliebige Anwendungsfälle maßgeschneidert und optimiert werden, wie die Evaluation unserer Lösung anhand echter Szenarien in dieser Dissertation zeigt. KW - Notifikation KW - Abonnement KW - Modellierung KW - Generierung KW - Relationale Datenbank KW - MDA KW - Trigger KW - Aktive Datenbanken KW - Metamodellierung KW - Publish/Subscribe KW - Publish/Subscribe KW - Notification KW - Active Database Systems KW - MDA KW - Trigger Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-22485 ER - TY - THES A1 - Berl, Andreas T1 - Energy Efficiency in Office Computing Environments T1 - Energieeffizienz in Büroumgebungen N2 - The increasing cost of energy and the worldwide desire to reduce CO2 emissions has raised concern about the energy efficiency of information and communication technology. Whilst research has focused on data centres recently, this thesis identifies office computing environments as significant consumers of energy. Office computing environments offer great potential for energy savings: On one hand, such environments consist of a large number of hosts. On the other hand, these hosts often remain turned on 24~hours per day while being underutilised or even idle. This thesis analyzes the energy consumption within office computing environments and suggests an energy-efficient virtualized office environment. The office environment is virtualized to achieve flexible virtualized office resources that enable an energy-based resource management. This resource management stops idle services and idle hosts from consuming resources within the office and consolidates utilised office services on office hosts. This increases the utilisation of some hosts while other hosts are turned off to save energy. The suggested architecture is based on a decentralized approach that can be applied to all kinds of office computing environments, even if no centralized data centre infrastructure is available. The thesis develops the architecture of the virtualized office environment together with an energy consumption model that is able to estimate the energy consumption of hosts and network within office environments. The model enables the energy-related comparison of ordinary and virtualized office environments, considering the energy-efficient management of services. Furthermore, this thesis evaluates energy efficiency and overhead of the suggested approach. First, it theoretically proves the energy efficiency of the virtualized office environment with respect to the energy consumption model. Second, it uses Markov processes to evaluate the impact of user behaviour on the suggested architecture. Finally, the thesis develops a discrete-event simulation that enables the simulation and evaluation of office computing environments with respect to varying virtualization approaches, resource management parameters, user behaviour, and office equipment. The evaluation shows that the virtualized office environment saves more than half of the energy consumption within office computing environments, depending on user behaviour and office equipment. N2 - Die steigenden Kosten von Energie und die weltweiten Bemühungen CO2-Emmissionen zu reduzieren, führt aktuell zu einer intensiven Untersuchung der Energieeffizienz von Informations- und Kommunikationstechnologien. Während ein großer Teil der aktuellen Forschung sich auf Rechenzentren fokussiert, betrachtet diese Arbeit Büroumgebungen mit ihren Rechnern und dem verbindenden Netzwerk. Eine energieeffiziente Architektur wird vorgeschlagen, die auf die Virtualisierung und Konsolidierung von Diensten setzt, ohne auf zentralisierte Rechenzentrumshardware oder Thin Clients angewiesen zu sein. KW - Energieeffizienz KW - Virtualisierung KW - Konsolidierung KW - Büro KW - Energy efficiency KW - virtualization KW - consolidation KW - office computing environments Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-22516 ER - TY - INPR A1 - Kreitmeier, Wolfgang T1 - Optimal vector quantization in terms of Wasserstein distance N2 - The optimal quantizer in memory-size constrained vector quantization induces a quantization error which is equal to a Wasserstein distortion. However, for the optimal (Shannon-)entropy constrained quantization error a proof for a similar identity is still missing. Relying on principal results of the optimal mass transportation theory, we will prove that the optimal quantization error is equal to a Wasserstein distance. Since we will state the quantization problem in a very general setting, our approach includes the R\'enyi-$\alpha$-entropy as a complexity constraint, which includes the special case of (Shannon-)entropy constrained $(\alpha = 1)$ and memory-size constrained $(\alpha = 0)$ quantization. Additionally, we will derive for certain distance functions codecell convexity for quantizers with a finite codebook. Using other methods, this regularity in codecell geometry has already been proved earlier by Gy\"{o}rgy and Linder. KW - Maßtheorie KW - Transporttheorie KW - Quantisierung KW - Entropie KW - Wasserstein distance KW - optimal quantization error KW - codecell convexity KW - R\'enyi-$\alpha$-entropy Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-22502 N1 - This is a preprint of an article accepted for publication in the Journal of Multivariate Analysis ISSN 0047-259X. The original publication is available at http://www.elsevier.com/. The digital object identifier (DOI) of the definitive article is 10.1016/j.jmva.2011.04.005. ER - TY - THES A1 - Störzer, Maximilian T1 - Impact Analysis for AspectJ - A Critical Analysis and Tool-Based Approach to AOP T1 - Impact-Analyse für AspectJ - Eine kritische Analyse mit werkzeuggestütztem Ansatz N2 - Aspect-Oriented Programming (AOP) has been promoted as a solution for modularization problems known as the tyranny of the dominant decomposition in literature. However, when analyzing AOP languages it can be doubted that uncontrolled AOP is indeed a silver bullet. The contributions of the work presented in this thesis are twofold. First, we critically analyze AOP language constructs and their effects on program semantics to sensitize programmers and researchers to resulting problems. We further demonstrate that AOP—as available in AspectJ and similar languages—can easily result in less understandable, less evolvable, and thus error prone code—quite opposite to its claims. Second, we examine how tools relying on both static and dynamic program analysis can help to detect problematical usage of aspect-oriented constructs. We propose to use change impact analysis techniques to both automatically determine the impact of aspects and to deal with AOP system evolution. We further introduce an analysis technique to detect potential semantical issues related to undefined advice precedence. The thesis concludes with an overview of available open source AspectJ systems and an assessment of aspect-oriented programming considering both fundamentals of software engineering and the contents of this thesis. KW - Modularität KW - Aspektorientierte Programmierung KW - Programmanalyse KW - Software Engineering KW - Separation of Concerns KW - Change Impact Analyse KW - AspectJ Fallstudie KW - Change Impact Analysis KW - AspectJ Case Study Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-897 ER - TY - THES A1 - Kickingereder, Reiner T1 - Optische Vermessung partiell reflektierender Oberflächen N2 - Die vorliegende Arbeit befaßt sich mit der dreidimensionalen Rekonstruktion reflektierender Oberflächen. Dabei wird sowohl die Oberflächenform als auch die absolute Lage im Raum bestimmt. Es werden Oberflächen behandelt, die einerseits total reflektieren, andererseits diffuse und spiegelnde Reflexionsanteile aufweisen. Zur Lösung des Problems werden zwei Kameras und mehrere Lichtquellen verwendet. Eine genauere Analyse der Lichtreflexion an spiegelnden Objekten führt zu einer Beschreibung des Problems als Lösung einer totalen Differentialgleichung. Diese Lösung wird als Startwert für die Rekonstruktion partiell reflektierender Oberflächen verwendet. KW - Dreidimensionale Rekonstruktion KW - Bildverarbeitung KW - reflektierende Oberflächen KW - Spiegelung KW - image processing KW - object reconstruction KW - reflecting surfaces Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-936 ER - TY - INPR A1 - Kreitmeier, Wolfgang T1 - Optimal Quantization for Dyadic Homogeneous Cantor Distributions N2 - For a large class of dyadic homogeneous Cantor distributions in \mathbb{R}, which are not necessarily self-similar, we determine the optimal quantizers, give a characterization for the existence of the quantization dimension, and show the non-existence of the quantization coefficient. The class contains all self-similar dyadic Cantor distributions, with contraction factor less than or equal to \frac{1}{3}. For these distributions we calculate the quantization errors explicitly. KW - Maßtheorie KW - Fraktale Dimension KW - Iteriertes Funktionensystem KW - Cantor-Menge KW - Hausdorff-Dimension KW - Hausdorff-Maß KW - Quantization KW - homogeneous Cantor measures KW - Quantization dimension KW - Quantization coefficient Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-3845 N1 - Die Endfassung des Artikels kann beim Verfasser angefordert werden. Kontaktinformation: opus@uni-passau.de ER - TY - THES A1 - Hölbling, Günther T1 - Personalized Means of Interacting with Multimedia Content T1 - Persönliche Wege der Interaktion mit multimedialen Inhalten N2 - Today the world of multimedia is almost completely device- and content-centered. It focuses it’s energy nearly exclusively on technical issues such as computing power, network specifics or content and device characteristics and capabilities. In most multimedia systems, the presentation of multimedia content and the basic controls for playback are main issues. Because of this, a very passive user experience, comparable to that of traditional TV, is most often provided. In the face of recent developments and changes in the realm of multimedia and mass media, this ”traditional” focus seems outdated. The increasing use of multimedia content on mobile devices, along with the continuous growth in the amount and variety of content available, make necessary an urgent re-orientation of this domain. In order to highlight the depth of the increasingly difficult situation faced by users of such systems, it is only logical that these individuals be brought to the center of attention. In this thesis we consider these trends and developments by applying concepts and mechanisms to multimedia systems that were first introduced in the domain of usercentrism. Central to the concept of user-centrism is that devices should provide users with an easy way to access services and applications. Thus, the current challenge is to combine mobility, additional services and easy access in a single and user-centric approach. This thesis presents a framework for introducing and supporting several of the key concepts of user-centrism in multimedia systems. Additionally, a new definition of a user-centric multimedia framework has been developed and implemented. To satisfy the user’s need for mobility and flexibility, our framework makes possible seamless media and service consumption. The main aim of session mobility is to help people cope with the increasing number of different devices in use. Using a mobile agent system, multimedia sessions can be transferred between different devices in a context-sensitive way. The use of the international standard MPEG-21 guarantees extensibility and the integration of content adaptation mechanisms. Furthermore, a concept is presented that will allow for individualized and personalized selection and face the need for finding appropriate content. All of which can be done, using this approach, in an easy and intuitive way. Especially in the realm of television, the demand that such systems cater to the need of the audience is constantly growing. Our approach combines content-filtering methods, state-of-the-art classification techniques and mechanisms well known from the area of information retrieval and text mining. These are all utilized for the generation of recommendations in a promising new way. Additionally, concepts from the area of collaborative tagging systems are also used. An extensive experimental evaluation resulted in several interesting findings and proves the applicability of our approach. In contrast to the ”lean-back” experience of traditional media consumption, interactive media services offer a solution to make possible the active participation of the audience. Thus, we present a concept which enables the use of interactive media services on mobile devices in a personalized way. Finally, a use case for enriching TV with additional content and services demonstrates the feasibility of this concept. N2 - Die heutige Welt der Medien und der multimedialen Inhalte ist nahezu ausschließlich inhalts- und geräteorientiert. Im Fokus verschiedener Systeme und Entwicklungen stehen oft primär die Art und Weise der Inhaltspräsentation und technische Spezifika, die meist geräteabhängig sind. Die zunehmende Menge und Vielfalt an multimedialen Inhalten und der verstärkte Einsatz von mobilen Geräten machen ein Umdenken bei der Konzeption von Multimedia Systemen und Frameworks dringend notwendig. Statt an eher starren und passiven Konzepten, wie sie aus dem TV Umfeld bekannt sind, festzuhalten, sollte der Nutzer in den Fokus der multimedialen Konzepte rücken. Um dem Nutzer im Umgang mit dieser immer komplexeren und schwierigen Situation zu helfen, ist ein Umdenken im grundlegenden Paradigma des Medienkonsums notwendig. Durch eine Fokussierung auf den Nutzer kann der beschriebenen Situation entgegengewirkt werden. In der folgenden Arbeit wird auf Konzepte aus dem Bereich Nutzerzentrierung zurückgegriffen, um diese auf den Medienbereich zu übertragen und sie im Sinne einer stärker nutzerspezifischen und nutzerorientierten Ausrichtung einzusetzen. Im Fokus steht hierbei der TV-Bereich, wobei die meisten Konzepte auch auf die allgemeine Mediennutzung übertragbar sind. Im Folgenden wird ein Framework für die Unterstützung der wichtigsten Konzepte der Nutzerzentrierung im Multimedia Bereich vorgestellt. Um dem Trend zur mobilen Mediennutzung Sorge zu tragen, ermöglicht das vorgestellte Framework die Nutzung von multimedialen Diensten und Inhalten auf und über die Grenzen verschiedener Geräte und Netzwerke hinweg (Session mobility). Durch die Nutzung einer mobilen Agentenplattform in Kombination mit dem MPEG-21 Standard konnte ein neuer und flexibel erweiterbarer Ansatz zur Mobilität von Benutzungssitzungen realisiert werden. Im Zusammenhang mit der stetig wachsenden Menge an Inhalten und Diensten stellt diese Arbeit ein Konzept zur einfachen und individualisierten Selektion und dem Auffinden von interessanten Inhalten und Diensten in einer kontextspezifischen Weise vor. Hierbei werden Konzepte und Methoden des inhaltsbasierten Filterns, aktuelle Klassifikationsmechanismen und Methoden aus dem Bereich des ”Textminings” in neuer Art und Weise in einem Multimedia Empfehlungssystem eingesetzt. Zusätzlich sind Methoden des Web 2.0 in eine als Tag-basierte kollaborative Komponente integriert. In einer umfassenden Evaluation wurde sowohl die Umsetzbarkeit als auch der Mehrwert dieser Komponente demonstriert. Eine aktivere Beteiligung im Medienkonsum ermöglicht unsere iTV Komponente. Sie unterstützt das Anbieten und die Nutzung von interaktiven Diensten, begleitend zum Medienkonsum, auf mobilen Geräten. Basierend auf einem Szenario zur Anreicherung von TV Sendungen um interaktive Dienste konnte die Umsetzbarkeit dieses Konzepts demonstriert werden. KW - Empfehlungssystem KW - Personalisierung KW - Interaktives Fernsehen KW - Künstliche Intelligenz KW - Kollaborative Filterung KW - Recommender system KW - personalization KW - interactive TV KW - session mobility Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-24210 ER - TY - THES A1 - Johns, Martin T1 - Code Injection Vulnerabilities in Web Applications - Exemplified at Cross-site Scripting T1 - Code-injection Verwundbarkeiten in Web Anwendungen am Beispiel von Cross-site Scripting N2 - The majority of all security problems in today's Web applications is caused by string-based code injection, with Cross-site Scripting (XSS)being the dominant representative of this vulnerability class. This thesis discusses XSS and suggests defense mechanisms. We do so in three stages: First, we conduct a thorough analysis of JavaScript's capabilities and explain how these capabilities are utilized in XSS attacks. We subsequently design a systematic, hierarchical classification of XSS payloads. In addition, we present a comprehensive survey of publicly documented XSS payloads which is structured according to our proposed classification scheme. Secondly, we explore defensive mechanisms which dynamically prevent the execution of some payload types without eliminating the actual vulnerability. More specifically, we discuss the design and implementation of countermeasures against the XSS payloads Session Hijacking'', Cross-site Request Forgery'', and attacks that target intranet resources. We build upon this and introduce a general methodology for developing such countermeasures: We determine a necessary set of basic capabilities an adversary needs for successfully executing an attack through an analysis of the targeted payload type. The resulting countermeasure relies on revoking one of these capabilities, which in turn renders the payload infeasible. Finally, we present two language-based approaches that prevent XSS and related vulnerabilities: We identify the implicit mixing of data and code during string-based syntax assembly as the root cause of string-based code injection attacks. Consequently, we explore data/code separation in web applications. For this purpose, we propose a novel methodology for token-level data/code partitioning of a computer language's syntactical elements. This forms the basis for our two distinct techniques: For one, we present an approach to detect data/code confusion on run-time and demonstrate how this can be used for attack prevention. Furthermore, we show how vulnerabilities can be avoided through altering the underlying programming language. We introduce a dedicated datatype for syntax assembly instead of using string datatypes themselves for this purpose. We develop a formal, type-theoretical model of the proposed datatype and proof that it provides reliable separation between data and code hence, preventing code injection vulnerabilities. We verify our approach's applicability utilizing a practical implementation for the J2EE application server. N2 - Cross-site Scripting (XSS) ist eine der häufigsten Verwundbarkeitstypen im Bereich der Web Anwendungen. Die Dissertation behandelt das Problem XSS ganzheitlich: Basierend auf einer systematischen Erarbeitung der Ursachen und potentiellen Konsequenzen von XSS, sowie einer umfassenden Klassifikation dokumentier Angriffsarten, wird zunächst eine Methodik vorgestellt, die das Design von dynamischen Gegenmaßnahmen zur Angriffseingrenzung erlaubt. Unter Verwendung dieser Methodik wird das Design und die Evaluation von drei Gegemaßnahmen für die Angriffsunterklassen "Session Hijacking", "Cross-site Request Forgery" und "Angriffe auf das Intranet" vorgestellt. Weiterhin, um das unterliegende Problem grundsätzlich anzugehen, wird ein Typ-basierter Ansatz zur sicheren Programmierung von Web Anwendungen beschrieben, der zuverlässigen Schutz vor XSS Lücken garantiert. KW - Computersicherheit KW - World Wide Web KW - XSS KW - SQL Injection KW - Security KW - Web KW - XSS KW - SQL Injection Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-23626 ER - TY - THES A1 - Rabl, Tilmann T1 - Efficiency in Cluster Database Systems - Dynamic and Workload-Aware Scaling and Allocation T1 - Effizienz in Cluster-Datenbanksystemen - Dynamische und Arbeitslastberücksichtigende Skalierung und Allokation N2 - Database systems have been vital in all forms of data processing for a long time. In recent years, the amount of processed data has been growing dramatically, even in small projects. Nevertheless, database management systems tend to be static in terms of size and performance which makes scaling a difficult and expensive task. Because of performance and especially cost advantages more and more installed systems have a shared nothing cluster architecture. Due to the massive parallelism of the hardware programming paradigms from high performance computing are translated into data processing. Database research struggles to keep up with this trend. A key feature of traditional database systems is to provide transparent access to the stored data. This introduces data dependencies and increases system complexity and inter process communication. Therefore, many developers are exchanging this feature for a better scalability. However, explicitly managing the data distribution and data flow requires a deep understanding of the distributed system and reduces the possibilities for automatic and autonomic optimization. In this thesis we present an approach for database system scaling and allocation that features good scalability although it keeps the data distribution transparent. The first part of this thesis analyzes the challenges and opportunities for self-scaling database management systems in cluster environments. Scalability is a major concern of Internet based applications. Access peaks that overload the application are a financial risk. Therefore, systems are usually configured to be able to process peaks at any given moment. As a result, server systems often have a very low utilization. In distributed systems the efficiency can be increased by adapting the number of nodes to the current workload. We propose a processing model and an architecture that allows efficient self-scaling of cluster database systems. In the second part we consider different allocation approaches. To increase the efficiency we present a workload-aware, query-centric model. The approach is formalized; optimal and heuristic algorithms are presented. The algorithms optimize the data distribution for local query execution and balance the workload according to the query history. We present different query classification schemes for different forms of partitioning. The approach is evaluated for OLTP and OLAP style workloads. It is shown that variants of the approach scale well for both fields of application. The third part of the thesis considers benchmarks for large, adaptive systems. First, we present a data generator for cloud-sized applications. Due to its architecture the data generator can easily be extended and configured. A key feature is the high degree of parallelism that makes linear speedup for arbitrary numbers of nodes possible. To simulate systems with user interaction, we have analyzed a productive online e-learning management system. Based on our findings, we present a model for workload generation that considers the temporal dependency of user interaction. N2 - Datenbanksysteme sind seit langem die Grundlage für alle Arten von Informationsverarbeitung. In den letzten Jahren ist das Datenaufkommen selbst in kleinen Projekten dramatisch angestiegen. Dennoch sind viele Datenbanksysteme statisch in Bezug auf ihre Kapazität und Verarbeitungsgeschwindigkeit was die Skalierung aufwendig und teuer macht. Aufgrund der guten Geschwindigkeit und vor allem aus Kostengründen haben immer mehr Systeme eine Shared-Nothing-Architektur, bestehen also aus unabhängigen, lose gekoppelten Rechnerknoten. Da dieses Konstruktionsprinzip einen sehr hohen Grad an Parallelität aufweist, werden zunehmend Programmierparadigmen aus dem klassischen Hochleistungsrechen für die Informationsverarbeitung eingesetzt. Dieser Trend stellt die Datenbankforschung vor große Herausforderungen. Eine der grundlegenden Eigenschaften traditioneller Datenbanksysteme ist der transparente Zugriff zu den gespeicherten Daten, der es dem Nutzer erlaubt unabhängig von der internen Organisation auf die Daten zuzugreifen. Die resultierende Unabhängigkeit führt zu Abhängigkeiten in den Daten und erhöht die Komplexität der Systeme und der Kommunikation zwischen einzelnen Prozessen. Daher wird Transparenz von vielen Entwicklern für eine bessere Skalierbarkeit geopfert. Diese Entscheidung führt dazu, dass der die Datenorganisation und der Datenfluss explizit behandelt werden muss, was die Möglichkeiten für eine automatische und autonome Optimierung des Systems einschränkt. Der in dieser Arbeit vorgestellte Ansatz zur Skalierung und Allokation erhält den transparenten Zugriff und zeichnet sich dabei durch seine vollständige Automatisierbarkeit und sehr gute Skalierbarkeit aus. Im ersten Teil dieser Dissertation werden die Herausforderungen und Chancen für selbst-skalierende Datenbankmanagementsysteme behandelt, die in auf Computerclustern betrieben werden. Gute Skalierbarkeit ist eine notwendige Eigenschaft für Anwendungen, die über das Internet zugreifbar sind. Lastspitzen im Zugriff, die die Anwendung überladen stellen ein finanzielles Risiko dar. Deshalb werden Systeme so konfiguriert, dass sie eventuelle Lastspitzen zu jedem Zeitpunkt verarbeiten können. Das führt meist zu einer im Schnitt sehr geringen Auslastung der unterliegenden Systeme. Eine Möglichkeit dieser Ineffizienz entgegen zu steuern ist es die Anzahl der verwendeten Rechnerknoten an die vorliegende Last anzupassen. In dieser Dissertation werden ein Modell und eine Architektur für die Anfrageverarbeitung vorgestellt, mit denen es möglich ist Datenbanksysteme auf Clusterrechnern einfach und effizient zu skalieren. Im zweiten Teil der Arbeit werden verschieden Möglichkeiten für die Datenverteilung behandelt. Um die Effizienz zu steigern wird ein Modell verwendet, das die Lastverteilung im Anfragestrom berücksichtigt. Der Ansatz ist formalisiert und optimale und heuristische Lösungen werden präsentiert. Die vorgestellten Algorithmen optimieren die Datenverteilung für eine lokale Ausführung aller Anfragen und balancieren die Last auf den Rechnerknoten. Es werden unterschiedliche Arten der Anfrageklassifizierung vorgestellt, die zu verschiedenen Arten von Partitionierung führen. Der Ansatz wird sowohl für Onlinetransaktionsverarbeitung, als auch Onlinedatenanalyse evaluiert. Die Evaluierung zeigt, dass der Ansatz für beide Felder sehr gut skaliert. Im letzten Teil der Arbeit werden verschiedene Techniken für die Leistungsmessung von großen, adaptiven Systemen präsentiert. Zunächst wird ein Datengenerierungsansatz gezeigt, der es ermöglicht sehr große Datenmengen völlig parallel zu erzeugen. Um die Benutzerinteraktion von Onlinesystemen zu simulieren wurde ein produktives E-learningsystem analysiert. Anhand der Analyse wurde ein Modell für die Generierung von Arbeitslasten erstellt, das die zeitlichen Abhängigkeiten von Benutzerinteraktion berücksichtigt. KW - Verteiltes Datenbanksystem KW - Cluster KW - Allokation KW - Skalierung KW - Effizienzsteigerung KW - Clusterdatenbanksystem KW - Dynamic Allocation KW - Autonomic Scaling KW - Cluster Database System Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-25821 ER - TY - THES A1 - Ali, Rashid T1 - Weyl Gröbner Basis Cryptosystems N2 - In this thesis, we shall consider a certain class of algebraic cryptosystems called Gröbner Basis Cryptosystems. In 1994, Koblitz introduced the Polly Cracker cryptosystem that is based on the theory of Gröbner basis in commutative polynomials rings. The security of this cryptosystem relies on the fact that the computation of Gröbner basis is, in general, EXPSPACE-hard. Cryptanalysis of these commutative Polly Cracker type cryptosystems is possible by using attacks that do not require the computation of Gröbner basis for breaking the system, for example, the attacks based on linear algebra. To secure these (commutative) Gröbner basis cryptosystems against various attacks, among others, Ackermann and Kreuzer introduced a general class of Gröbner Basis Cryptosystems that are based on the difficulty of computing module Gröbner bases over general non-commutative rings. The objective of this research is to describe a special class of such cryptosystems by introducing the Weyl Gröbner Basis Cryptosystems. We divide this class of cryptosystems in two parts namely the (left) Weyl Gröbner Basis Cryptosystems and Two-Sided Weyl Gröbner Basis Cryptosystems. We suggest to use Gröbner bases for left and two-sided ideals in Weyl algebras to construct specific instances of such cryptosystems. We analyse the resistance of these cryptosystems to the standard attacks and provide computational evidence that secure Weyl Gröbner Basis Cryptosystems can be built using left (resp. two-sided) Gröbner bases in Weyl algebras. KW - Gröbner-Basis KW - Weyl-Algebra KW - Kryptologie KW - Public Key Cryptosystem KW - Non commutative Gröbner Basis Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-23195 ER - TY - INPR A1 - Kreitmeier, Wolfgang A1 - Linder, Tamas T1 - High-Resolution Scalar Quantization with Rényi Entropy Constraint N2 - We consider optimal scalar quantization with $r$th power distortion and constrained R\'enyi entropy of order $\alpha$. For sources with absolutely continuous distributions the high rate asymptotics of the quantizer distortion has long been known for $\alpha=0$ (fixed-rate quantization) and $\alpha=1$ (entropy-constrained quantization). These results have recently been extended to quantization with R\'enyi entropy constraint of order $\alpha \ge r+1$. Here we consider the more challenging case $\alpha\in [-\infty,0)\cup (0,1)$ and for a large class of absolutely continuous source distributions we determine the sharp asymptotics of the optimal quantization distortion. The achievability proof is based on finding (asymptotically) optimal quantizers via the companding approach, and is thus constructive. KW - Maßtheorie KW - Quantisierung KW - Entropie KW - Companding KW - high-resolution asymptotics KW - optimal quantization KW - Rényi entropy Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-23787 N1 - This is a preprint of an article accepted for publication in the IEEE Transactions on Information Theory Journal, ISSN: 0018-9448. The original publication is available at http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=18 ER - TY - THES A1 - Houyou, Amine Mohamed T1 - Context-Aware Mobility: A Distributed Approach to Context Management T1 - Kontext-basierte Mobilität: Ein verteilter Ansatz zum Kontext-Management N2 - The recent development of a whole plethora of new wireless technologies, such as IEEE 802.11, IEEE 802.15, IEEE 802.16, UMTS, and more recently LTE, etc, has triggered several efforts to integrate these technologies in a converged world of transparent and ubiquitous wireless connectivity. Most of these technologies have evolved around a certain use case and with some user behaviour being assumed; however, there still lacks a holistic solution to adapt access to user needs, in an automatic and transparent manner. One major problem that has to be addressed first, is mobility management between heterogeneous wireless networks. Current mobility management solutions mostly originate from cellular networking systems, which are operator specific, centralised, and focused on a single link technology. In order to deal with the wireless diversity of future wireless and mobile Internet, a new approach is needed. Adaptive wireless connectivity that is tailored around the user needs and capabilities is named context-aware mobility management. Context refers to the information describing the surroundings of the user as well as his/her behaviour, and additional semantic information that could optimise the adaption process. Context management normally entails discovering and tracking context, reasoning based on the discovered information, then adapting (or acting) upon the context-aware application or system. This context management chain is adapted throughout the thesis to the task of context-aware mobility management. The added complexity is necessary to adapt the ubiquitous access to the condition of both the user and the surrounding networks, while assuming that overlapping wireless networks could still be managed in separate management domains. Linking these management domains and aggregating this composite information in the form of a network context is one of the major contributions of this work. An overlay-based solution takes into account this scattered nature of the context management system, which is modelled as a decentralised dynamic location-based service. The proposed architecture is generalised to support ubiquitous location-based services, and a design methodology is proposed to ensure the localised impact of mobility-led context retrieval overhead. KW - Netze KW - Mobilität KW - Kontextbezogenes System KW - Hilbert-Unterraum KW - Hilbert-Fläche KW - Drahtloses lokales Netz KW - Overlay-Netz KW - Geoinformationssystem KW - St KW - Mobility Management KW - Cellular networks KW - 4G Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-17975 ER - TY - THES A1 - Ogris, Georg T1 - Multi-modal on-body sensing of human activities N2 - Increased usage and integration of state-of-the-art information technology in our everyday work life aims at increasing the working efficiency. Due to unhandy human-computer-interaction methods this progress does not always result in increased efficiency, for mobile workers in particular. Activity recognition based contextual computing attempts to balance this interaction deficiency. This work investigates wearable, on-body sensing techniques on their applicability in the field of human activity recognition. More precisely we are interested in the spotting and recognition of so-called manipulative hand gestures. In particular the thesis focuses on the question whether the widely used motion sensing based approach can be enhanced through additional information sources. The set of gestures a person usually performs on a specific place is limited -- in the contemplated production and maintenance scenarios in particular. As a consequence this thesis investigates whether the knowledge about the user's hand location provides essential hints for the activity recognition process. In addition, manipulative hand gestures -- due to their object manipulating character -- typically start in the moment the user's hand reaches a specific place, e.g. a specific part of a machinery. And the gestures most likely stop in the moment the hand leaves the position again. Hence this thesis investigates whether hand location can help solving the spotting problem. Moreover, as user-independence is still a major challenge in activity recognition, this thesis investigates location context as a possible key component in a user-independent recognition system. We test a Kalman filter based method to blend absolute position readings with orientation readings based on inertial measurements. A filter structure is suggested which allows up-sampling of slow absolute position readings, and thus introduces higher dynamics to the position estimations. In such a way the position measurement series is made aware of wrist motions in addition to the wrist position. We suggest location based gesture spotting and recognition approaches. Various methods to model the location classes used in the spotting and recognition stages as well as different location distance measures are suggested and evaluated. In addition a rather novel sensing approach in the field of human activity recognition is studied. This aims at compensating drawbacks of the mere motion sensing based approach. To this end we develop a wearable hardware architecture for lower arm muscular activity measurements. The sensing hardware based on force sensing resistors is designed to have a high dynamic range. In contrast to preliminary attempts the proposed new design makes hardware calibration unnecessary. Finally we suggest a modular and multi-modal recognition system; modular with respect to sensors, algorithms, and gesture classes. This means that adding or removing a sensor modality or an additional algorithm has little impact on the rest of the recognition system. Sensors and algorithms used for spotting and recognition can be selected and fine-tuned separately for each single activity. New activities can be added without impact on the recognition rates of the other activities. KW - Kontextbezogenes System KW - Mustererkennung KW - Kalman filter based sensor fusion KW - Spotting of Manipulative hand gestures KW - Force sensing resistors KW - Location modeling Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-17930 ER - TY - INPR A1 - Kreitmeier, Wolfgang T1 - Hausdorff measure of uniform self-similar fractals N2 - Let d ≥ 1 be an integer and E a self-similar fractal set, which is the attractor of a uniform contracting iterated function system (UIFS) on Rd. Denote by D the Hausdorff dimension, by HD(E) the Hausdorff measure and by diam (E) the diameter of E. If the UIFS is parametrised by its contracting factor c, while the set ω of fixed points of the UIFS does not depend on c, we will show the existence of a positive constant depending only on ω, such that the Hausdorff dimension is smaller than one and HD = (E) D if c is smaller than this constant. We apply our result to modified versions of various classical fractals. Moreover we present a parametrised UIFS where ω depends on c and HD < diam(E)D, if c is small enough. KW - Maßtheorie KW - Iteriertes Funktionensystem KW - Hausdorff-Dimension KW - Hausdorff-Maß KW - Self-similar set KW - Hausdorff measure Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-17948 N1 - This is a preprint of an article accepted for publication in Analysis in Theory and Applications ISSN: 1672-4070 (print version) ISSN: 1573-8175 (electronic version) Copyright (c) by Springer. The original publication is available at www.springerlink.com ER - TY - INPR A1 - Kreitmeier, Wolfgang T1 - Optimal quantization for the one-dimensional uniform distribution with Rényi -α-entropy constraints N2 - We establish the optimal quantization problem for probabilities under constrained Rényi-α-entropy of the quantizers. We determine the optimal quantizers and the optimal quantization error of one-dimensional uniform distributions including the known special cases α = 0 (restricted codebook size) and α = 1 (restricted Shannon entropy). KW - Maßtheorie KW - Quantisierung KW - Entropie KW - optimal quantization KW - uniform distribution KW - Rényi-α-entropy Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-16983 ER - TY - THES A1 - Oberender, Jens O. T1 - Widerstandsfähige Anonymisierungsnetze T1 - Resilient Anonymity Networks N2 - Unverkettbare Nachrichten sind ein Grundbaustein anonymer Kommunikation. Anonymisierungsnetze schützen mittels Unverkettbarkeit, wer mit wem kommuniziert sowie die Identität der Beteiligten einer Kommunikationsbeziehung. Anonymisierungsnetze benötigen Kooperation, da die Anonymität durch Ressourcen anderer Teilnehmer geschützt wird. Wenn die Kosten und der Nutzen eines Anonymisierungsnetzes transparent sind, ergeben sich Zielkonflikte zwischen rationalen Teilnehmern. Es wird daher untersucht, inwiefern daraus resultierendes egoistisches Verhalten die Widerstandsfähigkeit dieser Netze beeinträchtigt. Störungen werden in einem spieltheoretischen Modell untersucht, um widerstandsfähige Konfigurationen von Anonymisierungsnetzen zu ermitteln. Eine weitere Störquelle sind Überflutungsangriffe mittels unverkettbarer Nachrichten. Es soll sowohl die Verfügbarkeit als auch die Anonymität geschützt werden. Dazu wird Unverkettbarkeit für Nachrichten aufrecht erhalten, außer wenn die Senderate eines Nachrichtenstroms eine Richtlinie überschreitet. Innerhalb verkettbarer Nachrichten können Überflutungsangriffe erkannt werden. Darüber kann die Verfügbarkeit des Netzdienstes geschützt werden. KW - Anonymität KW - Privatheit KW - Widerstandsfähigkeit KW - Computerunterstützte Kommunikation KW - Spieltheorie KW - DoS-Attacke KW - Verbindungsanonymität KW - Connection anonymity Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-16846 ER - TY - INPR A1 - Kreitmeier, Wolfgang T1 - Error bounds for high-resolution quantization with Rényi - α - entropy constraints N2 - We consider the problem of optimal quantization with norm exponent r > 0 for Borel probabilities on Rd under constrained Rényi-α-entropy of the quantizers. If the bound on the entropy becomes large, then sharp asymptotics for the optimal quantization error are well-known in the special cases α = 0 (memory-constrained quantization) and α = 1 (Shannon-entropy-constrained quantization). In this paper we determine sharp asymptotics for the optimal quantization error under large entropy bound with entropy parameter α ∈ [1+r/d, ∞]. For α ∈ [0,1+r/d[ we specify the asymptotical order of the optimal quantization error under large entropy bound. The optimal quantization error decays exponentially fast with the entropy bound and the exact decay rate is determined for all α ∈ [0, ∞]. KW - Maßtheorie KW - Quantisierung KW - Vektorquantisierung KW - Entropie KW - Vector quantization KW - high-resolution quantization KW - Rényi-α-entropy KW - approximation of probabilities Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-16647 ER - TY - THES A1 - Maydl, Walter T1 - Komponentenbasierte Softwareentwicklung für datenflußorientierte eingebettete Systeme N2 - Diese Dissertation beschäftigt sich mit den Problemen bei der Entwicklung von effizienter und zuverlässiger Software für eingebettete Systeme. Eingebettete Systeme sind inhärent nebenläufig, was mit einen Grund für ihre hohe Entwurfskomplexität darstellt. Aus dieser Nebenläufigkeit resultiert ein hoher Grad an Kommunikation zwischen den einzelnen Komponenten. Eine wichtige Forderung zur Vereinfachung des Entwurfsprozesses besteht in der getrennten Modellierung von Kommunikationsprotokollen und eigentlichen Verarbeitungsalgorithmen. Daraus resultiert eine höhere Wiederverwendbarkeit bei sich ändernden Kommunikationsstrukturen. Die Grundlage für die sogenannten Datenflußsprachen bildet eine einfache von Gilles Kahn konzipierte Sprache für Parallelverarbeitung. In dieser Sprache besteht ein System aus einer Menge sequentieller Prozesse (Komponenten), die über Fifokanäle miteinander kommunizieren. Ein Prozess ist rechenbereit, wenn seine Eingangsfifos mit entsprechenden Daten gefüllt sind. Übertragen werden physikalische Signale, die als Ströme bezeichnet werden. Ströme sind Folgen von Werten ohne explizite Zeitangaben. Das Einsatzgebiet von Datenflußsprachen liegt in der Entwicklung von Programmen zur Bild- und Signalverarbeitung, typischen Aufgaben in eingebetteten Systemen. Die Programmierung erfolgt visuell, wobei man Icons als Repräsentanten parametrisierbarer Komponenten aus einer Bibliothek auswählt und mittels Kanten (Fifos) verbindet. Ein im allgemeinen dynamischer Scheduler überwacht die Ausführung des fertiggestellten Anwendungsprogramms. Diese Arbeit schlägt ein universelleres Modell physikalischer Signale vor. Dabei werden zwei Ziele verfolgt: 1. Effiziente Kommunikation zwischen den Komponenten 2. Entwurfsbegleitende Überprüfung von Programmeigenschaften unter Verwendung komplexerer Komponentenmodelle Zur Effizienzsteigerung werden nur relevante Werte innerhalb von Strömen übertragen. Dies erhöht zwar den Mehraufwand zur Kennzeichnung des Aufbaus eines Teilstroms, in praktischen Anwendungen ist die hier vorgestellte Methode jedoch effizienter. Die Einführung neuer Signalmerkmale erlaubt unterschiedlichste Überprüfungen der Einhaltung von Typregeln durch die Eingangs- und Ausgangsströme einer Komponente. Anstelle einfacher Schaltregeln werden aufwendigere Kommunikationsprotokolle für die verschiedenen Arten von Komponenten eingeführt. Fifomaten (Fifo-Automaten) dienen als formale Grundlage. Mittels eines dezidierten Model-Checking-Verfahrens wird das Zusammenspiel der Fifomaten daraufhin untersucht, ob ein zyklischer Schedule existiert. Die Existenz eines solchen zyklischen Schedules schließt Speicherüberlauf und Deadlocks aus und garantiert darüber hinaus, daß das Programm nach endlicher Zeit wieder in die Ausgangssituation zurückfindet. Da im allgemeinen die Datenflußprogramme turingäquivalent sind, kann es allerdings zyklische Schedules geben, die das Verfahren nicht entdeckt. Mit der hier vorgestellten und implementierten Methode wird die Entwicklungszeit korrekter Datenflußprogramme deutlich reduziert. Das neue Modell physikalischer Signale macht zudem die Ausführung effizienter. KW - Softwareentwicklung KW - Eingebettetes System KW - Datenflussgraph KW - Komponente KW - Software Development KW - Embedded System KW - Dataflow Graph KW - Component-Based Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-681 ER - TY - THES A1 - Schwarzfischer, Thomas T1 - Quality and Utility - On the Use of Time-Value Functions to Integrate Quality and Timeliness Flexible Aspects in a Dynamic Real-Time Scheduling Environment T1 - Qualität und Nutzen - Über den Gebrauch von Zeit-Wert-Funktionen zur Integration qualitäts- und zeit-flexibler Aspekte in einer dynamischen Echtzeit-Einplanungsumgebung N2 - Scheduling methodologies for real-time applications have been of keen interest to diverse research communities for several decades. Depending on the application area, algorithms have been developed that are tailored to specific requirements with respect to both the individual components of which an application is made up and the computational platform on which it is to be executed. Many real-time scheduling algorithms base their decisions solely or partly on timing constraints expressed by deadlines which must be met even under worst-case conditions. The increasing complexity of computing hardware means that worst-case execution time analysis becomes increasingly pessimistic. Scheduling hard real-time computations according to their worst-case execution times (which is common practice) will thus result, on average, in an increasing amount of spare capacity. The main goal of flexible real-time scheduling is to exploit this otherwise wasted capacity. Flexible scheduling schemes have been proposed to increase the ability of a real-time system to adapt to changing requirements and nondeterminism in the application behaviour. These models can be categorised as those whose source of flexibility is the quality of computations and those which are flexible regarding their timing constraints. This work describes a novel model which allows to specify both flexible timing constraints and quality profiles for an application. Furthermore, it demonstrates the applicability of this specification method to real-world examples and suggests a set of feasible scheduling algorithms for the proposed problem class. N2 - Einplanungsverfahren für Echtzeitanwendungen stehen seit Jahrzehnten im Interesse verschiedener Forschungsgruppen. Abhängig vom Anwendungsgebiet wurden Algorithmen entwickelt, welche an die spezifischen Anforderungen sowohl hinsichtlich der einzelnen Komponenten, aus welchen eine Anwendung besteht, als auch an die Rechnerplattform, auf der diese ausgeführt werden sollen, angepasst sind. Viele Echtzeit-Einplanungsverfahren gründen ihre Entscheidungen ausschließlich oder teilweise auf Zeitbedingungen, welche auch bei Auftreten maximaler Ausführungszeiten eingehalten werden müssen. Die zunehmende Komplexität von Rechner-Hardware bedeutet, dass die Worst-Case-Analyse in steigendem Maße pessimistisch wird. Die Einplanung harter Echtzeit-Berechnungen anhand ihrer maximalen Ausführungszeiten (was die gängige Praxis darstellt) resultiert daher im Regelfall in einer frei verfügbaren Rechenkapazität in steigender Höhe. Das Hauptziel flexibler Echtzeit-Einplanungsverfahren ist es, diese ansonsten verschwendete Kapazität auszunutzen. Flexible Einplanungsverfahren wurden vorgeschlagen, welche die Fähigkeit eines Echtzeitsystems erhöhen, sich an veränderte Anforderungen und Nichtdeterminismus im Verhalten der Anwendung anzupassen. Diese Modelle können unterteilt werden in solche, deren Quelle der Flexibilität die Qualität der Berechnungen ist, und jene, welche flexibel hinsichtlich ihrer Zeitbedingungen sind. Diese Arbeit beschreibt ein neuartiges Modell, welches es erlaubt, sowohl flexible Zeitbedingungen als auch Qualitätsprofile für eine Anwendung anzugeben. Außerdem demonstriert sie die Anwendbarkeit dieser Spezifikationsmethode auf reale Beispiele und schlägt eine Reihe von Einplanungsalgorithmen für die vorgestellte Problemklasse vor. KW - Echtzeitsystem KW - Scheduling KW - Betriebssystem KW - Informatik KW - soft real-time KW - dynamic scheduling KW - time-value functions KW - local search KW - meta scheduling Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-619 ER - TY - THES A1 - Kreitmeier, Wolfgang T1 - Optimale Quantisierung verallgemeinerter Cantor-Verteilungen N2 - Für verallgemeinerte Cantor-Verteilungen, die im Eindimensionalen mittels klassischer Wischkonstruktion bzw. in höheren Dimensionen über iterierte Funktionensysteme definiert werden, wird das Problem der optimalen Quantisierung unter bestimmten Voraussetzungen vollständig gelöst. Es werden die optimalen Codebücher bestimmt und Formeln für den optimalen Quantisierungsfehler bewiesen. Im eindimensionalen Fall wird eine Existenzcharakterisierung der Quantisierungsdimension gegeben und unter bestimmten Voraussetzungen die Nichtexistenz des Quantisierungskoeffizienten gezeigt. Auch in höheren Dimensionen wird für die betrachteten Verteilungen bewiesen, dass der Quantisierungskoeffizient, bei existenter Quantisierungsdimension, nicht existiert. Die gewonnenen Resultate werden auf die Gleichverteilungen von modifizierten klassischen fraktalen Mengen, wie das Sierpinski-Dreieck, die Cantormenge und den Cantor-Staub angewandt. KW - Maßtheorie KW - Fraktale Dimension KW - Iteriertes Funktionensystem KW - Sierpinski-Menge KW - Cantor-Menge KW - Hausdorff-Dimension KW - Hausdorff-Maß KW - Optimale Quantisierung KW - homogene Cantormaße KW - Quantisierungsdimension KW - Quantisierungskoeffizient KW - Sierpinski-Dreieck KW - Optimal Quantization KW - homogeneous Cantor measures KW - Quantization dimension KW - Quantization coefficient KW - Sierpinski Gasket Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-913 ER - TY - INPR A1 - Kreitmeier, Wolfgang T1 - Optimal quantization of probabilities concentrated on small balls N2 - We consider probability distributions which are uniformly distributed on a disjoint union of balls with equal radius. For small enough radius the optimal quantization error is calculated explicitly in terms of the ball centroids. We apply the results to special self-similar measures. KW - Maßtheorie KW - Quantisierung KW - Iteriertes Funktionensystem KW - Schwerpunkt KW - optimal quantization KW - centroid KW - self-similar probabilities Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-12010 ER - TY - INPR A1 - Kreitmeier, Wolfgang T1 - Asymptotic order of quantization for Cantor distributions in terms of Euler characteristic, Hausdorff and Packing measure N2 - For homogeneous one-dimensional Cantor sets, which are not necessarily self-similar, we show under some restrictions that the Euler exponent equals the quantization dimension of the uniform distribution on these Cantor sets. Moreover for a special sub-class of these sets we present a linkage between the Hausdorff and the Packing measure of these sets and the high-rate asymptotics of the quantization error. KW - Maßtheorie KW - Fraktale Dimension KW - Iteriertes Funktionensystem KW - Cantor-Menge KW - Hausdorff-Dimension KW - Hausdorff-Maß KW - Homogeneous Cantor set KW - Euler characteristic KW - Euler exponent KW - quantization dimension KW - quantization coefficient KW - Hausdorff dimension Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-7374 N1 - Die Endfassung des Artikels kann beim Verfasser angefordert werden. Kontaktinformation: opus@uni-passau.de ER - TY - THES A1 - Ramsauer, Markus T1 - Energie- und qualitätsbewußte Einplanung von periodischen Prozessen in eingebetteten Echtzeitsystemen T1 - Energy- and quality-aware scheduling of periodic tasks in embedded real-time systems N2 - Mobile Geräte dienen immer häufiger zur Ausführung von Echtzeitanwendungen, sie bieten immer mehr Rechenleistung und sie werden kleiner und leichter. Hohe Rechenleistung erfordert jedoch sehr viel Energie, was im Gegensatz zu den geringen Akkukapazitäten, die aus der Forderung nach kleinen und leichten Geräten resultieren, steht. Bei der Echtzeiteinplanung von Rechenprozessen gewinnt daher der Energieverbrauch der Geräte neben der rechtzeitigen Beendigung von Anwendungen zunehmend an Bedeutung, weil sie möglichst lange unabhängig vom Stromnetz betrieben werden sollen. Andererseits werden auf diesen Geräten rechenintensive Anwendungen ausgeführt, bei denen es wünschenswert ist, die maximale mit der verfügbaren Rechenleistung erzielbare Qualität zu erhalten. In dieser Arbeit wird ein Systemmodell vorgestellt, das den Design-to-time-Ansatz mit den Möglichkeiten der dynamischen Leistungsanpassung (Rechenleistung und verbrauchte elektrische Leistung) moderner Prozessoren vereinigt. Der Design-to-time-Ansatz ermöglicht Energieeinsparungen oder Qualitätssteigerungen durch die dynamische Auswahl alternativer Implementierungen, welche dieselbe Aufgabe mit unterschiedlicher Ausführungsdauer und Qualität bzw. Energieverbrauch erfüllen. Das Systemmodell umfaßt unter anderem periodische Prozesse mit harten Echtzeitbedingungen, Datenabhängigkeiten und alternativen Implementierungen, sowie Prozessoren mit diskreten Leistungsstufen. Die Einplanung der Prozesse erfolgt in zwei Phasen. In der Offline-Phase wird ein flexibler Schedule berechnet, der für die zur Laufzeit möglichen Kombinationen von verstrichener Zeit und noch einzuplanender Prozeßmenge den jeweils einzuplanenden Prozeß, sowie die zu verwendende Implementierung und gegebenenfalls die einzustellende Leistungsstufe beinhaltet. Dieser flexible Schedule wird während der Online-Phase mit vernachlässigbarem Zeit- und Energieaufwand von einem Scheduler interpretiert. Für die Berechnung der optimalen flexiblen Schedules wurde ein Optimierer entwickelt, der eine Folge von flexiblen Schedules mit monoton steigender Güte (niedriger Energieverbrauch bzw. hohe Qualität) generiert, und damit der Klasse der Anytime-Algorithmen zuzuordnen ist. Eine Variante der Dynamischen Programmierung dient zur Bestimmung global optimaler, flexibler Schedules, die beispielsweise als Basis für Benchmarks dienen. Eine auf Simulated Annealing basierende Variante des Optimierers ermöglicht ein schnelleres Auffinden guter, flexibler Schedules für umfangreichere Anwendungen. N2 - Mobile devices are excessively used for executing real-time applications, today. They provide increasing performance and they are getting more lightweight and smaller every day. Unfortunately, high processing performance demands much energy and thus anticipates smaller battery capacities resulting from the required size and weight of the devices. Therefore, energy consumption gains importance besides the timely completion of real-time tasks when a schedule has to be calculated, to provide a longer operating time independent of a power outlet. On the other hand, when calculation intensive tasks are being executed, high performance should be provided, to obtain maximum quality. This work presents a system model joining the design-to-time approach with modern processor's capabilities to run at different clock frequencies. Design-to-time scheduling allows for energy savings or quality enhancements by dynamically selecting alternative implementations, which fulfill a task's function with different time and with different energy consumption or quality. The system model comprises periodic tasks with hard real-time constraints, data-dependencies and alternative implementations, as well as processors with multiple clock modes. Scheduling is split in two phases. First, in an offline phase a flexible plan is calculated. It contains the task, implementation and clock frequency to be scheduled for every possible combination of elapsed time and unscheduled task set. Second, the flexible plan is interpreted by an online scheduler with a negligible amount of time and energy. A pair of optimization algorithms has been developed for calculating optimal flexible plans. They deliver a series of flexible plans with increasing quality or decreasing energy demand, and therefore they belong to the class of anytime algorithms. A variation of dynamic programming is used for finding globally optimal plans, e.g. aiming as reference values for benchmarks, whereas for complex system models an optimizer based on simulated annealing is provided, that finds good flexible plans fast. KW - Echtzeitsystem KW - Scheduling KW - Betriebssystem KW - Informatik KW - Optimierung KW - Anytime-Algorithmus KW - Dynamische Programmierung KW - Simulated Annealing KW - Optimization KW - Anytime-Algorithm KW - Dynamic Programming KW - Simulated Annealing Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-628 ER - TY - THES A1 - Raitner, Marcus T1 - Efficient visual navigation of hierarchically structured graphs T1 - Effiziente visuelle Navigation in hierarchisch strukturierten Graphen N2 - Visual navigation of hierarchically structured graphs is a technique for interactively exploring large graphs that possess an additional hierarchical structure. This structure is expressed in form of a recursive clustering of the nodes: in call graphs of telephone networks, for instance, the nodes are identified with phone numbers; they are clustered recursively through the implicit structure of the numbers, e. g., nodes with the same area code belong to a cluster. In order to reduce the complexity and the size of the graph, only those subgraphs that are currently needed are shown in detail, while the others are collapsed, i. e., represented by meta nodes. In such a graph view the subgraphs in the areas of interest are expanded furthest, whereas those on the periphery are abstracted. As the areas of interest change over time, clusters in a view need to be expanded or contracted. First and foremost, there is need for an efficient data structure for this graph view maintenance problem. Depending on the admissible modifications of the graph and its hierarchical clustering, three variants have been discussed in the literature: in the static case, everything is fixed; in the dynamic graph variant, only edges of the graph can be inserted and deleted; finally, in the dynamic graph and tree variant the graph additionally is subject to node insertions and deletions and the clustering may change through splitting and merging of clusters. We introduce a new variant, dynamic leaves, which is based on the dynamic graph variant, but additionally allows insertion and deletion of graph nodes, i. e., leaves of the hierarchy. So far efficient data structures were known only for the static and the dynamic graph variant, i. e., neither the nodes of the graph nor the clustering could be modified. As this is unsatisfactory in an interactive editor for hierarchically structured graphs, we first generalize the approach of Buchsbaum et. al (Proc. 8th ESA, vol. 1879 of LNCS, pp. 120–131, 2000), in which graph view maintenance is formulated as a special case of range searching over tree cross products, to the new dynamic leaves variant. This generalization builds on a novel technique of superimposing a search tree over an ordered list maintenance structure. With an additional factor of roughly O(log n/log log n), this is the first data structure for the problem of graph view maintenance where the node set is dynamic. Visualizing the expanding and contracting appropriately is the second challenge. We propose a local update scheme for the algorithm of Sugiyama and Misue (IEEE Trans. on Systems, Man, and Cybernetics 21 (1991) 876– 892) for drawing compound digraphs. The layered drawings that it produces have many applications ranging from biochemical pathways to UML diagrams. Modifying the intermediate results of every step of the original algorithm locally, the update scheme is more efficient than re-applying the entire algorithm after expansion or contraction. As our experimental results on randomly generated graphs show, the average time for updating the drawing is around 50 % of the time for redrawing for dense graphs and below 20 % for sparse graphs. Also, the performance gain is not at the expense of quality as regards the area of the drawing, which increases only insignificantly, and the number of crossings, which is reduced. At the same time, the locality of the updates preserves the user ’s mental map of the graph: nodes that are are not affected stay on the same level in the same relative order and expanded edges take the same course as the corresponding contracted edge; furthermore, expansion and contraction are visually inverse. Finally, our new data structure and the update scheme are combined into an interactive editor and viewer for compound (di-)graphs. A flexible and extensible software architecture is introduced that lays the ground for future research. It employs the well-known Model-View-Controller (MVC) paradigm to separate the abstract data from its presentation. As a consequence, the purely combinatorial parts, i. e., the compound (di-)graph and its views, are reusable without the editor front-end. A proof-of-concept implementation based on the proposed architecture shows its feasibility and suitability. KW - Dynamische Datenstruktur KW - Kognitive Landkarte KW - Graphenzeichnen Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-658 ER - TY - THES A1 - Lauren, Verena T1 - Semilineare Approximation in der Bildrekonstruktion N2 - In der Bildverarbeitung spielen Segmentierungsalgorithmen, bei denen die Art der zu segmentierenden Menge schon im Voraus festgelegt werden kann und nur noch ihre Größe und Lage angepasst werden muss, eine eher untergeordnete Rolle. Gründe hierfür sind vor allem komplizierte Zielfunktionen und daraus resultierende lange Rechenzeiten, die zudem meist kein optimales Ergebnis liefern. Dabei kann eine mengenbasierte Segmentierung durchaus sinnvoll eingesetzt werden, wenn gewisse Rahmenbedingungen eingehalten werden. In dieser Arbeit wird eine Theorie zur allgemeinen mengenbasierten Segmentierung vorgestellt und untersucht, unter welchen Bedingungen optimale Segmentierungsergebnisse erreicht werden können. Die anschließenden Anwendungen bestätigen die Nützlichkeit dieser Theorie. KW - Optimale Rekonstruktion KW - Rekonstruktion KW - Bildverarbeitung KW - Objektrekonstruktion KW - Bildrekonstruktion KW - image reconstruction KW - image processing KW - object reconstruction Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-730 ER - TY - THES A1 - Streckenbach, Mirko T1 - KABA - a system for refactoring Java programs T1 - KABA - ein System für Refactoring von Java-Programmen N2 - Refactoring is a well known technique to enhance various aspects of an object-oriented program. It has become very popular during recent years, as it allows to overcome deficits present in many programs. Doing refactoring by hand is almost impossible due to the size and complexity of modern software systems. Automated tools provide support for the application of refactorings, but do not give hints, which refactorings to apply and why. The Snelting/Tip analysis is a program analysis, which creates a refactoring proposal for a class hierarchy by analyzing how class members are used inside a program. KABA is an adaption and extension of the Snelting/Tip analysis for Java. It has been implemented and expanded to become a semantic preserving, interactive refactoring system. Case studies of real world programs will show the usefulness of the system and its practical value. KW - Java KW - Refactoring KW - Programmanalyse Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-638 ER - TY - THES A1 - Fischer, Andreas T1 - Peano-differentiable functions in O-Minimal structures T1 - Peano-differenzierbare Funktionen in o-minimalen Strukturen N2 - We discuss several aspects of Peano-differentiable functions which are definable in an o-minimal structure expanding a real closed field. After recalling some already known results about o-minimal structures we develop techniques for the intrinsic study of differentiable functions in these structures. After this we study (ordinary) differentiable functions definable in an o-minimal structure and their continuiuty properties along curves of different differentiability classes. Then we generalise (ordinary) differentiability to Peano-differentiability. We study differentiability of certain Peano-derivatives of definable functions and characterise the sets of non-continuity of these derivatives. In the end we study extendability of these functions defined on closed sets and give sufficient conditions by which we can extend functions as Peano-differentiable functions. KW - Semialgebraische Menge KW - Reelle Analysis KW - Reell-abgeschlossener Körper KW - Differenzierbare Funktion KW - Reelle algebraische Geometrie KW - o-minimale Struktur KW - Peano-differenzierbare Funktion KW - o-minimal structure KW - Peano-differentiable function Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-673 ER - TY - THES A1 - Wüchner, Patrick T1 - Energy-Efficient and Timely Event Reporting Using Wireless Sensor Networks T1 - Energieeffiziente und rechtzeitige Ereignismeldung mittels drahtloser Sensornetze N2 - This thesis investigates the suitability of state-of-the-art protocols for large-scale and long-term environmental event monitoring using wireless sensor networks based on the application scenario of early forest fire detection. By suitable combination of energy-efficient protocol mechanisms a novel communication protocol, referred to as cross-layer message-merging protocol (XLMMP), is developed. Qualitative and quantitative protocol analyses are carried out to confirm that XLMMP is particularly suitable for this application area. The quantitative analysis is mainly based on finite-source retrial queues with multiple unreliable servers. While this queueing model is widely applicable in various research areas even beyond communication networks, this thesis is the first to determine the distribution of the response time in this model. The model evaluation is mainly carried out using Markovian analysis and the method of phases. The obtained quantitative results show that XLMMP is a feasible basis to design scalable wireless sensor networks that (1) may comprise hundreds of thousands of tiny sensor nodes with reduced node complexity, (2) are suitable to monitor an area of tens of square kilometers, (3) achieve a lifetime of several years. The deduced quantifiable relationships between key network parameters — e.g., node size, node density, size of the monitored area, aspired lifetime, and the maximum end-to-end communication delay — enable application-specific optimization of the protocol. KW - Drahtloses Sensorsystem KW - Netzwerk KW - Elektronische Kommunikation KW - Protokoll KW - Kommunikationsprotokoll KW - Markov-Kette KW - Wireless sensor network KW - Energy efficiency KW - Communication protocol KW - Mathematical modeling KW - Continuous-time Markov chain KW - Finite-source retrial queue Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-27159 ER -