Die Dissertation liefert einen Beitrag zur Entwicklung von Compilern funktionaler Sprachen zur Erzeugung von Zielcode in einer höheren prozeduralen Programmiersprache. In der Dissertation werden mehrere Implementationstechniken funktionaler Sprachen analysiert, wobei für jede Technik ein Verfahren zur Realisierung eines auf der Übersetzung in eine prozedurale Sprache basierenden Compilers angegeben wird. Durch die verschiedenen Implementationsverfahren, die in der Arbeit analysiert bzw. definiert wurden, sind die beiden großen Klassen funktionaler Sprachen abgedeckt worden: strikte und nicht-strikte funktionale Programmiersprachen. Die Dissertation kann in drei größere Teile gegliedert werden, die sich mit folgenden Bereichen beschäftigen: Direkte übersetzungen funktionaler in prozedurale Programmiersprachen Übersetzung des Codes der abstrakten SECD-Maschine in eine prozedurale Sprache Erzeugung des Zielcodes in einer prozeduralen Programmiersprache bei Graph-Reduktion-basierten Implementationstechniken. Im ersten Teil, dem Schwerpunkt der Arbeit, wird eine über existierende Ansätze hinausgehende Transformation einer einfachen strikten funktionalen Programmiersprache (erweiterter Lambda-Kalkül) in den Code einer prozeduralen Zielsprache eingeführt und durch ein formales System von Transformationsregeln beschrieben. Die Transformation zeichnet sich durch Transparenz und Einfachheit (Erzeugung minimalen Codes) aus. Im zweiten und dritten Teil werden die aus der Literatur bekannten Implementationstechniken modifiziert bzw. optimiert, um Zielprogramme in einer höheren prozeduralen Programmiersprache erzeugen zu können. / This work contributes methods for the design and implementation of translation schemes for functional programming languages with procedural programming languages as a target. The dissertation analyzes different implementation techniques of functional languages. For each technique an approach is defined for the implementation of a compiler that translates the functional source language into a procedural target language. The analyzed techniques cover both classes of functional languages, strict and non-strict ones. The work is structured into three parts with the following topics: direct translation of functional programming languages into procedural programming languages; translation of the code of the SECD-abstract machine into a procedural language; emission of a target code in a procedural language by graph-reduction-based implementation techniques. In the first part, we give a formal definition for translating a simple functional language (syntacticly sugared lambda calculus) into the code of a procedural programming language. The defined transformation is simple and transparent. In the second and the third part, existing translation schemes are modified, i. e. two known implementation techniques are optimized to emit target code in an procedural language.

Wir berichten über eine experimentelle Studie zu lokalen Suchverfahren für das Pairing-Problem bei Fluggesellschaften unter Benutzung realer Testdatensätze mit bis zu 4600 Fl"ugen kurzer Reichweite. Unter einer Run-Cutting Formulierung vergleichen wir Verfahren wie Simulated Annealing, Modifikationen der Wasserspiegel-Algorithmen nach Dueck, eine elementare Implementation von Tabu Suche sowie einen GRASP Ansatz. Es zeigt sich, da"s die Wasserspiegel-Algorithmen vergleichbare Ergebnisse wie Simulated Annealing, und um etwa 40% bessere Ergebnisse als blo"se lokale Verbesserungsheuristiken liefern, w"ahrend Tabu Suche und GRASP hier ungeeignet erscheinen. Die Ergebnisse von Simulated Annealing und der Wasserspiegel-Algorithmen k"onnen sich auch mit den LP-Schranken f"ur die SET PARTITIONING Formulierung mit Packungsungleichungen und bis zu 3.9 Millionen Spalten messen. Eine Clustering-Parallelisierung des Simulated Annealings auf einem Parallelrechner GigaCluster PowerPlus weist eine sehr gute Beschleunigung auf. / For the airline pairing problem using a run-cutting formulation. Computational results are reported for some real-world short-haul testproblems with up to 4600 flights per month. In particular, we evaluate the relative performance of simulated annealing, modified versions of the waterlevel algorithms proposed by Dueck, an elementary tabu search, and a GRASP approach. We find that the waterlevel algorithms compare well with simulated annealing and both improve on mere improvement heuristics by about 40%. Tabu search and GRASP do not yield competitive results here. Simulated annealing and the waterlevel algorithms also compare favourably with LP-bounds for a SET PARTITIONING formulation with knapsack constraints containing up to 3.9 million columns. A clustering parallelization of simulated annealing on a GigaCluster PowerPlus parallel computer exhibits an excellent speed-up.

