Biolog:innen untersuchen häufig Pathways, Netzwerke von Interaktionen zwischen Proteinen und Genen mit einer spezifischen Funktion. Neue Erkenntnisse über Pathways werden in der Regel zunächst in Publikationen veröffentlicht und dann in strukturierter Form in Lehrbüchern, Datenbanken oder mathematischen Modellen weitergegeben. Deren Kuratierung kann jedoch aufgrund der hohen Anzahl von Publikationen sehr aufwendig sein. In dieser Arbeit untersuchen wir wie Text Mining Methoden die Kuratierung unterstützen können. Wir stellen PEDL vor, ein Machine-Learning-Modell zur Extraktion von Protein-Protein-Assoziationen (PPAs) aus biomedizinischen Texten. PEDL verwendet Distant Supervision und vortrainierte Sprachmodelle, um eine höhere Genauigkeit als vergleichbare Methoden zu erreichen. Eine Evaluation durch Expert:innen bestätigt die Nützlichkeit von PEDLs für Pathway-Kurator:innen. Außerdem stellen wir PEDL+ vor, ein Kommandozeilen-Tool, mit dem auch Nicht-Expert:innen PPAs effizient extrahieren können. Drei Kurator:innen bewerten 55,6 % bis 79,6 % der von PEDL+ gefundenen PPAs als nützlich für ihre Arbeit. Die große Anzahl von PPAs, die durch Text Mining identifiziert werden, kann für Forscher:innen überwältigend sein. Um hier Abhilfe zu schaffen, stellen wir PathComplete vor, ein Modell, das nützliche Erweiterungen eines Pathways vorschlägt. Es ist die erste Pathway-Extension-Methode, die auf überwachtem maschinellen Lernen basiert. Unsere Experimente zeigen, dass PathComplete wesentlich genauer ist als existierende Methoden. Schließlich schlagen wir eine Methode vor, um Pathways mit komplexen Ereignisstrukturen zu erweitern. Hier übertrifft unsere neue Methode zur konditionalen Graphenmodifikation die derzeit beste Methode um 13-24% Genauigkeit in drei Benchmarks. Insgesamt zeigen unsere Ergebnisse, dass Deep Learning basierte Informationsextraktion eine vielversprechende Grundlage für die Unterstützung von Pathway-Kurator:innen ist. / Biological knowledge often involves understanding the interactions between molecules, such as proteins and genes, that form functional networks called pathways. New knowledge about pathways is typically communicated through publications and later condensed into structured formats such as textbooks, pathway databases or mathematical models. However, curating updated pathway models can be labour-intensive due to the growing volume of publications. This thesis investigates text mining methods to support pathway curation. We present PEDL (Protein-Protein-Association Extraction with Deep Language Models), a machine learning model designed to extract protein-protein associations (PPAs) from biomedical text. PEDL uses distant supervision and pre-trained language models to achieve higher accuracy than the state of the art. An expert evaluation confirms its usefulness for pathway curators. We also present PEDL+, a command-line tool that allows non-expert users to efficiently extract PPAs. When applied to pathway curation tasks, 55.6% to 79.6% of PEDL+ extractions were found useful by curators. The large number of PPAs identified by text mining can be overwhelming for researchers. To help, we present PathComplete, a model that suggests potential extensions to a pathway. It is the first method based on supervised machine learning for this task, using transfer learning from pathway databases. Our evaluations show that PathComplete significantly outperforms existing methods. Finally, we generalise pathway extension from PPAs to more realistic complex events. Here, our novel method for conditional graph modification outperforms the current best by 13-24% accuracy on three benchmarks. We also present a new dataset for event-based pathway extension. Overall, our results show that deep learning-based information extraction is a promising basis for supporting pathway curators.

