Students Wanted

We look for students who want to prepare a thesis in one of the following areas:

• Computational Intelligence: simulation of swarm behavior,
• Light-Weight Cryptography: security protocol for RFID,
• General Purpose Graphics Card Processing (GPGPU): dynamic programming algorithms on graphics card processor (GPU),
• Algebraic Coding: Gröbner bases for linear codes.

In these areas, we have contributed by recent journal publications.

Cooperative thesis:

• Logistics: data management and optimization (Prof. Pawellek).

External thesis:

• Efficient reconfiguration of aircraft cabin by using intelligent components (Airbus).

Gödel, Escher, Bach

Gödel, Escher, Bach – ein Endloses Geflochtenes Band ist ein Buch von Douglas R. Hofstadter aus dem Jahre 1979. Der englische Originaltitel lautet: Gödel, Escher, Bach – An Eternal Golden Braid.

Hofstadter verbindet das mathematische Werk von Kurt Gödel (Unvollständigkeit der Arithmetik und Prädikatenlogik) mit den kunstvollen Illustrationen von M.C. Escher und der Musik von Johann Sebastian Bach. Diese Werke setzt er in Relation zur Informatik, selbstbezügliche Computerprogramme, und zur Molekularbiologie, Strukturen der DNA.

Hofstadter erhielt für sein Werk im Jahre 1980 den Pulitzer-Preis. Zudem stand das Buch fünf Monate lang auf Platz 1 der deutschen Sachbuch-Bestsellerliste.

Dieses Buch ist für Studierende der Informatik ein Muss.

Literatur:

• Douglas R. Hofstadter: Gödel, Escher, Bach - ein Endloses Geflochtenes Band. 18. Auflage. Klett-Cotta, 2008.

Discrete Mathematics I - Lecture 6

In der heutigen Vorlesung wurde zuerst das Kapitel über Permutationen (Signum, Eigenschaften des Signums) ad acta gelegt.

Anschließend wurden grundlegende Eigenschaften der natürlichen Zahlen behandelt:

• Peano-Axiomatik
• Addition und Multiplikation
• Rechengesetze
• Beweis durch vollständige Induktion
• Beispiele.

Computational Biology - Lecture 6

Today, we will consider the Hidden Markov Model (HMM). For this, we will first introduce the fully observed (toric) HMM and show how to establish corresponding maximum likelihood estimates.

Second, we will introduce the HMM. By decomposing the marginal probabilities in a sum of products, we obtain by tropicalization the Viterbi algorithm, which provides to each output sequence a state sequence that most likely produced the output sequence.

As an example, we will consider the computation of CpG islands in genomic sequences.

Introduction to Bioinformatics - Lecture 6

Today, we considered the following topics:

• profile-sequence alignment,
• profile-profile alignment,
• center-star algorithm.

RFID-Protokolle für den Schlüsselaustausch mittels Permutation Parity Machines

Techniken zur Identifizierung und Datenübertragung mittels RFID (Radio Frequency IDentification) finden zunehmend Verbreitung im Alltag. Für die Übertragung von privaten Daten ist die Sicherung der Kommunikation gegen unautorisiertes Mithören von großer Bedeutung. Selbst wenn die Reichweite der Verbindung zwischen Chipkarte und Lesegerät stark begrenzt ist, etwa 10 cm, ist ein passives Mithören auf größere Entfernungen durchaus möglich.

Die Kommunikationsstrecke kann durch symmetrische oder asymmetrische Kryptoverfahren gesichert werden. Allerdings ist die Leistungsfähigkeit heutiger Chipkarten oftmals nicht ausreichend, um sichere symmetrische Schlüsselaustausch-Verfahren , etwa Diffie-Hellman, zu implementieren, während asymmetrische Verfahren einer Infrastruktur für die Zertifizierung bedürfen.

In der Arbeit wird ein Verfahren für den Schlüsselaustausch vorgeschlagen, das auf neuronalen Netzen, den so genannten Permutation Parity Machines (PPMs), beruht. Die PPM wurde als Binärversion der Tree Parity Machine (TPM) in der Arbeitsgruppe entwickelt. Es wurde gezeigt, dass die Verschlüsselung mit gängigen Verfahren nicht zu brechen ist.

Die Arbeit ist konzeptueller Natur. Der nächste Schritt ist die Implementierung des Protokolls in Software/Hardware. Abschlussarbeiter und Studienarbeiter sind herzlich willkommen!