Im Rahmen dieser Arbeit wird das Modell der Case Retrieval Netze vorgestellt, das ein Speichermodell für die Phase des Retrievals beim fallbasierten Schliessen darstellt. Dieses Modell lehnt sich an Assoziativspeicher an, insbesondere wird das Retrieval als Rekonstruktion des Falles betrachtet anstatt als eine Suche im traditionellen Sinne. Zwei der wesentlichen Vorteile des Modells sind Effizienz und Flexibilität: Effizienz beschreibt dabei die Fähigkeit, mit grossen Fallbasen umzugehen und dennoch schnell ein Resultat des Retrievals liefern zu können. Im Rahmen dieser Arbeit wird dieser Aspekt formal untersucht, das Hauptaugenmerk ist aber eher pragmatisch motiviert insofern als der Retrieval-Prozess so schnell sein sollte, dass der Benutzer möglichst keine Wartezeiten in Kauf nehmen muss. Flexibilität betrifft andererseits die allgemeine Anwendbarkeit des Modells in Bezug auf veränderte Aufgabenstellungen, auf alternative Formen der Fallrepräsentation usw. Hierfür wird das Konzept der Informationsvervollständigung diskutiert, welches insbesondere für die Beschreibung von interaktiven Entscheidungsunterstützungssystemen geeignet ist. Traditionelle Problemlöseverfahren, wie etwa Klassifikation oder Diagnose, können als Spezialfälle von Informationsvervollständigung aufgefasst werden. Das formale Modell der Case Retrieval Netze wird im Detail erläutert und dessen Eigenschaften untersucht. Anschliessend werden einige möglich Erweiterungen beschrieben. Neben diesen theoretischen Aspekten bilden Anwendungen, die mit Hilfe des Case Retrieval Netz Modells erstellt wurden, einen weiteren Schwerpunkt. Diese lassen sich in zwei grosse Richtungen einordnen: intelligente Verkaufsunterstützung für Zwecke des E-Commerce sowie Wissensmanagement auf Basis textueller Dokumente, wobei für letzteres der Aspekt der Wiederbenutzung von Problemlösewissen essentiell ist. Für jedes dieser Gebiete wird eine Anwendung im Detail beschrieben, weitere dienen der Illustration und werden nur kurz erläutert. Zuvor wird allgemein beschrieben, welche Aspekte bei Entwurf und Implementierung eines Informationssystems zu beachten sind, welches das Modell der Case Retrieval Netze nutzt. / In this thesis, a specific memory structure is presented that has been developed for the retrieval task in Case-Based Reasoning systems, namely Case Retrieval Nets (CRNs). This model borrows from associative memories in that it suggests to interpret case retrieval as a process of re-constructing a stored case rather than searching for it in the traditional sense. Tow major advantages of this model are efficiency and flexibility: Efficiency, on the one hand, is concerned with the ability to handle large case bases and still deliver retrieval results reasonably fast. In this thesis, a formal investigation of efficiency is included but the main focus is set on a more pragmatic view in the sense that retrieval should, in the ideal case, be fast enough such that for the users of a related system no delay will be noticeable. Flexibility, on the other hand, is related to the general applicability of a case memory depending on the type of task to perform, the representation of cases etc. For this, the concept of information completion is discussed which allows to capture the interactive nature of problem solving methods in particular when they are applied within a decision support system environment. As discussed, information completion, thus, covers more specific problem solving types, such as classification and diagnosis. The formal model of CRNs is presented in detail and its properties are investigated. After that, some possible extensions are described. Besides these more theoretical aspects, a further focus is set on applications that have been developed on the basis of the CRN model. Roughly speaking, two areas of applications can be recognized: electronic commerce applications for which Case-Based Reasoning may provide intelligent sales support, and knowledge management based on textual documents where the reuse of problem solving knowledge plays a crucial role. For each of these areas, a single application is described in full detail and further case studies are listed for illustration purposes. Prior to the details of the applications, a more general framework is presented describing the general design and implementation of an information system that makes uses of the model of CRNs.