Immer wenn neue Anforderungen an ein System gestellt werden, müssen die Korrektheit und Konsistenz der Systemspezifikation überprüft werden, was in der Praxis in der Regel manuell erfolgt. Eine mögliche Option, um die Nachteile dieser manuellen Analyse zu überwinden, ist das sogenannte Contract-Based Design. Dieser Entwurfsansatz kann den Verifikationsprozess zur Überprüfung, ob die Anforderungen auf oberster Ebene konsistent verfeinert wurden, automatisieren. Die Verifikation kann somit iterativ durchgeführt werden, um die Korrektheit und Konsistenz des Systems angesichts jeglicher Änderung der Spezifikationen sicherzustellen. Allerdings ist es aufgrund der mangelnden Benutzerfreundlichkeit und der Schwierigkeiten bei der Interpretation von Verifizierungsergebnissen immer noch eine Herausforderung, formale Ansätze in der Industrie einzusetzen. Stellt beispielsweise der Model Checker bei der Verifikation eine Inkonsistenz fest, generiert er ein Gegenbeispiel (Counterexample) und weist gleichzeitig darauf hin, dass die gegebenen Eingabespezifikationen inkonsistent sind. Hier besteht die gewaltige Herausforderung darin, das generierte Gegenbeispiel zu verstehen, das oft sehr lang, kryptisch und komplex ist. Darüber hinaus liegt es in der Verantwortung der Ingenieurin bzw. des Ingenieurs, die inkonsistente Spezifikation in einer potenziell großen Menge von Spezifikationen zu identifizieren. Diese Arbeit schlägt einen Ansatz zur Erklärung von Gegenbeispielen (Counterexample Explanation Approach) vor, der die Verwendung von formalen Methoden vereinfacht und fördert, indem benutzerfreundliche Erklärungen der Verifikationsergebnisse der Ingenieurin bzw. dem Ingenieur präsentiert werden. Der Ansatz zur Erklärung von Gegenbeispielen wird mittels zweier Methoden evaluiert: (1) Evaluation anhand verschiedener Anwendungsbeispiele und (2) eine Benutzerstudie in Form eines One-Group Pretest-Posttest Experiments. / Whenever new requirements are introduced for a system, the correctness and consistency of the system specification must be verified, which is often done manually in industrial settings. One viable option to traverse disadvantages of this manual analysis is to employ the contract-based design, which can automate the verification process to determine whether the refinements of top-level requirements are consistent. Thus, verification can be performed iteratively to ensure the system’s correctness and consistency in the face of any change in specifications. Having said that, it is still challenging to deploy formal approaches in industries due to their lack of usability and their difficulties in interpreting verification results. For instance, if the model checker identifies inconsistency during the verification, it generates a counterexample while also indicating that the given input specifications are inconsistent. Here, the formidable challenge is to comprehend the generated counterexample, which is often lengthy, cryptic, and complex. Furthermore, it is the engineer’s responsibility to identify the inconsistent specification among a potentially huge set of specifications. This PhD thesis proposes a counterexample explanation approach for formal methods that simplifies and encourages their use by presenting user-friendly explanations of the verification results. The proposed counterexample explanation approach identifies and explains relevant information from the verification result in what seems like a natural language statement. The counterexample explanation approach extracts relevant information by identifying inconsistent specifications from among the set of specifications, as well as erroneous states and variables from the counterexample. The counterexample explanation approach is evaluated using two methods: (1) evaluation with different application examples, and (2) a user-study known as one-group pretest and posttest experiment.

In den letzten Jahren sind immer mehr erschwingliche Kamera-Sensoren mit einer zunehmenden Vielfalt optischer Abbildungsfunktionen verfügbar geworden. Low-Cost-Optiken können aufgrund höherer Toleranzen und unterschiedlicher optischer Materialien von der gewünschten Lochkamera Metrik abweichen. Weitwinkel- und Fischaugenobjektive, verzerrende katadioptrische Objektive (spiegelnd und refraktiv) und andere ungewöhnliche Objektive weichen von der Annahme des Modells einer Lochkamera mit einer Brennweite ab. Actionkameras können die gesamte Umgebung mit zwei Objektiven abbilden, diese entsprechen meist nicht mehr dem Lochkameramodell. Kameras werden auch für Messaufgaben hinter zusätzlichen optischen Elementen eingesetzt. Die vorliegende Arbeit erweitert die ersten Erkenntnisse im Bereich der differenzierbaren (glatten) Kameramodelle ohne Einschränkungen. Viele existierende Modelle sind auf bestimmte Objektivtypen spezialisiert. In dieser Arbeit werden mehrere solcher allgemeinen Modelle eingeführt, ohne dass eine global feste Brennweite und spezielle Anforderungen an die Symmetrie der Abbildung erforderlich sind. Eine Einführung alternativer Fehlermetriken im Objektraum bringt auch enorme Rechenvorteile, da eine Abbildungsrichtung analytisch berechnet und viele der Berechnungsergebnisse konstant gehalten werden können. Zur Initialisierung solcher Modelle wird in dieser Arbeit eine generische lineare Kamera vorgestellt. Das wesentliche Merkmal dabei ist eine künstliche Transformation in höhere Dimensionen, welche mit linearen Verfahren weiterverwendet werden. Sie modellieren bereits nichtlineare Verzerrungen und Asymmetrien. Eine Multikamera-Kalibrierungssoftware wird ebenfalls beschrieben und implementiert. Das Ergebnis der Arbeit ist ein theoretischer Rahmen für glatte Kameramodelle im Objektraum selbst – anstelle der Abbildung in den Bildraum – mit mehreren konkreten Modellvorschlägen, Implementierungen und dem angepassten und erweiterten Kalibrierungsprozess. / In recent years, more and more affordable camera sensors with an increasing variety of optical imaging features have become available. Low-cost optics may deviate from the desired pinhole metric due to higher tolerances and different optical materials. Wide-angle and fisheye lenses, distorting catadioptric lenses (specular and refractive) and other unusual lenses deviate from the single focal pinhole camera model assumption, which is sometimes intentional. Action cameras can map the entire environment using two lenses, these usually no longer correspond to the pinhole camera model. Cameras are also used for measuring tasks behind additional optical elements – with unforeseeable deviations in the line of sight. The present work expands the first findings in the field of differentiable (smooth) camera models without constraints. Many existing models specialise in certain types of lenses. In this work, several such general models are introduced without requiring fixed global focal length and symmetry requirements. An introduction of alternative error metrics in the object space also gives enormous computational advantages, since one imaging direction can be calculated analytically and many of the calculation results can be kept constant. For the generation of meaningful starting values of such models, this work introduces a generic linear camera. The essential feature of is an artificial transformation into higher dimensions. These transformed coordinates can then continue to be used with linear methods. They already model non-linear distortions and asymmetries. A multi-camera calibration software that efficiently implements these models is also described and implemented. The result of the work is a theoretical framework for smooth camera models in the object space itself - instead of the established mapping into the image space - with several concrete model proposals, implementations and the adapted and extended calibration process.