Literatur:

• T. Kuhr: Analyse von RFID-Protokollen zur Implementierung eines Schlüsselaustauschverfahrens mittels PPM, Studienarbeit, TUHH, 2010.

Weiterführende Literatur (PPM):

• O. Reyes, I. Kopitzke, K.-H. Zimmermann: Permutation parity machines for neural synchronization. J. Physics A: Math. Theor., vol. 42, 195002, 2009.

• O. Reyes, K.-H. Zimmermann: Permutation parity machines for neural cryptography. Phys. Rev. E, vol. 81, 066117, 2010.

Simulating Swarm Behaviour

The emergent collective intelligence of groups of simple agents known as swarm intelligence is a new exiting way of achieving a form of artificial intelligence. This paper studies a formal model for swarm intelligence inspired by biological swarms found in nature. Software agents are used to model the individuals of a swarm. Each agent is controlled by a neural network that processes position data from the others in its visible zone given by a compound eye and in this way navigates in 3D space. An additional input parameter is used to represent the agent’s motivation to form a swarm. Simulations with different motivation parameters exhibit remarkable agent formations that can be considered as biologically plausable. Several ways to improve the model are discussed.

W. Kramper, R. Wanker, K.-H. Zimmermann: Analysis of Swarm Behavior Using Compound Eye and Neural Network Control. J. Sig. Proc. Systems, submitted.

Graphics Card Processing: Accelerating Profile-Profile Alignment

Alignment is the fundamental operation in molecular biology for comparing biomolecular sequences. The most widely used method for aligning groups of alignments is based on the alignment of the profiles corresponding to the groups. We show that profile-profile alignment can be significantly speeded up by general purpose computing on a modern commodity graphics card. In this way, the huge computational power of graphics cards can be exploited to develop high performance solutions for multiple sequence alignment.

Keywords Alignment · Progressive alignment · Graphics processor card · Basic linear algebra subprograms · Performance.

M.K. Hanif, K.-H. Zimmermann: Accelerating Profile-Profile Alignment Using Graphics Processor Units. J. Sig. Proc. Systems, submitted.

Reed-Muller Codes Revisited

Recently, we studied linear codes as ideals in the group algebra over an elementary abelian p-group. These codes can be described in terms of Groebner bases which in turn provide encoding and decoding procedures. In particular, we investigated generalizations of primitive Reed-Muller codes and constructed corresponding Groebner bases. We also showed that the class of codes studied contains an interesting family of linear codes. These codes have a designed Hamming distance and turn out to be superior to the primitive Reed-Muller codes in the non-binary case.

AMS Subject Classification: 13P10, 94B05

Keywords: Commutative polynomial rings, ideals, Groebner bases, Reed-Muller codes, decoding.

M. Saleemi, K.-H. Zimmermann: From Ideals in Polynomial Rings to Linear Codes using Groebner Bases. Int. J. Pure Appl. Math., to appear.

Discrete Mathematics I - Lecture 5

In der heutigen Vorlesungsstunde wurden zuerst Ordnungsrelationen behandelt:

• Begriffe reflexiv, transitiv, antisymmetrisch,
• halbgeordnete Mengen,
• Hasse-Diagramme,
• Teilbarkeitsrelation.

Anschließend wurde mit dem Kapitel über Abbildungen begonnen:

• Begriffe linkstotal, rechtseindeutig,
• Abbildungen
• Gleichheit von Abbildungen,
• Komposition von Abbildungen,
• Begriffe injektiv, surjektiv
• bijektive Abbildungen,
• Invertierung bijektiver Abbildungen,
• Permutationen vom Grad n und ihre Darstellung (zweireihig, durch Zykeln).

Computational Biology - Lecture 5

Today, we introduced some basic algebraic-statistical models:

• DiaNA,
• linear model,
• toric Markov chain model, and
• Markov chain model.

Moreover, we considered maximum-likelihood estimation in these models.

Introduction to Bioinformatics - Lecture 5

Today, we focussed on the problem of multiple-sequence alignment:

• alignment scores,
• dynamic programming algorithm for multiple-sequence alignment,
• progressive alignment.

The Art of Proof

The other day, I got a copy of the book

M.Beck and R. Geoghegan: The Art of Proof, Undergraduate Texts in Mathematics, Springer, 2010.

The book is addressed to undergraduate students who have already taken basic courses in higher mathematics (i.e., linear algebra, calculus) but who are not yet prepared for upper-level mathematics.

