Logo des Repositoriums

D06 (2005) - Ausgezeichnete Informatikdissertationen

https://dl.gi.de/handle/20.500.12116/4401

Dorothea Wagner et al. (Hrsg.)

GI-Edition - Lecture Notes in Informatics (LNI), D-6

Bonner Köllen Verlag (2005)

ISBN 3-88579-330-X

Auflistung nach:

Auflistung D06 (2005) - Ausgezeichnete Informatikdissertationen nach Titel

1 - 10 von 24
  • Textdokument
    Algorithmen und Softwarewerkzeuge für Vergleichende Genomanalyse
    (Ausgezeichnete Informatikdissertationen 2005, 2006) Abouelhoda, Mohamed Ibrahim
    Vergleichende Genomanalyse ist ein relativ neues Gebiet der Bioinformatik, das durch die Verfügbarkeit einer immer größer werdender Zahl sequenzierter Genomen an Bedeutung gewinnt. Die vorliegende Dissertation präsentiert Algorithmen und Softwarewerkzeuge, mit denen mehrere Genome effizient verglichen werden können. Die vorgestellten Algorithmen lösen bisher offene Probleme der theoretischen Bioinformatik. In der Praxis reduzierten wir sowohl die Rechenzeit als auch den Platzbedarf für das Vergleichen der großen Genome.
  • Textdokument
    Approximability of cycle covers and smoothed analysis of binary search trees
    (Ausgezeichnete Informatikdissertationen 2005, 2006) Manthey, Bodo
    Der Beitrag enthält eine Zusammenfassung der Dissertation Approxima- ” bility of Cycle Covers and Smoothed Analysis of Binary Search Trees“. Eine Zyklenüberdeckung eines Graphen ist ein Teilgraph, der nur aus Zyklen besteht, so dass jeder Knoten Teil genau eines Zyklus ist. Bei einer L-Zyklenüberdeckung muss zusätzlich die Länge jedes Zyklus in der Menge L liegen. Im ersten Teil der Dissertation wurde die Komplexität und Approximierbarkeit des Problems untersucht, L- Zyklenüberdeckungen maximalen Gewichts zu berechnen. Es wurden einerseits effiziente Approximationsalgorithmen zur Berechnung von L-Zyklenüberdeckungen entwickelt. Andererseits wurde bewiesen, dass L-Zyklenüberdeckungsprobleme für fast alle Mengen L nicht beliebig gut approximiert werden können. Im zweiten Teil der Dissertation wurde eine Smoothed Analysis der Höhe binärer Suchbäume durchgeführt. Die Smoothed Analysis interpoliert zwischen der Worst- Case-Komplexität, die oft zu pessimistisch ist und durch pathologische“ Instanzen ” dominiert wird, und der Average-Case-Komplexität, die oft zu optimistisch ist.
  • Textdokument
    ClusterRAID Architektur und Prototyp eines Verteilten Fehlertoleranten Massenspeichersystems fuer Cluster
    (Ausgezeichnete Informatikdissertationen 2005, 2006) Wiebalck, Arne
    Dieser Artikel beschreibt die Architektur und die Prototyp-Implementierung eines verteilten, fehlertoleranten Massenspeichersystems für Cluster. Die grundlegende Idee der Architektur ist es, die lokale Festplatte eines Clusterknotens zuverlässig zu machen, ohne dabei die Schnittstelle für das Betriebssystem bzw. für die Anwendung zu verändern. Hierbei werden fehler-korrigierende Codes eingesetzt, die es ermöglichen, die Anzahl der zu tolerierenden Fehler und somit die Zuverlässigkeit des Gesamtsystems beliebig einzustellen. Das Anordnungsschema für die Datenblöcke innerhalb des Systems berücksichtigt das Zugriffsverhalten einer ganzen Klasse von Applikationen und kann so die erforderlichen Netzwerkzugriffe auf ein Minimum reduzieren. Gründliche Messungen und Funktionstests des Prototypen, sowohl allein als auch im Zusammenwirken mit lokalen und verteilten Dateisystemen, belegen die Validität des Konzeptes.
  • Textdokument
    Completeness for parallel access to NP and counting class separation
    (Ausgezeichnete Informatikdissertationen 2005, 2006) Spakowski, Holger
    Die Dissertation beschäftigt sich mit Problemen, die vollständig für die Komplexitätsklasse PNP sind, sowie mit der Separation von Zählklassen. PNP ist die Klasse der Probleme, die sich effizient mit parallelem Zugriff auf NP lösen lassen. Wir untersuchen die Komplexität von mit Wahlsystemen assoziierten Problemen. Wahlsysteme sind Vorschriften, nach denen aus einer Kandidatenmenge die Gewinner einer Abstimmung bestimmt werden können. Wir beweisen, daß das Gewinner- Problem für die Wahlsysteme von Kemeny und Young beide vollständig für die Klasse PNP sind. Weiterhin betrachten wir zwei prominente Heuristiken für die Approximation des NP-vollständigen Problems der minimalen Knotenüberdeckung. Wir weisen nach, daß gewisse Entscheidungsprobleme, die mit der Qualität der Approximation durch diese Heuristiken in Zusammenhang stehen, vollständig für PNP sind. Der letzte Teil der Dissertation beantwortet Fragen, die in der einflußreichen Arbeit von Fenner, Fortnow und Kurtz im Jahre 1994 aufgeworfen wurden: Wir zeigen, daß die Zählklassen LWPP und WPP nicht uniform gap-definierbar sind. Desweiteren konstruieren wir ein Orakel, relativ zu dem WPP nicht abgeschlossen unter polynomialzeitbeschränkter Turing-Reduzierbarkeit ist. Dies hat zur Folge, daß ein Beweis für die Gleichheit der ähnlich definierten Klassen LWPP und WPP nichtrelativierbar sein muß. Wir erhalten diese Resultate durch Anwendung einer bekannten Technik, bei der Orakel-Turingmaschinen in multilineare Polynome mit kleinem Grad kodiert werden. Wir beweisen dazu eine neue kombinatorische Eigenschaft solcher Polynome.
  • Textdokument
    Design and quantitative analysis of protocols for epidemic information disseminationin mobile ad hoc networks
    (Ausgezeichnete Informatikdissertationen 2005, 2006) Waldhorst, Oliver
    Die vorgestellte Arbeit [Wal05] beschäftigt sich mit dem Gebiet der Protokolle für die epidemische Verbreitung von Informationen in mobilen Ad-hoc Netzen (MANET). Solche Protokolle nutzen die in diesen Netzen vorhandene Mobilität und übertragen Informationen, wenn sich zwei Geräte ,,begegnen“ (d.h. sich in Funkreichweite befinden), ähnlich der Übertragung einer ansteckenden Krankheit zwischen Individuen. Die Arbeit setzt sich aus drei Forschungsbeiträgen in diesem Gebiet zusammen. (1) Ein universell einsetzbarer verteilter Suchdienst für mobile Anwendungen in MANET wird vorgestellt, der auf epidemischer Verbreitung von Einträgen eines verteilten Index beruht. (2) Verschiedene Mechanismen zur Verbreitung von Präsenzinformationen in einem MANET werden untersucht und basierend auf den Ergebnissen dieser Untersuchungen ein Präsenzdienst für ein mobiles Instant Messaging System vorgeschlagen. (3) Ein neuartiger stochastischer Modellierungsansatz zur Analyse und Optimierung von Systemen zur epidemischen Informationsverbreitung wird vorgeschlagen und auf ein existierendes System angewendet.
  • Textdokument
    Effiziente Generierung und Ausfuehrung von DAG-strukturierten Anfragegraphen
    (Ausgezeichnete Informatikdissertationen 2005, 2006) Neumann, Thomas
    Datenbanksysteme verwenden traditionell baumstrukturierte Pläne für die Anfragebearbeitung. Einige Optimierungstechniken wie Faktorisierung lassen sich mit Bäumen aber nicht gut formulieren. Eine attraktive Möglichkeit, die Pläne ausdrucksstärker zu machen, ist die Verallgemeinerung von Bäumen zu gerichteten azyklischen Graphen (DAGs). Existierende Ansätze betrachten DAGs nur in Spezialfällen, sie sind nicht voll in die Anfrageoptimierung integriert. Der hier vorgestellte Plangenerator ist der erste, der generisch optimale DAG-strukturierte Pläne erzeugt. Die experimentellen Ergebnisse zeigen, dass die so erzeugten Pläne teilweise deutlich effizienter sind.
  • Textdokument
    Frontmatter
    (Ausgezeichnete Informatikdissertationen 2005, 2006)
  • Textdokument
    Graphbasierte Modelle als Kollaborationsmedien
    (Ausgezeichnete Informatikdissertationen 2005, 2006) Pinkwart, Niels
    Dieser Artikel beschreibt einen theoretischen Ansatz und ein darauf aufbauendes Softwaresystem zur Unterstützung von Kollaboration mittels graphbasierter Modelle - die Arbeit verbindet Aspekte interaktiver Systeme (in Echtzeit manipulierbare und simulierfähige Modelle) mit einer flexiblen Definition von Kooperationsszenarien. Zunächst werden in diesem Artikel die Begriffe visueller getypter Graphen und “Reference Frames” als formale Notationen für kollaborativ nutzbare Modelle bzw. interoperable Modellierungssprachen eingeführt. Der Artikel stellt Cool Modes, eine Implementierung des Reference Frame-Ansatzes auf Basis einer flexiblen Softwarearchitektur, vor. Diese Anwendung verwaltet mehrere extern definierbare Reference Frames und unterstützt Kollaboration mit Hilfe gemeinsam nutzbarer Arbeitsbereiche. Hierbei werden Syntaxregeln, Modellinterpretationsund Simulationsmöglichkeiten ebenso unterstützt wie partielle Modellsynchronisation unter Berücksichtigung semantischer Konsistenz: über spezielle Benutzerschnittstellen zu “Reference Frames” wird es Anwendern ermöglicht, heterogene Modelle (die aus Elementen verschiedener Sprachen zusammengesetzt sind) gemeinsam zu erstellen und zu nutzen. Abschließend beschreibt dieser Artikel einige Anwendungsbeispiele aus dem Lehr/Lernbereich, in denen Cool Modes im Rahmen von EU-Forschungsprojekten und Unterrichtsreihen an Schulen eingesetzt worden ist.
  • Textdokument
    High quality surface generation and efficient multiresolution editing basedon triangle meshes
    (Ausgezeichnete Informatikdissertationen 2005, 2006) Botsch, Mario
  • Textdokument