In dieser Arbeit werden P2P-Algorithmen in ressourcen-limitierten und irregulären Wireless-ad-hoc-Netzwerken (WAHN) betrachtet, die effizient, skalierbar und fehlertolerant in Situationen arbeiten sollen, in denen eine räumlich benachbarte Gruppe von Netzwerkknoten simultan ausfällt. Es wird ein fehlertolerantes Replikationsschema zur datenzentrischen Speicherung betrachtet, und eine selbstorganisierende, skalierbare Berechnung von Datenaggregaten zur Lösung des Konsensproblems. Existierende P2P-Algorithmen die Skalierbarkeit, Fehlertoleranz und Selbstorganisation in drahtgebundenen Netzen betrachten sind für die Klasse des WAHNs nicht geeignet weil sie Engpässe in WAHNs verursachen können und in Katastrophenmanagement-szenarien die Zuverlässigkeit der Daten nicht sicherstellen können. Die Verwendung von Informationen der geographischen Position von Knoten ist ein möglicher Weg, um die Effizienz und Skalierbarkeit von P2P-Anwendungen in drahtlosen Netzwerken zu verbessern. In dieser Arbeit wird ein neuer Ansatz vorgestellt, wie auf effiziente Weise 1) Gebiet des Netzwerks, das die geographische Ausbreitung seiner Knoten umfasst, und 2) Gruppenzugehörigkeit, wobei jeder Knoten zu genau einer Gruppe innerhalb eines einstellbaren Gebietes gehört, erzeugt werden kann. Dadurch können: existierenden, skalierbare P2P Datenspeicheralgorithmen für WAHNs genutzt werden, effiziente, fehlertolerante Replikation erstellt werden, die Effizienz von geographischen Routing und der Suche nach Replikaten verbessert werden sowie, Anwendungen auf einen bestimmten geographischen Bereich innerhalb des WAHN beschränkt werden (z.B. im Aggregationsprotokoll). Die entwickelten Protokolle sind tolerant gegenüber Nachrichtenverlust und verwenden ausschließlich lokale Broadcast-Nachrichten. Das Protokoll wurde mit Simulationen untersucht, die auf realistischen Netzwerktopologien mit Anteilen an sehr spärlichen und sehr dichten Knotenansammlungen basieren. / This dissertation addresses the challenge of reaching efficiency, scalability and fault-tolerance by P2P algorithms for resource-limited and irregular wireless ad-hoc networks (WAHNs) in disaster management (DM) scenarios where a spatially correlated group of nodes may crash simultaneously. In particular, we consider a fault-tolerant replication scheme for data-centric storage and a self-organized, scalable calculation of localized data aggregates for solving the consensus problem. Existing Peer-to-Peer algorithms that address issues of scalability, fault tolerance and self-organization in wired networks are inadequate for the addressed systems, they may cause bottlenecks in WAHNs and use replication that abstracts from geographical location of replicas and cannot therefore supply data survivability in DM scenarios in WAHNs. Incorporating information on geographical location of nodes is a recognized way to increase the efficiency and scalability of P2P applications in wireless networks. This dissertation proposes to efficiently construct new position information in a location-aware WAHN, where each node knows its own location and location of its direct neighbors. The new information are: network area, which expresses the geographical area covered by the network, and group membership, where each node belongs to exactly one group that is placed over the area of a maximum defined size. Together, they enable the use of the existing, scalable P2P data store in WAHNs (Geographical Hash Table), allow design of efficient fault-tolerant replication for the assumed fault model, increase efficiency of geographic routing and replica search, and allow to limit the geographical extent of activity of any distributed application, as we show using an example of data aggregation protocol. Proposed protocols tolerate message loss and use local broadcast only. They are evaluated by simulation over irregular topologies following the node placement of the existing, large WAHNs.

