Autor*innen mit den meisten Dokumenten
Auflistung nach:
Neueste Veröffentlichungen
- TextdokumentEinsatz von Lasttransformationen und ihren Invertierungen zur realitätsnahen Lastmodellierung in Rechnernetzen(Ausgezeichnete Informatikdissertationen 2011, ) Heckmüller, StephanDie im Folgenden zusammengefasste Dissertation [Hec11] befasst sich mit der Charakterisierung von Lasten in Rechnernetzen. Da moderne Rechnernetze aus einer Vielzahl von Einzelkomponenten bestehen, welche die Charakteristika der Last verändern, wird besonderes Augenmerk auf die Abhängigkeit der Lasteigenschaften von der betrachteten Schnittstelle gelegt. Die Veränderung von Lasteigenschaften durch Auftragsverarbeitung wird durch das Konzept der Lasttransformation formalisiert. Hierbei ist Lasttransformation als Transformation einer Primärlast in eine Sekundärlast durch ein verarbeitendes System zu verstehen. Aufbauend auf dem Konzept der Lasttransformation werden Transformationen, wie sie durch häufig eingesetzte Verarbeitungsmechanismen in heutigen Netzen vorgenommen werden, als Abbildungen auf markovschen Prozessen modelliert. Hierzu werden für solche Primärlasten, die sich als Batch Markovian Arrival Process (BMAP) charakterisieren lassen, Beschreibungen der Sekundärlast als BMAP angegeben. Es werden modellbasierte Transformationen für Fragmentierungsmechanismen, verlustbehaftete Übertragungen und Ratenkontrollmechanismen vorgeschlagen und diskutiert. Umfangreiche Validationsstudien bestätigen den hohen Grad an Realitätsnähe der vorgeschlagenen modellbasierten Transformationen. Neben der Betrachtung der in Rechnernetzen auftretenden Lasttransformationen wird das hierzu inverse Problem der inversen Lasttransformation untersucht. Diesbezüglich wird die inverse Transformation von Auftragslängen untersucht. Darüber hinaus werden Verfahren vorgeschlagen, um die Charakteristika des Ankunftsprozesses eines zeitdiskreten Warteschlangensystems ausgehend von der Kenntnis des Abgangsprozesses zu rekonstruieren.
- TextdokumentExponentielle untere Schranken zur Lösung infinitärer Auszahlungsspiele und linearer Programme(Ausgezeichnete Informatikdissertationen 2011, ) Friedmann, OliverWir betrachten die Strategieverbesserungstechnik zur Lösung infinitärer Auszahlungsspiele sowie den Simplexalgorithmus zur Lösung damit assoziierter linearer Programme. Unser Beitrag zur Strategieverbesserung und zum Simplexverfahren besteht in der Konstruktion exponentieller unterer Schranken für mehrere Verbesserungs- bzw. Pivotregeln. Für jede Verbesserungsregel, die wir in dieser Arbeit unter die Lupe nehmen, konstruieren wir Zweispieler-Paritätsspiele, zu deren Lösung der entsprechend parametrisierte Strategieverbesserungsalgorithmus eine exponentielle Anzahl an Iterationen benötigt. Anschließend übersetzen wir diese Spiele in Einspieler-Markov-Entscheidungsprozesse, die wiederum beinahe direkt in konkrete lineare Programme überführt werden können, zu deren Lösung der entsprechende parametrisierte Simplexalgorithmus dieselbe Anzahl an Iterationen benötigt. Zusätzlich zeigen wir, wie sich die unteren Schranken auf expressivere Spieleklassen wie Auszahlungs- und stochastische Auszahlungsspiele übertragen lassen.
- TextdokumentInclusion of Pattern Languages and Related Problems(Ausgezeichnete Informatikdissertationen 2011, ) Freydenberger, Dominik D.Patternsprachen sind ein einfacher und eleganter Mechanismus zur Beschreibung von Sprachen, deren Wörter über Wiederholungen definiert sind. Trotz dieser Einfachheit sind viele der kanonischen Fragestellungen für Patternsprachen überraschend schwer zu lösen. Die vorliegende Arbeit befasst sich mit verschiedenen Aspekten des Inklusionsproblems für Patternsprachen. Neben Beweisen zur Unentscheidbarkeit dieses Problems, selbst für verschiedene stark eingeschränkte Unterklassen, werden die Resultate auf regex, eine in modernen Programmiersprachen weit verbreitete Erweiterung der regulären Ausdrücke übertragen. Ein weiterer Schwerpunkt der Untersuchungen sind die Existenz und Berechnung deskriptiver Pattern, welche inklusionsminimale Verallgemeinerungen beliebiger Sprachen durch Patternsprachen darstellen.
- TextdokumentQualitätsziel-orientierter Architekturentwurf und Traceability für weiterentwickelbare Software-Systeme(Ausgezeichnete Informatikdissertationen 2011, ) Bode, StephanDie Evolution von Softwaresystemen erfordert häufige Anpassungen z. B. aufgrund sich ändernder Geschäftsprozesse oder Technologien. Bisherige Methoden unterstützen dies nur unzureichend aufgrund mangelnder Berücksichtigung von Qualitätszielen wie Weiterentwickelbarkeit sowie mangelnder Nachvollziehbarkeit von Architekturentwurfsentscheidungen. Das neue Konzept Goal Solution Scheme, das Qualitätsziele über Architekturprinzipien auf Lösungsinstrumente durch explizite Abhängigkeiten abbildet, hilft geeignete Architekturlösungen entsprechend ihrem Einfluss auf die Qualitätsziele wie Weiterentwickelbarkeit auszuwählen und Entwurfsentscheidungen nachzuvollziehen. Das Schema ist in ein zielorientiertes Architekturentwurfsvorgehen eingebettet, das etablierte Methoden und Konzepte des Requirements Engineering und Architekturentwurfs verbessert und integriert. Dies wird ergänzt durch ein Traceability-Konzept, welches eine (halb-)automatische Erstellung von Traceability Links mit hoher Genauigkeit und Trefferquote ermöglicht. Die Realisierbarkeit des Entwurfsansatzes wurde mit einer Fallstudie eines Softwaresystems für mobile Serviceroboter gezeigt. Ein prototypisches Werkzeug names EMFTrace zeigt die Anwendbarkeit der Konzepte.
- TextdokumentGenerierung von Prozessoren aus Instruktionssatzbeschreibungen(Ausgezeichnete Informatikdissertationen 2011, ) Dreesen, RalfDie Automatisierung der Prozessorentwicklung ist ein seit Langem untersuchtes Thema, das durch den zunehmenden Einsatz anwendungsspezifischer Prozessoren (ASIPs) in Ein-Chip-Systemen (SoCs) erheblich an Bedeutung gewonnen hat. Bei bisherigen Ansätzen werden Prozessoren auf mikroarchitektonischer Ebene beschrieben, wodurch ein Entwickler viele komplexe und fehleranfällige Aspekte definieren muss. Die Dissertation [Dre11] verfolgt einen bisher kaum untersuchten Ansatz, bei dem nur der Instruktionssatz eines Prozessors modelliert wird. Die Mikroarchitektur wird vollständig und automatisch durch neu entworfene Methoden erzeugt. Durch Variation eines Generatorparameters wird so ein Satz kompatibler Prozessoren mit verschiedenen physikalischen und dynamischen Eigenschaften erzeugt. Abhängig vom Einsatzgebiet kann aus diesem Entwurfsraum eine passende Implementierung ausgewählt werden.
- TextdokumentTheorie künstlicher Immunsysteme(Ausgezeichnete Informatikdissertationen 2011, ) Zarges, ChristineKünstliche Immunsysteme sind adaptive Systeme, die sich bezüglich ihrer Komponenten und Funktionsweisen an Theorien natürlicher Immunsysteme orientieren und diese nachahmen. Wir analysieren verschiedene Mechanismen, die dabei typischerweise zum Einsatz kommen. Mit dieser Arbeit stellen wir uns damit einer der größten Herausforderungen des Gebietes und leisten einen signifikanten Beitrag zu dessen Weiterentwicklung. Wir untersuchen zwei zentrale Komponenten künstlicher Immunsysteme, Variation und Alterung. Da unsere theoretischen Analysen zum Verständnis der verwendeten Verfahren in der Praxis beitragen sollen, liegt unser Fokus auf der praktischen Relevanz. Einem grundlegenden Aspekt dieser Fragestellung ist abschließend ein eigener Abschnitt gewidmet.
- TextdokumentGenome Rearrangement Algorithmen(Ausgezeichnete Informatikdissertationen 2011, ) Bader, MartinDurch die steigende Anzahl von vollständig sequenzierten Genomen gewinnt der Vergleich von Spezies auf Basis der sequenzierten Genome immer mehr an Bedeutung. Im Gegensatz zum klassischen Ansatz, welcher ein Distanzmaß basierend auf Punktmutationen verwendet, lassen Genome Rearrangement Algorithmen kleinere Mutationen ausser acht und berücksichtigen nur größere Umstrukturierungen, welche die Reihenfolge der Gene auf den Chromosomen verändern. Dadurch sind diese Algorithmen ein wertvolles Hilfsmittel zum Vergleich von Spezies, welche seit Millionen von Jahren divergieren, sowie von sich schnell verändernden Genomen, wie sie zum Beispiel in Krebszellen vorkommen. Die Untersuchung dieser Genomumstrukturierungen führt zu einer Vielzahl von algorithmischen Fragestellungen, wie die Berechnung von evolutionären Distanzen, die Rekonstruktion evolutionärer Ereignisse und der Genreihenfolge in hypothetischen Vorfahren, bis hin zur Berechnung ganzer phylogenetischer Bäume. In der hier vorgestellten Dissertation [Bad11] werden einige dieser Problemstellungen sowohl von der theoretischen als auch von der praktischen Seite untersucht. So wird gezeigt, dass das Median-Problem, bei welchem ein möglichst plausibler Vorfahr für drei gegebene Genome gesucht wird, sowohl für die Transpositionsdistanz als auch für die gewichtete Reversal- und Transpositionsdistanz zu den NP-vollständigen Problemen gehört. Dazu wird ein Algorithmus vorgestellt, welcher in der Praxis vorkommende Instanzen dieser Probleme dennoch lösen kann. Desweiteren werden ein neuer Algorithmus zur phylogenetischen Rekonstruktion basierend auf diesen Distanzen sowie erstmals Algorithmen zum paarweisen Genomvergleich, welche Duplikationen und Deletionen beliebiger Länge zulassen, vorgestellt. Ein weiteres Ergebnis der Dissertation, auf welches in dieser Zusammenfassung jedoch nicht näher eingegangen werden soll, ist eine effiziente Implementierung eines Vor- und Nachverarbeitungsschritt, welcher für viele Genome Rearrangement Algorithmen benötigt wird.
- TextdokumentEntwicklung einer Komplexitätstheorie für randomisierte Suchheuristiken: Black-Box-Modelle(Ausgezeichnete Informatikdissertationen 2011, ) Winzen, CarolaRandomisierte Suchheuristiken sind problemunabhängige Algorithmen, die sowohl im wissenschaftlichen als auch im industriellen Kontext zur Optimierung von schwierigen Problemen genutzt werden. Sie sind einfach zu implementieren, lassen sich vielseitig einsetzen und liefern überraschend häufig bereits in kurzer Zeit sehr gute Ergebnisse. Daher sind randomisierte Suchheuristiken weit verbreitet. Ein großes Problem in Anwendung von randomisierten Suchheuristiken ist jedoch die Tatsache, dass sich schwer vorhersagen lässt, ob sich das zu optimierende Problem gut durch eine geeignete Heuristik lösen lässt oder ob andere problemspezifische Verfahren deutliche besser geeignet sind. Mit meiner Dissertation leisten wir einen Beitrag zur Entwicklung einer Komplexitätstheorie für randomisierte Suchheuristiken. Unser langfristiges Ziel ist die Charakterisierung von Problemklassen in solche, die sich schnell und zuverlässig durch Suchheuristiken optimieren lassen und solche, für die grundsätzlich andere Methoden besser geeignet sind.
- TextdokumentDynamische Code-Evolution für Java(Ausgezeichnete Informatikdissertationen 2011, ) Würthinger, ThomasDynamische Code-Evolution ermöglicht strukturelle Änderungen an laufenden Programmen. Das Programm wird temporär angehalten, der Programmierer verändert den Quelltext und dann wird die Ausführung mit der neuen Programm-Version fortgesetzt. Diese Arbeit beschreibt einen neuartigen Algorithmus für die unlimitierte dynamische Neudefinition von Java-Klassen in einer virtuellen Maschine. Die unterstützten Änderungen beinhalten das Hinzufügen und Entfernen von Feldern und Methoden sowie Veränderungen der Klassenhierarchie. Der Zeitpunkt der Veränderung ist nicht beschränkt und die aktuell laufenden Ausführungen von alten Versionen einer Methode werden fortgesetzt. Mögliche Verletzungen der Typsicherheit werden erkannt und führen zu einem Abbruch der Neudefinition. Die entwickelten Techniken können die Entwicklung neuer Programme beschleunigen sowie den Versionswechsel ohne Abschaltpause von Server-Anwendungen ermöglichen. Die Arbeit präsentiert auch ein Programmiermodell für sichere dynamische Aktualisierungen und diskutiert nützliche Limitierungen, die es dem Programmierer ermöglichen, über die semantische Korrektheit einer Aktualisierung Schlussfolgerungen zu ziehen. Alle Algorithmen sind in der Java HotSpot VM implementiert und es wird derzeit seitens Oracle an der Integration in die offizielle Java-Version gearbeitet. Die Evaluierung zeigt, dass die neuen Fähigkeiten weder vor noch nach einer dynamischen Veränderung einen negativen Einfluss auf die Spitzenleistung der virtuellen Maschine haben.
- TextdokumentSymbolische Methoden für die probabilistische Verifikation – Zustandsraumreduktion und Gegenbeispiele(Ausgezeichnete Informatikdissertationen 2011, ) Wimmer, RalfEin bekanntes Hindernis für die formale Verifikation von Systemen bildet die potentiell stark anwachsende Größe des Zustandsraums, genannt "Zustandsraumexplosion". Dieses Problem konnte für digitale Schaltungen durch den Einsatz symbolischer Methoden zufriedenstellend gelöst oder zumindest entscheidend entschärft werden. Für probabilistische Systeme, die als Markow-Kette oder Markow-Entscheidungsprozess modelliert sind, brachte die direkte Übertragung dieser symbolischen Methoden bisher keinen Durchbruch. In dieser Arbeit stellen wir zwei neue Ansätze vor, mit denen Markow-Modelle mit sehr großen Zustandsräumen verifiziert werden können. Die erste Methode ist ein symbolisches Verfahren zur Vorverarbeitung: Zu jedem Markow-Modell berechnen wir mit rein symbolischen Verfahren das kleinste Modell, das in den interessierenden Eigenschaften mit dem Original-Modell übereinstimmt. Die Verifikation kann danach auf dem minimierten Modell durchgeführt werden. Das zweite offene Problem, das in der Dissertation gelöst wird, ist die symbolische Berechnung von Gegenbeispielen, wenn Sicherheitseigenschaften von Markow-Ketten mit diskreter Zeit verletzt sind. Anhand von Experimenten wird gezeigt, dass die neu entwickelten Verfahren den bisher verfügbaren Verfahren hinsichtlich der Laufzeit bzw. der Größe der handhabbaren Systeme deutlich überlegen sind.