Kaiserslautern - Fachbereich Informatik
Refine
Document Type
- Bachelor Thesis (4) (remove)
Language
- English (4)
Has Fulltext
- yes (4)
Keywords
- Earley-Parser (1)
- RNA interaction (1)
- architecture (1)
- buildroot (1)
- discosat (1)
- multiple context free grammar (1)
- sdr (1)
- semiring parsing (1)
- sniffing (1)
- stochastic context free grammar (1)
Faculty / Organisational entity
It has been observed that for understanding the biological function of certain RNA molecules, one has to study joint secondary structures of interacting pairs of RNA. In this thesis, a new approach for predicting the joint structure is proposed and implemented. For this, we introduce the class of m-dimensional context-free grammars --- an extension of stochastic context-free grammars to multiple dimensions --- and present an Earley-style semiring parser for this class. Additionally, we develop and thoroughly discuss an implementation variant of Earley parsers tailored to efficiently handle dense grammars, which embraces the grammars used for structure prediction. A currently proposed partitioning scheme for joint secondary structures is transferred into a two-dimensional context-free grammar, which in turn is used as a stochastic model for RNA-RNA interaction. This model is trained on actual data and then used for predicting most likely joint structures for given RNA molecules. While this technique has been widely used for secondary structure prediction of single molecules, RNA-RNA interaction was hardly approached this way in the past. Although our parser has O(n^3 m^3) time complexity and O(n^2 m^2) space complexity for two RNA molecules of sizes n and m, it remains practically applicable for typical sizes if enough memory is available. Experiments show that our parser is much more efficient for this application than classical Earley parsers. Moreover the predictions of joint structures are comparable in quality to current energy minimization approaches.
Industrial manufacturing companies have different IT control functions that can be represented with a so-called hierarchical automation pyramid. While these conventional software systems especially support the mass production with consistent demand, the future project “Industry 4.0” focuses on customer-oriented and adaptable production processes. In order to move from conventional production systems to a factory of the future, the control levels must be redistributed. With the help of cyber-physical production systems, an interoperable architecture must be, implemented which removes the hierarchical connection of the former control levels. The accompanied digitalisation of industrial companies makes the transition to modular production possible. At the same time, the requirements for production planning and control are increasing, which can be solved with approaches such as multi-agent systems (MASs). These software solutions are autonomous and intelligent objects with a distinct collaborative ability. There are different modelling methods, communication and interaction structures, as well as different development frameworks for these new systems. Since multi-agent systems have not yet been established as an industrial standard due to their high complexity, they are usually only tested in simulations. In this bachelor thesis, a detailed literature review on the topic of MASs in the field of production planning and control is presented. In addition, selected multi-agent approaches are evaluated and compared using specific classification criteria. In addition, the applicability of using these systems in digital and modular production is assessed.
With the ever-increasing amount of satellite-backed communication, constellations covering the entire world, and the rise of Software Defined Radios (SDRs), satellite signals have already become prime targets for scientific research all over the globe. However, due to logistical challenges like capture time/location and peripheral/system management for the sensors and the wide variety of protocols/encoding schemes used, no one-fits-all sniffing solution exists for capturing their wide variety of signals. Therefore, this thesis aims to analyze, design, and implement a system that makes it possible to study LEO (Low Earth Orbit) L-Band satellite signals with readily available Single Board Computers (SBCs) in a widely distributed, location, and time-aware way. The key design factors were useability, maintainability, adaptability, and security in a centrally managed client-server architecture. The research presented yielded a Satellite probe Operating System called SATOS, which aims to implement on-sensor data decoding driven by GNU Radio and secure Over The Air (OTA) updates inside the Buildroot build environment. Its intended use case is the future deployment of DISCOSAT on a university working group scale.
In 2003, a dictionary data structure called jumplist has been introduced by Brönnimann, Cazals and Durand. It is based on a circularly closed (singly) linked list, but additional jump-pointers are added to provide shortcuts to parts further ahead in the list.
The original jump-and-walk data structure by Brönnimann, Cazals and Durand only introduces one jump-pointer per node. In this thesis, I add one more-jump pointer to each node and present algorithms for generation, insertion and search for the resulting data structure.
Furthermore, I try to evaluate the effects on the expected search costs and the complexity of the generation and insertion.
It turns out that the two-jump-pointer variant of the jumplist has a slightly better prefactor (1.2 vs. 2) in the leading term of the expected internal path length than the original version and despite the more complex structure of the two-jump-pointer variant compared to the regular jumplist, the complexity of generation and insertion remains linearithmic.