Einst als Hilfssatz für Szemerédis Theorem entwickelt, hat sich das Regularitätslemma in den vergangenen drei Jahrzehnten als eines der wichtigsten Werkzeuge der Graphentheorie etabliert. Im Wesentlichen hat das Lemma zum Inhalt, dass dichte Graphen durch eine konstante Anzahl quasizufälliger, bipartiter Graphen approximiert werden können, wodurch zwischen deterministischen und zufälligen Graphen eine Brücke geschlagen wird. Da letztere viel einfacher zu handhaben sind, stellt diese Verbindung oftmals eine wertvolle Zusatzinformation dar. Vom Regularitätslemma ausgehend gliedert sich die vorliegende Arbeit in zwei Teile. Mit Fragestellungen der Extremalen Hypergraphentheorie beschäftigt sich der erste Teil der Arbeit. Es wird zunächst eine Version des Regularitätslemmas Hypergraphen angewandt, um asymptotisch scharfe Schranken für das Auftreten von Hamiltonkreisen in uniformen Hypergraphen mit hohem Minimalgrad herzuleiten. Nachgewiesen werden des Weiteren asymptotisch scharfe Schranken für die Existenz von perfekten und nahezu perfekten Matchings in uniformen Hypergraphen mit hohem Minimalgrad. Im zweiten Teil der Arbeit wird ein neuer, Szemerédis ursprüngliches Konzept generalisierender Regularitätsbegriff eingeführt. Diesbezüglich wird ein Algorithmus vorgestellt, welcher zu einem gegebenen Graphen ohne zu dichte induzierte Subgraphen eine reguläre Partition in polynomieller Zeit berechnet. Als eine Anwendung dieses Resultats wird gezeigt, dass das Problem MAX-CUT für die oben genannte Graphenklasse in polynomieller Zeit bis auf einen multiplikativen Faktor von (1+o(1)) approximierbar ist. Der Untersuchung von Chung, Graham und Wilson zu quasizufälligen Graphen folgend wird ferner der sich aus dem neuen Regularitätskonzept ergebende Begriff der Quasizufälligkeit studiert und in Hinsicht darauf eine Charakterisierung mittels Eigenwertseparation der normalisierten Laplaceschen Matrix angegeben. / Once invented as an auxiliary lemma for Szemerédi''s Theorem the regularity lemma has become one of the most powerful tools in graph theory in the last three decades which has been widely applied in several fields of mathematics and theoretical computer science. Roughly speaking the lemma asserts that dense graphs can be approximated by a constant number of bipartite quasi-random graphs, thus, it narrows the gap between deterministic and random graphs. Since the latter are much easier to handle this information is often very useful. With the regularity lemma as the starting point two roads diverge in this thesis aiming at applications of the concept of regularity on the one hand and clarification of several aspects of this concept on the other. In the first part we deal with questions from extremal hypergraph theory and foremost we will use a generalised version of Szemerédi''s regularity lemma for uniform hypergraphs to prove asymptotically sharp bounds on the minimum degree which ensure the existence of Hamilton cycles in uniform hypergraphs. Moreover, we derive (asymptotically sharp) bounds on minimum degrees of uniform hypergraphs which guarantee the appearance of perfect and nearly perfect matchings. In the second part a novel notion of regularity will be introduced which generalises Szemerédi''s original concept. Concerning this new concept we provide a polynomial time algorithm which computes a regular partition for given graphs without too dense induced subgraphs. As an application we show that for the above mentioned class of graphs the problem MAX-CUT can be approximated within a multiplicative factor of (1+o(1)) in polynomial time. Furthermore, pursuing the line of research of Chung, Graham and Wilson on quasi-random graphs we study the notion of quasi-randomness resulting from the new notion of regularity and concerning this we provide a characterisation in terms of eigenvalue separation of the normalised Laplacian matrix.