Die Bedeutung der in den relationalen Datenbankmanagementsystemen dargestellten Realwelt-Objekten wird weder explizit noch vollständig beschrieben. Demzufolge treffen häufig diese Systeme mit den Anfrageantworten nicht die Benutzerabsichten. Die vorliegende Dissertation präsentiert einen ontologie-basierten Ansatz für die semantische Anfrageverarbeitung. In diesem Ansatz sollen semantische Informationen aus einer gegebenen Ontologie abgeleitet und für die Umformulierung der Benutzeranfrage verwendet werden. Dies führt zu einer neuen Anfrage, die für den Benutzer sinnvollere Ergebnisse aus der Datenbank zurückliefern kann. Wir definieren und spezifizieren Einschränkungen und Abbildungen zwischen der Ontologie- und den Datenbank-Konzepten, um eine Ontologie mit einer Datenbank zu verknüpfen. Des Weiteren entwickeln wir eine Reihe von Algorithmen, die uns helfen, diese Abbildungen auf eine halbautomatische Weise zu finden. Au"serdem entwickeln wir eine Reihe von semantischen Regeln, die für die Umformulierung einer Anfrage benutzt werden. Die Haupteigenschaft einer Regel ist es, Begriffe einer Anfrage durch andere Begriffe zu ersetzen oder anzureichern, die von denselben ontologischen Konzepten dargestellt werden. Weiterhin benutzen wir die Theorie der Termersetzungssysteme, um den Transformationsprozess zu formalisieren und die wesentlichen Eigenschaften für das Anwenden der Regeln zu studieren. Aufbauend auf diesem Ansatz wurde ein Prototyp implementiert und wurde die Fähigkeit unseres Ansatzes durch einer real existierenden Anwendung ausgewertet. / Currently, database management systems solely rely on exact syntax of queries to retrieve data. As consequence query answers often do not meet the user''s intention. In this thesis we propose an ontology-based semantic query processing approach for database systems. We use ontologies to transform a user query into another query that may provide a more meaningful answer to the user. For this purpose, we define and specify different mappings that relate concepts of an ontology with those of an underlying database and develop a set of algorithms that allow us to find these mappings in a semi-automatic way. Moreover, we propose a set of semantic rules for transforming queries using terms derived from the ontology. We classify the rules and demonstrate their usefulness using practical examples. Furthermore, we make use of the theory of term rewriting systems to formalize the transformation process and to study the basic properties for applying these rules. Finally, we implement a prototype system using current technologies and evaluate its capability by using a real world application.

No description available.

No description available.

Dies ist eine aktualisierte Version von einer gesperrten Publikation: 10.18452/14561. Grund der Sperrung: Persönliche Daten vom Deckblatt entfernt / Inhalt der Dissertation ist die Untersuchung der Evolutionsprozesse zufälliger diskreter Strukturen. Solche Evolutionsprozesse lassen sich üblicherweise wie folgt beschreiben. Anfangs beginnt man mit einer sehr einfachen Struktur (z.B. dem Graphen auf n Ecken, der keine Kanten hat) und einer Menge von "Bausteinen'' (z.B. der Kantenmenge des vollständigen Graphen auf n Ecken). Mit zunehmender Zeit werden zufällig mehr und mehr Bausteine eingefügt. Die grundlegende Frage, mit der sich diese Dissertation beschäftigt, ist die folgende: Wie sieht zu einem gegebenen Zeitpunkt die durch den Prozess erzeugte Struktur mit hoher Wahrscheinlichkeit aus? Obwohl das Hauptthema der Dissertation die Evolution zufälliger diskreter Strukturen ist, lassen sich die erzielten Ergebnisse auch unter den folgenden Gesichtspunkten zusammenfassen: Zufällige Greedy-Algorithmen: Es wird ein zufälliger Greedy-Algorithmus untersucht, der für einen gegebenen Graphen H einen zufälligen H-freien Graphen erzeugt. Extremale Ergebnisse: Es wird die Existenz von Graphen mit hoher Taillenweite und hoher chromatischer Zahl bewiesen, wobei bestehende Schranken verbessert werden. Asymptotische Enumeration: Es werden präzise asymptotische Schranken für die Anzahl dreiecksfreier Graphen mit n Ecken und m Kanten bewiesen. "Probabilistische'' Versionen klassischer Sätze: Es wird eine probabilistische Version des Satzes von Sperner bewiesen. / In this thesis, we study the evolution of random discrete structures. Such evolution processes usually fit into the following general framework. Initially (say at time 0), we start with a very simple structure (e.g. a graph on n vertices with no edges) and a set of "building blocks'' (e.g. the set of edges of the complete graph on n vertices). As time increases, we randomly add more and more elements from our set of building blocks. The basic question which we shall investigate is the following: what are the likely properties of the random structure produced by the process at any given time? Although this thesis is concerned with the evolution of random discrete structures, the results obtained can also be summarized according to the following keywords: Random greedy algorithms: we study the output of a random greedy algorithm which, for a given graph H, produces a random H-free graph. Extremal results: improving on previous bounds, we prove the existence of graphs with high girth and high chromatic number. Asymptotic enumeration: we prove sharp asymptotic bounds on the number of triangle-free graphs with n vertices and m edges for a large range of m. Probabilistic versions of "classical'' theorems: we prove a probabilistic version of Sperner's theorem on finite sets.