The book basically covers number systems: natural numbers and integers (Part I: Discrete), and rational numbers and real numbers (Part II: Continuous). It emphasizes induction, recursion, and convergence. The book claims to teach how to organize a proof, how to use quantifiers, how to negate an assertion, how to avoid fallacies, etc.

I found that this book can be very helpful for first and second year students of Computer Science and Computer Engineering, too.

Discrete Mathematics I - Lecture 4

In der heutigen Vorlesung wurden anfangs die grundlegenden Eigenschaften der Komposition von Relationen (u.a. Assoziativität, Zusammenspiel mit Inversenbildung) diskutiert.
Anschließend wurden homogene Relationen eingeführt:

• Digraphen 
• Visualisierung von homogenen Relationen mithilfe von Diagrammen.
• Wege und Kreise in Digraphen.

Der letzte Teil der Vorlesungsstunde stand im Zeichen der Äquivalenzrelationen:

• Äquivalenzen (Begriffe: reflexiv, transitiv, symmetrisch)
• Äquivalenzklassen
• Quotientenmenge (Zusammenfassung der Äquivalenzklassen zu einem Mengensystem).
• Beispiele
• Quotientenmengen als Partitionen.

Computational Biology - Lecture 4

Today's class will continue with combinatory geometry covering the following topics:

• Polytope algebra.
• Tropical algebra as one-dimensional polytope algebra.
• Newton polytopes.

Now we will be able to solve the parametric pairwise-alignment problem:

• Polytope propagation of marginal probabilities.
• For the resulting polytope, construct the normal fan; in  particular, the normal cones of the vertices.
• These normal cones correspond one-to-one with the optimal pairwise alignments.

Introduction to Bioinformatics - Lecture 4

Today's lecture will carry on with the topic of pairwise sequence alignment:

• Local alignment.
• Heuristic methods: Fasta and Blast.
• Scoring models: Pam and Blosum.

Discrete Mathematics I - Lecture 3

Die Mengenlehre bildet zusammen mit der Prädikatenlogik die Grundlage für die moderne Sprache der Mathematik. In der heutigen Vorlesung wurde die Mengenlehre näher beleuchtet:

• Darstellung von Mengen: beschreibend oder aufzählend.
• Gleichheit von Mengen.
• Teilmengen
• Leere Menge
• Mengenoperationen und Rechengesetze.
• Potenzmenge
• Mengensysteme
• Antinomien

Aufbauend auf der Mengenlehre wurden auch Relationen behandelt:

• Geordnetes Paar, Paarmenge.
• n-Tupel, kartesisches Produkt.
• Relationen
• Allrelation, Nullrelation, Gleichheitsrelation, inverse Relation.
• Komposition von Relationen.

Computational Biology - Lecture 3

Today, we review some basics of combinatorial geometry:

• Convex sets and polytopes.
• Affine hulls and affine spaces.
• Positive hulls and cones.
• Hyperplanes and half-spaces.
• Faces, f-vectors.
• Normal cones and normal fans.

The aim of the next lecture will be to interpret the product-sum decomposition of the marginal probabilities in the pair hidden Markov model in terms of the polytope algebra. This will provide a way to determine all optimal pairwise sequence alignments.

Introduction to Bioinformatics - Lecture 3

Alignment is the standard technique in molecular biology for comparing sequences. Today, we gave an introduction to this field:

• Similarity between proteins.
• Change of genetic material.
• Homology
• Definition of pairwise alignment.
• Scoring model: match and mismatch scores.
• Alignment scores.
• Global alignment problem.
• Optimal algorithm for global alignment (Needleman-Wunsch).
• Optimal algorithm for global-local alignment.
• Dynamic programming (Bellman).

Discrete Mathematics I - Lecture 2

Die Aussagenlogik ist nicht reichhaltig genug, um darin komplexere mathematische Aussagen formulieren zu können (z.B. die Stetigkeit von Funktionen oder den Grenzwert von Reihen). Prädikatenlogik und Mengenlehre liefern heute die Grundlagen für den Aufbau der modernen Mathematik. In der heutigen Vorlesung wird die Prädikatenlogik kurz beleuchtet:

• Prädikate und Objekte
• Quantoren
• Vertauschung von Quantoren
• Verneinung von quantorisierten Aussagen
• Freie und gebundene Variablen.

Am Ende der Stunde wurde mit dem Aufbau der Mengenlehre begonnen.