Die folgende Arbeit befasst sich mit den Untersuchungen von Problemen der Optimierung von Ressourcen in Umgebungen mit unvorhersehbarem Verhalten, wo: (i) nicht alle Informationen verfügbar sind, und (ii) die Umgebung unbekannte zeitliche Veränderungen aufweist. Diese Dissertation ist folgendermaßen gegliedert: Teil I stellt das Investitionsmodell vor. Es wird sowohl eine analytische als auch eine numerische Analyse der Dynamik dieses Modells für feste Investitionsstrategien in verschiedenen zufälligen Umgebungen vorgestellt. In diesem Investitionsmodell hängt die Dynamik des Budgets des Agenten x(t) von der Zufälligkeit der exogenen Rendite r(t) ab, wofür verschiedene Annahmen diskutiert wurden. Die Heavy-tailed Verteilung des Budgets wurde numerisch untersucht und mit theoretischen Vorhersagen verglichen. In Teil II wurde ein Investitionsszenario mit stilisierten exogenen Renditen untersucht, das durch eine periodische Funktion mit verschiedenen Arten und Stärken von Rauschen charakterisiert ist. In diesem Szenario wurden unterschiedliche Strategien, Agenten-Verhalten und Agenten Fähigkeiten zur Vorhersage der zukünftigen r(t) untersucht. Hier wurden Null-intelligenz-Agenten, die über technischen Analysen verfügen, mit Agenten, die über genetischen Algorithmen verfügen, verglichen. Umfangreiche Ergebnisse von Computersimulationen wurden präsentiert, in denen nachgewiesen wurde, dass für exogene Renditen mit Periodizität: (i) das wagemutige das vorsichtige Verhalten überbietet, und (ii) die genetischen Algorithmen in der Lage sind, die optimalen Investitionsstrategien zu finden und deshalb die anderen Strategien überbieten. Obwohl der Schwerpunkt dieser Dissertation im Zusammenhang mit dem Gebiet der Informatik präsentiert wurde, können die hier vorgestellten Ergebnisse auch in Szenarien angewendet werden, in denen der Agent anderere Arten von Ressourcen steuern muss, wie z.B. Energie, Zeitverbrauch, erwartete Lebensdauer, etc. / The main goal of this PhD thesis is to investigate some of the problems related to optimization of resources in environments with unpredictable behavior where: (i) not all information is available and (ii) the environment presents unknown temporal changes. The investigations in this PhD thesis are divided in two parts: Part I presents the investment model and some analytical as well as numerical analysis of the dynamics of this model for fixed investment strategies in different random environments. In this investment model, the dynamics of the investor''s budget x(t) depend on the stochasticity of the exogenous return on investment r(t) for which different model assumptions are discussed. The fat-tail distribution of the budget is investigated numerically and compared with theoretical predictions. Part II investigates an investment scenario with stylized exogenous returns characterized by a periodic function with different types and levels of noise. In this scenario, different strategies, agent''s behaviors and agent''s capacities to predict the future r(t) are investigated. Here, ''zero-intelligent'' agents using technical analysis (such as moving least squares) are compared with agents using genetic algorithms to predict r(t). Results are presented for extensive computer simulations, which shows that for exogenous returns with periodicity: (i) the daring behavior outperforms the cautious behavior and (ii) the genetic algorithm is able to find the optimal investment strategy by itself, thus outperforming the other strategies considered. Finally, the investment model is extended to include the formation of common investment projects between agents. Although the main focus of this PhD thesis is more related to the area of computer science, the results presented here can be also applied to scenarios where the agent has to control other kinds of resources, such as energy, time consumption, expected life time, etc.