Die Bestimmung der Ähnlichkeit von molekularen Strukturen und das Clustern solcher Strukturen gemäß Ähnlichkeit sind zwei zentrale Fragen im Wirkstoffdesign. Die Arbeit beschreibt im ersten Teil zwei neue Verfahren zum Vergleich von Molekülen auf 3-dimensionale Ähnlichkeit. Der erste Algorithmus benutzt als Eingabe nur die Koordinaten der Atome der zu vergleichenden Moleküle. Wir können zeigen, daß eine rein geometrische Zielfunktion in der Lage ist, Wirkungsähnlichkeit von Substanzen vorherzusagen, und daß der Algorithmus geeignet ist, Ähnlichkeiten zu finden, die mit bisherigen, einfacheren Methoden nicht gefunden werden konnten. Das zweite Verfahren nutzt zusätzlich noch die Bindungsstruktur der Eingabemoleküle. Es ist flexibel, d.h. alle Konformere der Moleküle werden simultan behandelt. Wir erhalten ein sehr schnelles Verfahren, das bei geeigneter Parametereinstellung auch beweisbar optimale Lösungen liefert. Für praktisch relevante Anwendungen erreichen wir erstmals Laufzeiten, die selbst das Durchsuchen großer Datenbanken ermöglichen. Im zweiten Teil beschreiben wir zwei Methoden, eine Menge von molekularen Strukturen so zu organisieren, daß die Suche nach geometrisch ähnlichen deutlich schneller durchgeführt werden kann als durch lineare Suche. Nach Analyse der Daten mit graphentheoretischen Methoden finden hierarchische Verfahren und repräsentantenbasierte Ansätze ihre Anwendung. Schließlich geben wir einen neuen Algorithmus zum Biclustern von Daten an, einem Problem, das bei der Analyse von Genexpressionsdaten eine wichtige Rolle spielt. Mit graphentheoretischen Methoden konstruieren wir zunächst deterministisch Obermengen von Lösungen, die danach heuristisch ausgedünnt werden. Wir können zeigen, daß dieser neue Ansatz bisherige, vergleichbare z.T. deutlich überbietet. Seine prinzipielle Einfachheit läßt anwendungsbezogene Modifikationen leicht zu. / Two important questions in drug design are the following: "How to compute the similarity of two molecules?" and "How to cluster molecules by similarity?" In the first part we describe two different approaches to compare molecules for 3D-similarity. The first algorithm just uses the 3D coordinates of the atoms as input. We show that this algorithm is able to detect similar activity or similar adverse reaction, even with a simple purely geometry based scoring function. Compared to previous simpler approaches more interesting hits are found. The connectivity structures of the molecular graphs are used by the second algorithm as additional input. This fully flexible approach -- conformers of the molecules are treated simultaneously -- may even find provably optimal solutions. Parameter settings for practically relevant instances allow running times that make it possible to even search large databases. The second part describes two methods to search a database of molecular structures. After analyzing the data with graph theoretical methods two algorithms for two different ranges of similarity are designed. Scanning the database for structures similar to a given query can be accelerated considerably. We use hierarchical methods and dominating set techniques. Finally we propose a new biclustering algorithm. Biclustering problems recently appeared mainly in the context of analysing gene expression data. Again graph theoretical methods are our main tools. In our model biclusters correspond to dense subgraphs of certain bipartite graphs. In a first phase the algorithm deterministically finds supersets of solution candidates. Thinning out these sets by heuristical methods leads to solutions. This new algorithm outperforms former comparable methods and its simple structure make it easy to customize it for practical applications.

