Logo des Repositoriums

D04 (2003) - Ausgezeichnete Informatikdissertationen

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

Dorothea Wagner et al. (Hrsg.)

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

Bonner Köllen Verlag (2003)

ISBN 3-88579-408-X

Auflistung nach:

Auflistung D04 (2003) - Ausgezeichnete Informatikdissertationen nach Titel

1 - 10 von 22
  • Textdokument
    Advanced slicing of sequential and concurrent programs
    (Ausgezeichnete Informatikdissertationen 2003, 2004) Krinke, Jens
    Program Slicing ist eine Technik zur Identifikation von Anweisungen, die andere Anweisungen beeinflussen können. Trotz seit nunmehr 25 Jahren anhaltender Forschung hat Program Slicing immer noch Probleme, die eine verbreitete Benutzung verhindern: Slices können zu groß oder zu unverständlich werden, oder ihre Berechnung kann zu teuer oder zu kompliziert für echte Programme sein. Diese Dissertation präsentiert Lösungen und Auswege aus diesen Problemen. Sie enthält einerseits eine Reihe von Slicing-Verfahren unterschiedlicher Präzision und Geschwindigkeit. Andererseits enthält sie verschiedenste Verfahren, die dem Benutzer helfen, Slices leichter zu verstehen indem die berechneten Slices mehr auf seine Bedürfnisse fokussiert werden. Alle vorgestellten Verfahren wurden im VALSOFT-System implementiert und gründlich evaluiert. Die dem Slicing zugrunde liegende Datenstruktur sind Programmabhängigkeitsgraphen. Diese können auch für andere Anwendungen benutzt werden: Ein neues Verfahren zur Entdeckung von dupliziertem Code identifiziert ähnliche Teilgraphen in Programmabhängigkeitsgraphen. Dieses Verfahren kann modifizierte Duplikate besser erkennen als andere Verfahren. Auf der theoretischen Seite präsentiert diese Dissertation ein hochpräzises Verfahren zum Slicing nebenläufiger prozeduraler Programme, wobei optimales Slicing bekannterweise nicht entscheidbar ist. Dieses Verfahren ist das erste zum Slicen nebenläufiger Programme, das nicht auf Inlining aufgerufener Prozeduren zurückgreift.
  • Textdokument
    Aufzählbarkeitsklassen von Turingmaschinen und endlichen Automaten
    (Ausgezeichnete Informatikdissertationen 2003, 2004) Tantau, Till
    Der Beitrag enthält eine Zusammenfassung der Dissertation n Structural Similarities of Finite Automata and Turing Machine Enumerability Classes. Die Dissertation [Ta03] eröffnet mit folgenden Worten: My Thesis: The enumerability and verboseness classes of finite automata on the one hand and of Turing machines on the other hand share numerous structural properties. They do not share these properties with intermediate resource-bounded computational models. Especially the finite automata versions of these classes have applications in areas unrelated to enumerability. Two methods that are used for the proofs of the structural similarities - elementary definitions of regular relations and branch diagonalisation - will be applicable to other proofs in automata, complexity, and recursion theory. Auf den folgenden 150 Seiten wird dann versucht, mittels etwa sechzig Sätzen, Korollaren und Lemmata diese These zu belegen und den Leser oder die Leserin von ihrer Richtigkeit zu überzeugen - nicht mehr und nicht weniger. Es wird sogar frech behauptet, man könne sich die weitere Lektüre der Arbeit sparen, sobald man von der {\tt>\hskip-.5e>}Thesis{\tt<\hskip-.5e<} überzeugt ist. Mein Hauptanliegen im vorliegenden Beitrag ist zu erläutern, was die obige These eigentlich genau besagt. Mathematische Exaktheit steht dabei weniger im Vordergrund als eine möglichst allgemein verständliche Darstellung der Ideen. Dazu werden zunächst die Konzepte wie Aufzählbarkeit oder Verboseness-Klassen genauer erklärt, dann die zentralen Resultate beschrieben, eine neue Beweismethode kurz angedeutet und zum Schluss Anwendungen skizziert. Die Konzepte 1.1 Turingmaschinen, endliche Automaten und Polynomialzeitmaschinen Schon der Titel der Dissertation verrät, dass es in ihr um Gemeinsamkeiten der beiden ältesten Maschinenmodelle der Informatik geht: Turingmaschinen und endliche Automaten. Grob gesprochen ist das Turingmaschinenmodell das mächtigste {\tt>\hskip-.5e>}sinnvolle{\tt<\hskip-.5e<} Maschinenmodell, das es gibt. {\tt>\hskip-.5e>}Mächtig{\tt<\hskip-.5e<} bedeutet hier, dass Turingmaschinen alles berechnen können, was sich überhaupt berechnen lässt. Da unklar ist, was die richtige Definition von {\tt>\hskip-.5e>}was sich überhaupt berechnen lässt{\tt<\hskip-.5e<} ist, ist es kein mathematischer Satz, dass Turingmaschinen allmächtig sind, sondern lediglich eine These, die aber der klangvollen Namen {\tt>\hskip-.5e>}Church'sche These{\tt<\hskip-.5e<} trägt. Praktisch kann man sich eine Turingmaschine als einen Rechner vorstellen, der über beliebig viel Speicher verfügt und der beliebig lange rechnen darf. Am anderen Ende des Spektrums der Maschinenmodelle finden sich die endlichen Automaten. Diese verarbeiten ihre Eingabe, indem sie sie einmal von links nach rechts lesen und am Ende sofort eine Ausgabe produzieren. Endliche Automaten benötigen keinerlei Speicher und ihre Rechenzeit ist proportional zur Eingabelänge. Vom praktischen Standpunkt aus sind Turingmaschinen viel zu mächtig, da sie Probleme spielend lösen können, die nachweislich nicht in vertretbarer Zeit (wie beispielsweise der zu erwartenden Lebensdauer des Universums) zu lösen sind. Endliche Automaten sind nicht mächtig genug, da sie manche Probleme nachweislich nicht lösen können, die ein Taschenrechner mit links löst. In der Komplexitätstheorie werden deshalb Modelle wie Polynomialzeitmaschinen betrachtet, die {\tt>\hskip-.5e>}in der Mitte liegen{\tt<\hskip-.5e<} und die die Fähigkeiten realer Computer realistischer modellieren.
  • Textdokument
    Bessere Software durch Querschneidende Module
    (Ausgezeichnete Informatikdissertationen 2003, 2004) Ostermann, Klaus
    Gute Separierung der Belange in Softwaresystemen ist der Schlüssel, um mit wachsender Komplexität umzugehen. Die wichtigste Aufgabe von Programmiersprachen in Bezug auf dieses Ziel ist die Bereitstellung von geeigneten Mitteln, um das mentale Modell eines Domänenexperten so direkt wie möglich in einer Programmiersprache festhalten zu können und damit die intellektuelle Distanz zwischen dem mentalen Modell und dem Programmcode so gering wie möglich zu halten. Dies ist der Kontext, im dem die hier zusammengefasste Dissertation versucht, den aktuellen Stand der Technik voranzubringen. Ein besonderer Schwerpunkt liegt dabei auf Sprachkonzepten für die Unterstützung sogenannter “querschneidender Modelle”, die aus unterschiedlichen Sichten auf ein Softwaresystem resultieren und mit konventioneller Technologie zu Programmen mit schlechten softwaretechnologischen Eigenschaften wie Wartbarkeit und Wiederverwendbarkeit führen. Die Resultate dieser Arbeit bilden die Grundlage der Programmiersprache Caesar, die zur Zeit in mehreren industriellen Projekten evaluiert wird. Neue Sprachkonstrukte für eine bessere Separierung der Belange (separation of concerns) in der Softwareentwicklung werden benötigt! Diese These ist der Ausgangspunkt der diesem Dokument zugrundeliegenden Dissertation [Os03]. Zunächst einmal: Was ist gemeint mit “guter Separierung der Belange”? Ein Belang (concern) ist jede kohärente Angelegenheit in einer Problemdomäne. Ein Be- lang kann ein beliebig komplexes Konzept wie “Sicherheit” oder “Lohnbuchhaltung” sein, oder primitive Konzepte wie “warten auf ein Mausereignis”. Separierung der Belange ist eng verwandt mit Kompositionsund Dekompositionsmechanismen in Programmiersprachen, also die Partitionierung eines Softwaresystems in kleine Teile (Dekomposition) und das Zusammenbauen eines Softwaresystems anhand dieser kleinen Teile (Komposition). Diese Definition sagt jedoch nichts darüber, wie ein Softwaresystem dekomponiert werden soll. Zum Beispiel könnte ein Programm in zwei Teile zerlegt werden, bei dem ein Teil die geraden Zeilennummern und ein anderer Teil die ungeraden Zeilennummern enthält. Offensichtlich macht diese Dekomposition jedoch keinen Sinn. Wir benötigen Kriterien, die benutzt werden können, um geeignete Dekompositionen eines Systems zu finden. Dies ist der Punkt, an dem sich das Konzept der Separierung der Belange, welches auf Parnas [Pa72a] und Dijkstra [Di76] zurückgeht, als nützlich erweist. Dieses Konzept postuliert, dass jeder Teil eines dekomponierten Softwaresystems für einen wohldefinierten Aspekt eines Systems verantwortlich sein sollte. Jeder Teil sollte sowenig Wissen wie möglich über andere Teile eines Systems haben, so daß es möglich ist, jeden Aspekt einzeln und isoliert von allen anderen Aspekten zu betrachten. Bessere Software durch Querschneidende Module In konventionellen Programmiersprachen wird dieses Konzept durch Module unterstützt, die eine hierarchische Aufteilung der Softwaredomäne ermöglichen und damit eine direkte Abbildung hierarchischer Modelle ermöglichen. Die dieser Arbeit zugrunde liegende These ist, daß neben einer Unterstützung für hierarchische Modelle noch eine zweite Di- mension von Modellen durch Programmiersprachen unterstützt werden sollte, nämlich sogenannte querschneidende Modelle, die durch unterschiedliche Sichten desselben Systems zustandekommen. Der Rest dieses Artikels ist wie folgt strukturiert: In Abschnitt 1 wird kurz die Bedeutung guter Separierung der Belange für die Softwareentwicklung erläutert. In Abschnitt 2 wird der Begriff der querschneidenden Modelle eingeführt und dessen Bedeutung für die Softwaretechnologie erläutert. Schliesslich wird Abschnitt 3 einen kleinen Überblick darüber geben, wie querschneidende Modelle in der Programmiersprache Caesar unterstützt werden.
  • Textdokument
    Bi-decomposition of function sets using multi-valued logic
    (Ausgezeichnete Informatikdissertationen 2003, 2004) Lang, Christian
    Logiksynthese für neue Schaltungstechniken und Data Mining sind zwei Anwendungsgebiete für die Synthese von Funktionen in mehrwertiger Logik. Bi-De- komposition ist eine Methode der Logiksynthese, bei der die gegebene Funktion in zwei einfachere Teilfunktionen zerlegt wird. In dieser Arbeit werden Algorithmen zur Darstellung und Bi-Dekomposition von Funktionsmengen in mehrwertiger Logik entwickelt. Als Ergebnis der Implementierung dieser Algorithmen ist das modulare Programmsystem YADE entstanden, das mehrwertige Funktionsmengen in ein Netzwerk von mehrwertigen Gattern dekomponiert. Vergleiche mit anderen Dekomposern zeigen, dass durch Bi-Dekomposition erzeugte Gatternetzwerke eine geringere Komplexität aufweisen.
  • Textdokument
    Data management and routing in general networks
    (Ausgezeichnete Informatikdissertationen 2003, 2004) Räcke, Harald
  • Textdokument
    Discrete scale-space formulation and multiscale edge extraction
    (Ausgezeichnete Informatikdissertationen 2003, 2004) Lim, Ji-Young
    In den letzten Jahren hat sich die Skalenraum-Theorie in den verschiedensten Anwendungen bewährt. Die in der Literatur vorherrschenden Multiskalen- Verfahren zur Kantenextraktion basieren auf der linearen Skalenraum-Theorie, sind jedoch nur für kontinuierliche Signale gültig. Dieser Beitrag fasst die Arbeiten aus meiner Dissertation über eine Erweiterung zu einer mehrdimensionalen diskreten Skalenraum-Formulierung sowie die Ergebnisse theoretischer und experimenteller Un- tersuchungen von Multiskalen-Verfahren zur Kantenextraktion basierend auf mehrdimensionalen Kantenmodellen zusammen.
  • Textdokument
    Exakte Algorithmen für NP-harte Probleme auf Netzwerken
    (Ausgezeichnete Informatikdissertationen 2003, 2004) Alber, Jochen
    Wir befassen uns in der Arbeit mit dem Entwurf von exakten Algorithmen für verschiedene NP-vollständige Optimierungsprobleme auf Graphen, wie beispielsweise Vertex Cover, Independent Set oder Dominating Set. Im Vordergrund der Arbeit stehen exakte Lösungsverfahren mit beweisbaren Laufzeitschranken. Wir verfolgen dabei den jüngst vorgeschlagenen Ansatz sogenannter “parametrisierter Algorithmen”. Dabei untersuchen wir sowohl von theoretischer, als auch von praktischer Seite unterschiedliche Methoden des Algorithmen-Designs: Datenreduktion, beschränkte Suchbäume, Separation von Graphen und das Konzept von Baumzerlegungen. Schließ- lich stellen wir ein Software-Paket vor, welches im Rahmen dieses Projektes entwickelt wurde und eine Vielzahl der entwickelten Algorithmen implementiert.
  • Textdokument
    Frontmatter
    (Ausgezeichnete Informatikdissertationen 2003, 2004)
  • Textdokument
    Kapazität und Planung von Wideband CDMA Systemen
    (Ausgezeichnete Informatikdissertationen 2003, 2004) Leibnitz, Kenji
    Das Ziel dieser Arbeit ist die Herleitung analytischer Modelle, um eine Leistungsbewertung von Mobilfunksystemen der dritten Generation (3G) zu ermöglichen. Als eine der wichtigsten Einflussfaktoren wird das dynamische Verhalten der Sendeleistungsregelung (engl. power control) erachtet. Die Aufgabe von Power Control ist es die Leistung der Sendestation derart einzustellen, dass sie möglichst minimal ist, jedoch auch den Mindestanforderungen für die empfangene Signalleistung genügt. Durch dieses dynamische Verhalten entsteht eine Wechselwirkung zwischen der Zellgröße, Kapazität und der Dienstgüte im System. Es ist daher von entscheidender Wichtigkeit vor der Einführung neuer Systeme die Systemstabilität zu untersuchen und alle Einflussfaktoren zu identifizieren.
  • Textdokument
    Multiplikation in eingeschränkten Branchingprogrammmodellen
    (Ausgezeichnete Informatikdissertationen 2003, 2004) Wölfel, Philipp
    und Ausblick Wir können nicht erwarten, auf die eingangs gestellte Frage nach der Komplexität der Multiplikation in naher Zukunft für irgendein allgemeines Rechenmodell wie Schaltkreise oder Branchingprogramme eine vollständige Antwort zu finden. Wir können aber versuchen, nach und nach zu umfassenderen Erkenntnissen über die Multiplikation zu gelangen und neue Techniken zum Nachweis oberer und unterer Schranken zu entwickeln, um auf diese Weise die Komplexität der Multiplikation besser einzugrenzen. Die Ergebnisse der Dissertation stellen einen weiteren Schritt in diese Richtung dar. Dass dies nicht der letzte war, zeichnet sich schon an einer Reihe weiterführender Erkenntnisse über die Branchingprogrammkomplexität der Multiplikation ab. So konnten z. B. in [BWW02] und [BW] exponentielle untere Schranken in weiteren eingeschränkten nichtdeterministischen FBDD-Modellen nachgewiesen werden und kürzlich zeigten Sauerhoff und Woelfel exponentielle untere Schranken für nichtdeterministische Branchingprogramme, bei denen jede Variable auf jedem graphtheoretischen Pfad konstant oft vorkommen darf [SW03]. Literatur [Br85] Bryant, R. E.: Symbolic manipulation of boolean functions using a graphical representation. Proceedings of the 22nd ACM/IEEE Design Automation Conference (DAC). S. 688-694. 1985. [Br86] Bryant, R. E.: Graph-ba