In dieser Arbeit schlagen wir die Verwendung von materialisierten Anfragen als Indexstruktur für RDF-Daten vor. Wir streben eine Reduktion der Bearbeitungszeit durch die Minimierung der Anzahl der Vergleiche zwischen Anfrage und RDF Datenmenge an. Darüberhinaus betonen wir die Rolle von Kostenmodellen und Indizes für die Auswahl eines efizienten Ausführungsplans in Abhängigkeit vom Workload. Wir geben einen Überblick über das Problem der Auswahl von materialisierten Anfragen in relationalen Datenbanken und diskutieren ihre Anwendung zur Optimierung der Anfrageverarbeitung. Wir stellen RDFMatView als Framework für SPARQL-Anfragen vor. RDFMatView benutzt materializierte Anfragen als Indizes und enthalt Algorithmen, um geeignete Indizes fur eine gegebene Anfrage zu finden und sie in Ausführungspläne zu integrieren. Die Auswahl eines effizienten Ausführungsplan ist das zweite Thema dieser Arbeit. Wir führen drei verschiedene Kostenmodelle für die Verarbeitung von SPARQL Anfragen ein. Ein detaillierter Vergleich der Kostmodelle zeigt, dass ein auf Index-- und Prädikat--Statistiken beruhendes Modell die genauesten Informationen liefert, um einen effizienten Ausführungsplan auszuwählen. Die Evaluation zeigt, dass unsere Methode die Anfragebearbeitungszeit im Vergleich zu unoptimierten SPARQL--Anfragen um mehrere Größenordnungen reduziert. Schließlich schlagen wir eine einfache, aber effektive Strategie für das Problem der Auswahl von materialisierten Anfragen über RDF-Daten vor. Ausgehend von einem bestimmten Workload werden algorithmisch diejenigen Indizes augewählt, die die Bearbeitungszeit des gesamten Workload minimieren sollen. Dann erstellen wir auf der Basis von Anfragemustern eine Menge von Index--Kandidaten und suchen in dieser Menge Zusammenhangskomponenten. Unsere Auswertung zeigt, dass unsere Methode zur Auswahl von Indizes im Vergleich zu anderen, die größten Einsparungen in der Anfragebearbeitungszeit liefert. / In this thesis, we propose to use materialized queries as a special index structure for RDF data. We strive to reduce the query processing time by minimizing the number of comparisons between the query and the RDF dataset. We also emphasize the role of cost models in the selection of execution plans as well as index sets for a given workload. We provide an overview of the materialized view selection problem in relational databases and discuss its application for optimization of query processing. We introduce RDFMatView, a framework for answering SPARQL queries using materialized views as indexes. We provide algorithms to discover those indexes that can be used to process a given query and we develop different strategies to integrate these views in query execution plans. The selection of an efficient execution plan states the topic of our second major contribution. We introduce three different cost models designed for SPARQL query processing with materialized views. A detailed comparison of these models reveals that a model based on index and predicate statistics provides the most accurate cost estimation. We show that selecting an execution plan using this cost model yields a reduction of processing time with several orders of magnitude compared to standard SPARQL query processing. Finally, we propose a simple yet effective strategy for the materialized view selection problem applied to RDF data. Based on a given workload of SPARQL queries we provide algorithms for selecting a set of indexes that minimizes the workload processing time. We create a candidate index by retrieving all connected components from query patterns. Our evaluation shows that using the set of suggested indexes usually achieves larger runtime savings than other index sets regarding the given workload.