Die mobile Robotik stellt ein sehr junges und komplexes Forschungsfelder unserer Zeit dar. Innerhalb der letzten Jahrzehnte wurde es Robotern möglich, sich innerhalb ihrer Umgebung zu bewegen, zu navigieren und mit ihrer Umwelt zu interagieren. Aufgrund der Tatsache, dass die Welt von Unsicherheit geprägt ist und ein Roboter immer nur partielle Information über sie erhalten kann, wurden probabilistische Navigationsverfahren entwickelt, mit denen sich Roboter lokalisieren und Objekte ihrer Umgebung modellieren können. Weiterhin wurden in letzter Zeit Verfahren untersucht, die die kooperative Exploration der Umgebung durch eine Gruppe von Robotern zum Ziel haben. In der vorliegenden Arbeit wird ein neuartiges Konzept, welches sich Perzeptrelationen für die kooperative Umweltmodellierung zu Nutze macht, vorgestellt und evaluiert. Einen zweiten Beitrag der Arbeit stellen constraintbasierte Lokalisierungstechniken dar, die es einem oder mehreren Robotern auf effiziente Art und Weise ermöglichen, sich zu lokalisieren und ihre Umwelt zu modellieren. / Mobile autonomous robotics is a very young and complex field of research. Only in recent decades have robots become able to explore, to move, navigate and to interact with their environment. Since the world is uncertain and since robots can only gain partial information about it, probabilistic navigation algorithms have become very popular whenever a robot has to localize itself or surrounding objects. Furthermore, cooperative exploration and localization approaches have become very relevant lately, as robots begin to act not just alone but in groups. Within this thesis a new approach using the concept of spatial percept-relations for cooperative environment modeling is presented and evaluated. As a second contribution, constraint based localization techniques will be introduced for having a robot or a group of robots efficiently localized and to model their environment.

Die vorliegende Arbeit besteht aus zwei Teilen. Der erste Teil der Arbeit befasst sich mit unteren Schranken für approximative Steinerbaumalgorithmen. Ein Steinerbaum ist ein kürzester Teilgraph, der eine gegebene Teilmenge der Knoten eines Graphen spannt. Das Berechnen eines Steinerbaumes ist ein klassisches NP-schweres Problem, und es existieren mehrere Approximationsalgorithmen, wobei bei den meisten Algorithmen die Approximationsgüte nur durch untere und obere Schranken eingegrenzt werden kann. Für einige dieser Algorithmen werden in dieser Arbeit Instanzen vorgestellt, welche die unteren Schranken verbessern. Für den Relativen Greedy Algorithmus wird außerdem ein Verfahren vorgestellt, mit dem die Güte des Algorithmus eingeschränkt auf die Graphenklasse mit k Terminalen auf einen beliebigen Faktor genau bestimmt werden kann. Der zweite Teil der Arbeit widmet sich vollständig bipartiten Subgraphen mit gleicher Partitionsgrößse, sogenannten balancierten Bicliquen. Seit langem ist bekannt, dass in dichten bipartiten Graphen balancierte Bicliquen mit Omega(log(n)) Knoten existieren, aber es ist unbekannt, ob und wie diese in polynomieller Zeit konstruiert werden können. Der zweite Teil liefert dazu einen Beitrag, indem ein polynomieller Algorithmus vorgestellt wird, der in hinreichend großen dichten bipartiten Graphen eine balancierte Biclique mit Omega(sqrt(log(n))) Knoten konstruiert. / This thesis consists of two parts. The first part is concerned with lower bounds for approximating Steiner trees. The Steiner tree problem is to find a shortest subgraph that spans a given set of vertices in a graph and is a classical NP-hard problem. Several approximation algorithms exist, but for most algorithms only lower and upper bounds for the approximation ratio are known. For some of these algorithms we present instances which improve the lower bounds. When the problem is restricted to the class of graphs with k terminals, we also present a method which can be used to determine the approximation ratio of the Relative Greedy Algorithm with arbitrary precision. The second part is about balanced bicliques, i.e. complete bipartite subgraphs with equal partition sizes. It has been known for a long time that every dense bipartite graph contains a balanced biclique of size Omega(log(n)), but whether and how such a biclique can be constructed in polynomial time is still unknown. Our contribution to this problem is a polynomial time algorithm which constructs a balanced biclique of size Omega(sqrt(log(n))) in sufficiently large and dense bipartite graphs.