Mitarbeiter Lehrstuhl/Einrichtung der Fakultät für Informatik und Mathematik
Refine
Year of publication
- 2005 (7) (remove)
Document Type
- Doctoral Thesis (6)
- Preprint (1)
Has Fulltext
- yes (7)
Is part of the Bibliography
- no (7)
Keywords
- Anytime-Algorithm (1)
- Anytime-Algorithmus (1)
- Betriebssystem (1)
- Bildrekonstruktion (1)
- Bildverarbeitung (1)
- Cantor-Menge (1)
- Component-Based (1)
- Dataflow Graph (1)
- Datenflussgraph (1)
- Differenzierbare Funktion (1)
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.
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.
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.
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.
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.
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.
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.