In dieser Arbeit untersuchen wir Algorithmen für Scheduling-Probleme. Wir betrachten semi-online Makespan-Scheduling und generalisiertes Bin Covering. Im online Makespan- Scheduling-Problem sind m Maschinen und n Jobs gegeben, wobei letztere jeweils eine individuelle Bearbeitungszeit haben. Es wird zu jedem Zeitpunkt ein Job offengelegt und muss sofort und unwiderruflich einer Maschine zugewiesen werden, ohne Wissen über zukünftige Jobs. Die Last einer Maschine wird als die Summe der Bearbeitungszeiten der ihr zugewiesenen Jobs definiert. Das Ziel ist es, eine Zuweisung von Jobs zu Maschinen zu finden, sodass die höchste Last einer Maschine minimiert wird. Im semi-online Scheduling-Modell wird dieses strikte Szenario relaxiert. Wir untersuchen drei verschied- ene Modelle. Im ersten ist uns die kumulierte Bearbeitungszeit der Jobs vor Ankunft der einzelnen Jobs bekannt. Im zweiten Modell dürfen wir bis zu einem gewissen Grade bereits zugewiesene Jobs anderen Maschinen neu zuordnen.Im dritten semi-online Scheduling-Modell darf ein Algorithmus mehrere Lösungen parallel konstruieren, von denen die beste ausgegeben wird. Beim generalisierten Bin Covering sind uns m Bintypen und n Objekte gegeben. Ein Bintyp Mj hat einen Bedarf dj und einen Profit rj. Jedes Objekt Jt hat eine Größe pt. Ein Bin vom Typ Mj heißt abgedeckt, wenn die Summe der Größen der ihm zugewiesenen Objekte mindestens dj ist. Wenn ein Bin vom Typ Mj abgedeckt ist, erzielen wir einen Profit von rj. Ziel ist es, die Objekte Bins zuzuweisen, sodass der erzielte Gesamtprofit maximiert wird. Wir untersuchen zwei Modelle, die sich in der Verfügbarkeit von Bintypen unterscheiden. Im Unit-Supply-Modell steht uns von jedem Bintyp genau ein Bin zur Verfügung. Im Gegensatz dazu stehen uns im Infinite-Supply-Modell von jedem Bintyp beliebig viele Bins zur Verfügung. Das Unit-Supply-Modell ist daher eine Verallgemeinerung des Infinite-Supply-Modells. Für alle Modelle zeigen wir beinahe scharfe obere und untere Schranken. / In this thesis we study algorithms for scheduling problems. We investigate semi-online minimum makespan scheduling and generalized bin covering. In online minimum makespan scheduling we are given a set of m machines and n jobs, where each job Jt is specified by a processing time. The jobs arrive one by one and we have to assign them to the machines without any knowledge about future incoming jobs. The load of a machine is defined to be total processing time of the assigned jobs. The goal is to place the jobs on the machines such that the maximum load of a machine is minimized. In semi-online minimum makespan scheduling this strict setting is softened. We investigate three different models. In the first setting an algorithm is given an advice on the total processing time of the jobs. In the second setting we may reassign jobs upto a limited amount. The third semi-online setting we study is minimum makespan scheduling with parallel schedules. In this problem an algorithm may maintain several schedules, the best of which is output after the arrival of the entire job sequence. In generalized bin covering we are given m bin types and n items. Each bin type Mj is specified by a demand dj and a revenue rj. Each item Jt has a size pj. A bin of type Mj is said to be covered if the total size of the assigned items is at least the demand dj. Then the revenue rj is earned. The goal is to find an assignment of items to bins maximizing the total obtained revenue. We study two models of bin supply. In the unit supply model there is only one bin of each type available. By contrast in the infinite supply model each bin type is available arbitrarily often, and hence the former is a generalization of the latter. We provide nearly tight upper and lower bounds for all models.

Petrinetze werden in vielen Bereichen als Modellierungstechnik verwendet. Die verschiedenen Einsatzgebiete und Modellierungsziele erfordern dabei unterschiedliche Typen von Petrinetzen. Einen Petrinetz-Typ kennzeichnen -- neben den üblichen Stellen, Transitionen und Kanten -- eine Menge zusätzlicher, spezifischer Elemente, sowie eine spezifische Schaltregel. In der Literatur findet man zahlreiche verschiedene Petrinetz-Typen. Diese Vielfalt an Petrinetz-Typen lässt sich nicht ohne weiteres überblicken. Deshalb fehlt es auch nicht an Versuchen, allgemeine Petrinetz-Typen oder Klassifikationen -- auch einzelner Aspekte -- zu etablieren. Allerdings erfassen die bisherigen Ansätze nur einen kleinen Teil aller Petrinetz-Typen. Unser semantisch orientierter Klassifizierungsansatz des Petrinetz-Hyperwürfels umfasst deutlich mehr Petrinetz-Typen und erhebt den Anspruch, universell zu sein. Der Petrinetz-Hyperwürfel hat einen syntaktisch orientierten Klassifizierungsansatz als Grundlage. Dieser Ansatz führt einerseits zum Vorschlag der Petri Net Markup Language. Damit können Petrinetze aller Typen einheitlich beschrieben werden. Andererseits führt derselbe Ansatz zu einer Basis für Petrinetz-Werkzeuge, in der die einzelnen Teile eines Petrinetz-Typs unabhängig voneinander implementiert werden. Der Petrinetz-Kern ist eine derartige Basis mit dessen Hilfe Petrinetz-Werkzeuge gebaut werden. Er implementiert Konzepte, die allen Petrinetzen gemein sind, unabhängig von konkreten Petrinetz-Typen. Gemeinsam mit dem Petrinetz-Hyperwürfel bildet der Petrinetz-Kern ein weiteres Basiswerkzeug für einen parametrisierten Petrinetz-Typ mit einer parametrisierten Schaltregel. Die Petri Net Markup Language und der Petrinetz-Kern sind die wesentlichen Beiträge der vorliegenden Arbeit. Gemeinsam bilden sie ein mächtiges Grundgerüst für Petrinetz-Werkzeuge beliebiger Petrinetz-Typen. / Petri nets are widely used for modelling systems. The different areas and goals require different types of Petri nets. Each Petri net contains beside places, transitions, and arcs several further specific elements. Furthermore, a Petri net type defines a specific firing rule. There are many different Petri net types. It is not easy to have a general view on this bulk of Petri net types. Thus, there are attempts to establish general Petri net types or classifications of Petri net types (even of particular aspects). But, current approaches include only a few of all Petri net types. Our approach is a classification by semantics of Petri nets. We call this classification Petri Net Hypercube. It is meant to be universal for all Petri net types. A syntactical classification approach is the base of the Petri Net Hypercube. This approach leads on the one hand to the proposal of the Petri Net Markup Language. This language describes Petri nets of all types. On the other hand, the same approach leads to a base of Petri net tools. The parts of a Petri net type are implemented in this base independently of each other. The Petri Net Kernel is such a base for building Petri net tools. It implements those concepts which are general concepts of each Petri net. The Petri Net Kernel forms together with the Petri Net Hypercube a further basic Petri net tool for a parameterized Petri net type with a parameterized firing rule. The Petri Net Markup Language and the Petri Net Kernel are the main contributions of this thesis. Together, they are a powerful base for Petri net tools of each Petri net type.

