uni-potsdam.de

Sie verwenden einen veralteten Browser mit Sicherheitsschwachstellen und können die Funktionen dieser Webseite nicht nutzen.

Hier erfahren Sie, wie einfach Sie Ihren Browser aktualisieren können.

  • Institut für Informatik und Computational Science

Vorträge von Prof. Dr. Victor Mitrana am 29.6. und am 6.7.2017

Im Rahmen des von PD Dr. Henning Bordihn veranstalteten Blockseminars "Computational Models Inspired by Nature" wird Prof. Dr. Victor Mitrana von der Universität Bukarest zwei Vorträge halten. Interessenten sind herzlich eingeladen.

1. Vortrag: Donnerstag, 29.06.2017, 18:15 Uhr, Campus Griebnitzsee, Haus 4, Raum 0.02
A New Operation Suggested by DNA Biochemistry: Hairpin Completion

We propose a new formal operation on words and languages suggested by DNA manipulation, called hairpin completion. By this operation, that is based on the Watson-Crick complementarity, annealing and PCR, one can generate a set of words, starting from a single word.This operation is considered here as an abstract operation on formal languages. We settle the closure properties under the non-iterated version of this operation of some classes in the Chomsky hierarchy as well as some complexity classes.

Then we consider a few algorithmic problems regarding the hairpin completion. The first problem we consider is the membership problem of the completion of a language. We propose an O(nf(n)) time recognition algorithm for the hairpin completion of a language recognizable in O(f(n)) time. We show that the n factor is not needed in the case of hairpin completion of regular and context-free languages.

The iterated version of hairpin completion is then discussed. We propose an O(n2f(n)) time recognition algorithm for the iterated hairpin completion of a language recognizable in O(f(n)) time. The n2 factor is not needed in the case of iterated hairpin completion of context-free languages, but it is reduced to n in the case of iterated hairpin completion of regular languages. We then define the hairpin completion distance between two words and present a cubic time algorithm for computing this distance. A linear time algorithm for deciding whether or not the hairpin completion distance with respect to a given word is connected is also discussed. Finally, we give a short list of open problems which appear attractive to us.

2. Vortrag: Donnerstag, 06.07.2017, 8:15 Uhr (!), Campus Griebnitzsee, Haus 4, Raum 0.02
Computing Translocation Distances

A basic problem in the area of combinatorial algorithms for genome evolution is to determine the minimum number of large scale evolutionary events (genome rearrangements) that transform a genome into another. We consider two translocation operations suggested by the genome rearrangements. In this talk chromosomes are viewed as being linear strings that exchange each other prefixes in the translocation process. We define a distance between a pair of multichromosomal genomes and examine the complexity of computing this distance in the case of uniform translocation.

Our work differs from previous approaches in several respects: the strings representing chromosomes may have multiple occurrences of the same symbol, they may have common symbols, the number of copies of all strings in the initial set is assumed arbitrarily large. One exact algorithm and one approximation algorithms, both of them based on greedy strategies, are discussed. We present an exact polynomial algorithm when the target set is a singleton while a 2-approximation algorithm is provided when considering arbitrary target sets. Some open problems are finally formulated.


Aus dem Institut für Informatik

Exzellente Forschung gestärkt – Uni Potsdam erhält zwei Sonderforschungsbereiche

Die Deutsche Forschungsgemeinschaft (DFG) hat heute zwei Sonderforschungsbereiche (SFB) bewilligt, die federführend von Wissenschaftlern der Universität Potsdam beantragt wurden. An der Schnittstelle zwischen Mathematik, Physik,...
26. Mai 2017
Die Deutsche Forschungsgemeinschaft (DFG) hat heute zwei Sonderforschungsbereiche (SFB) bewilligt, die federführend von Wissenschaftlern der Universität Potsdam beantragt wurden. An der Schnittstelle zwischen mehr ...

Universität Potsdam am Internet-Institut beteiligt – Berlin-Brandenburger Konsortium erhält Zuschlag

Die Universität Potsdam baut ihren Schwerpunkt IT und Digitalisierung weiter aus. Kurz nach der Gründung ihrer Digital Engineering Fakultät ist sie nun auch am Deutschen „Internet-Institut für die vernetzte Gesellschaft“...
23. Mai 2017
Die Universität Potsdam baut ihren Schwerpunkt IT und Digitalisierung weiter aus. Kurz nach der Gründung ihrer Digital Engineering Fakultät ist sie nun auch am Deutschen „Internet-Institut für die vernetzte mehr ...

IfI beteiligte sich mit dem Joint Lab am diesjährigen Potsdamer Tag der Wissenschaften

Das IfI war in diesem Jahr mit zwei Exponaten des Joint Labs und den Professuren "Zuverlässige und energieeffiziente Sensornetze“, „Design- und Testmethodik“ und „Architekturen eingebetteter Systeme für die...
22. Mai 2017
Das IfI war in diesem Jahr mit zwei Exponaten des Joint Labs und den Professuren "Zuverlässige und energieeffiziente Sensornetze“, „Design- und Testmethodik“ und „Architekturen eingebetteter Systeme für die mehr ...