Seit Jahrhunderten wird menschliches Wissen in Form von natürlicher Sprache ausgetauscht und in Dokumenten schriftlich aufgezeichnet. In den letzten Jahren konnte man auf dem Gebiet der Lebenswissenschaften eine exponentielle Zunahme wissenschaftlicher Publikationen beobachten. Diese Dissertation untersucht die automatische Extraktion von Beziehungen zwischen Eigennamen. Innerhalb dieses Gebietes beschäftigt sich die Arbeit mit der Steigerung der Robustheit für die Relationsextraktion. Zunächst wird der Einsatz von Ensemble-Methoden anhand von Daten aus der "Drug-drug-interaction challenge 2013" evaluiert. Ensemble-Methoden erhöhen die Robustheit durch Aggregation unterschiedlicher Klassifikationssysteme zu einem Modell. Weiterhin wird in dieser Arbeit das Problem der Relationsextraktion auf Dokumenten mit unbekannten Texteigenschaften beschrieben. Es wird gezeigt, dass die Verwendung des halb-überwachten Lernverfahrens self training in solchen Fällen eine höhere Robustheit erzielt als die Nutzung eines Klassifikators, der lediglich auf einem manuell annotierten Korpus trainiert wurde. Zur Ermittlung der Robustheit wird das Verfahren des cross-learnings verwendet. Zuletzt wird die Verwendung von distant-supervision untersucht. Korpora, welche mit der distant-supervision-Methode erzeugt wurden, weisen ein inhärentes Rauschen auf und profitieren daher von robusten Relationsextraktionsverfahren. Es werden zwei verschiedene Methoden untersucht, die auf solchen Korpora trainiert werden. Beide Ansätze zeigen eine vergleichbare Leistung wie vollständig überwachte Klassifikatoren, welche mit dem cross-learning-Verfahren evaluiert wurden. Um die Nutzung von Ergebnissen der Informationsextraktion zu erleichtern, wurde die semantische Suchmaschine GeneView entwickelt. Anforderungen an die Rechenkapazität beim Erstellen von GeneView werden diskutiert und Anwendungen auf den von verschiedenen Text-Mining-Komponenten extrahierten Daten präsentiert. / For several centuries, a great wealth of human knowledge has been communicated by natural language, often recorded in written documents. In the life sciences, an exponential increase of scientific articles has been observed, hindering the effective and fast reconciliation of previous finding into current research projects. This thesis studies the automatic extraction of relationships between named entities. Within this topic, it focuses on increasing robustness for relationship extraction. First, we evaluate the use of ensemble methods to improve performance using data provided by the drug-drug-interaction challenge 2013. Ensemble methods aggregate several classifiers into one model, increasing robustness by reducing the risk of choosing an inappropriate single classifier. Second, this work discusses the problem of applying relationship extraction to documents with unknown text characteristics. Robustness of a text mining component is assessed by cross-learning, where a model is evaluated on a corpus different from the training corpus. We apply self-training, a semi-supervised learning technique, in order to increase cross-learning performance and show that it is more robust in comparison to a classifier trained on manually annotated text only. Third, we investigate the use of distant supervision to overcome the need of manually annotated training instances. Corpora derived by distant supervision are inherently noisy, thus benefiting from robust relationship extraction methods. We compare two different methods and show that both approaches achieve similar performance as fully supervised classifiers, evaluated in the cross-learning scenario. To facilitate the usage of information extraction results, including those developed within this thesis, we develop the semantic search engine GeneView. We discuss computational requirements to build this resource and present some applications utilizing the data extracted by different text-mining components.