Christmas Greetings

Merry Christmas to all Followers and Readers of this blog.

“It is good to be children sometimes, and never better than at Christmas, when its mighty Founder was a child Himself.” - Charles Dickens

Bachelor Computational Informatics - Changes

There will be some changes to the curriculum of the Bachelor CI which will take effect in the winter term 2011/12:

Semester 1:

•  Machine-based Programming (instead of Computer Architecture); this will be a laboratory.

Semester 3:

• Computer Engineering and Hardware Lab (instead of Introduction to Security  and Databases)

Semester 5/6:

• Introduction to Security and Databases (instead of Web Engineering and Compiler Construction).

The courses Computer Architecture, Web Engineering, and Compiler Construction will become Compulsory Electives.

Discrete Mathematics I - Lecture 9

Heute ging es abschließend um Zählkoeffizienten für Variationen inklusive ihrer Typisierung, Permutationen, geordnete und ungeordnete Zahlpartitionen sowie Mengenpartitionen.
Damit ist das Kapitel über Kombinatorik beendet.

Computational Biology - Lecture 9

Today, the basics of Groebner bases were presented including test of ideal membership, uniqueness of division, existence of Groebner bases, and Hilbert's basis theorem.

Introduction to Bioinformatics - Lecture 9

Today, we resumed with additive-tree methods for the construction of phylogenetic trees. As an example, the UPGMA method was provided and a genetic algorithm for searching the space of trees with a constant number of leaves.

Living as Machine?

This is the title of the new book of Klaus Mainzer (Mentis Verlag, Paderborn, 2010, 274 p.) that I got the other day. Mainzer's view is that of a unified theory of complex dynamical systems which is based on the assumption that all dynamic processes can be described by a computer program. This view embraces systems biology, artificial intelligence, and cyber physical systems. At the end, humans will be able to communicate with thinking machines and will merge into a single super-organism.

Discrete Mathematics I - Lecture 8

Die Themen der heutigen Vorlesung:

• Prinzip der Inklusion-Exklusion,
• Darstellung von Abbildungen durch Wörter,
• Kombinationen, Binomialkoeffizient,
• Repetitionen,
• Variationen.

Computational Biology - Lecture 8

Today, we will present basics of computational commutative algebra:

• polynomial rings in several unknowns,
• term orders (plex, grlex, grevlex),
• Dickson's Lemma,
• division algorithm.

Introduction to Bioinformatics - Lecture 8

Today, we will firstly consider the maximum likelihood method for the reconstruction of phylogenies. For this, we will introduce evolutionary models. Such a model is based on a rooted tree and a rate matrix which specifies the substitution matrices along the branches of the tree. Then we will introduce the likelihood of the tree and discuss the problem of optimizing the branch lengths.

Secondly, we will study distance based methods. The goal is to construct the most additive tree from a given set of evolutionary distances. We will use linear programming to tackle this problem. An example involving four species will be given.

Discrete Mathematics I - Lecture 7

In der heutigen Vorlesung wurden zuerst abzählbare und überabzählbare Mengen behandelt:

• Menge der ganzen Zahlen,
• Menge der rationalen Zahlen (erste Cantorsche Diagonalisierungsmethode),
• Menge der Algorithmen,
• Menge der reellen Zahlen (zweite Cantorsche Diagonalisierungsmethode),
• Potenzmenge der natürlichen Zahlen.

Die Kontinuumshypothese sowe Abstufungen im Unendlichen wurden diskutiert.

Anschließend ging es um elementare Zählprinzipien:

• Gleichheitsprinzip,
• Additionsprinzip,
• Prinzip der doppelten Abzählung.

Computational Biology - Lecture 7

Today, we will consider the expectation-maximization (EM)  algorithm which can be used to provide maximum-likelihood estimates of the parameters in a statistical model with hidden variables, like the hidden Markov model (HMM). As an example, the EM algorithm is going to be applied to the casino model.

Finally, an HMM for CpG islands in human genomes will be discussed.

Introduction to Bioinformatics - Lecture 7

Today, we will start with the basics on phylogenetics:

• Distance and character data, basic assumptions.
• Number of labeled binary trees with fixed number of leaves - rooted or non-rooted.
• Small parsimony methods: weighted (Sankoff) and unweighted (Fitch).

MentorIng Meeting

The next MentorIng meeting will be on Friday, December 17, from 12:15 to 1:15 in room SBS95-3032. There are actually some new developments concerning the course of studies in CI (computer architecture, technical informatics).
Punsch, orange juice, and cookies will be served.

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.

Discrete Mathematics I - Lecture 1

In der Vorlesung werden anfangs die Grundlagen der höheren Mathematik gelehrt. Ganz wichtig ist dabei das Kennenlernen der Sprache der modernen Mathematik, die auf Logik und Mengenlehre basiert.
In der ersten Vorlesung wurde im Wesentlichen die Aussagenlogik behandelt:

• Aussagenbegriff
• Verknüpfung von Aussagen, Junktoren.
• Aussagevariablen und Aussageformen.
• Semantische Ebene: Auswerten von Aussageformen durch Wahrheitswerte.
• Tautologien
• Syntaktische Ebene: Umformen von Aussagenformen mittels Rechengesetzen.
• One Minute Paper.

Mit dem Aufbau der Prädikatenlogik wurde am Ende der Stunde begonnen.

Computational Biology - Lecture 2

Today, the second lecture studied the pair hidden Markov model for sequence alignment. Then the following steps have been taken:

• The tropicalization of the marginal probabilties leads to the optimal alignment problem. 
• The marginal probabilities are decomposed and the associated tropicalization elucidates an algorithm for optimal sequence alignment. 
• In particular, if the scores for the edit strings are neglected, the algorithm corresponds to the original algorithm of Needleman and Wunsch.

Introduction to Bioinformatics - Lecture 2

This lecture has provided a short introduction to DNA, RNA, genes, genomes, and biosynthesis:

• Structure of DNA.
• Domains of life.
• Structure of genomes, prokaryotes and eukaryotes.
• Virsuses
• Structure of genes, prokaryotes and eukaryotes.
• Structure of RNA.
• Transcription.
• Promoter regions in E.coli and human.
• Exons, introns, and splicing.
• Genetic code.
• Transfer RNA (tRNA).
• Ribosomes.
• Translation.
• Central dogma of molecular biology.
• Life cycle of HIV.

Computational Biology - Lecture 1

Sequence alignment is a fundamental task in molecular biology. The primary objective of biological sequence alignment is to find positions in the sequences that are homologous. Homologous means that the symbols at those positions have been derived from the same position in a some anchestral sequence.

Today, the first lecture introduced three ways to represent squence alignments: two-row representations with inserted blanks, edit strings over the alphabet with H, D, and I, and paths in alignnment graphs. After this, scorings schemes were considered consisting of 33 parameters. Then the algebraic-statistical analogue was pictured that amounts to the pair hidden Markov model. Finally, the tropical algebra was defined and the mapping between the tropical algebra and the natural semiring of the non-negative real numbers, given by assigning x to -log x.

Introduction to Bioinformatics - Lecture 1

Proteins perform many function essential for life. The building blocks of the proteins are the 20 naturally occurring amino acids. In the first lecture, we have considered the structure of amino acids and proteins.
Here is the contents:

• Chemical structure of amino acids.
• Condensation reaction to establish linear chains of amino acids.
• Backbone structure of proteins.
• Peptide bond between neighboring residues in a linear chain of amino acids.
• Structure of the protein crambin from Crambe abyssinica.
• Side chains of amino acids.
• Geometry of proteins: bond lengths and angles, dihedral angles.
• Ramachandran plots and distance maps.
• Conformations - thermodynamic hypothesis of Anfinsen.
• Secondary structures: helices and sheets.
• Proteins in a watery compartment: hydrophobic core, globular form.
• Quaternary structures (deoxy human hemoglobin).
• Example: Penicillin amidase.

DNA Computing

During the last years, we have studied various DNA based models. These models generally encode information by DNA and manipulate information by enzymes. The emphasis has been on autonomous models (i.e., models that work without hand-crafting). The applications of autonomous DNA models lie in the analysis of  DNA in vitro and eventually in the logical control of cell behaviour in vivo.

Our main inventions have been an autonomous DNA model for finite-state machines, an automaton called computational genes able to logically control cell activities, the first autonomous solution of Adleman's first experiment, a bunch of new sticker-based algorithms, and a method that allows to implement sticker-based algorithms in silico onto dedicated hardware (FPGA).

 Literature:

• I. Martinez-Perez, W. Brandt, M. Wild, K.-H. Zimmermann: Bioinspired parallel algorithms for maximum clique problem on FPGA architectures. J. Sig. Proc. Syst., 1939-8115 (online), 2009.
• I. Martinez-Perez, Z. Ignatova, K.-H. Zimmermann: An autonomous DNA model for finite state automata. Int. J. Bioinform. Res. App., vol. 5, no. 1, 81-96, 2009.
• I. Martinez-Perez, Z. Ignatova, K.-H. Zimmermann: Exploiting the features of finite state automata for biomolecular computing. J Recent Patents DNA & Gene Sequences, vol. 3, no. 2, 130-138, 2009.
• I. Martinez-Perez, Z. Ignatova, K.-H. Zimmermann: DNA Computing Models. Springer, 300 pages, 2008.
• I. Martinez-Perez, Z. Ignatova, K.-H. Zimmermann: Computational genes. Wikipedia, 2008.
• I. Martinez-Perez: Biomolecular Computing Models for Graph Problems and Finite State Automata. PhD thesis, mbv Berlin, 2007.
• I. Martinez-Perez, Z. Ignatova, K.-H. Zimmermann: Computational genes: A tool for molecular diagnosis and therapy of aberrant mutational phenotype..BMC Bioinformatics, vol. 8, 365, 2007.
• I. Martinez-Perez, Z. Ignatova, K.-H. Zimmermann: An autonomous DNA model for finite state automata. Techn. Report, 06.1, TUHH, 2006
• I. Martinez-Perez, Z. Ignatova, K.-H. Zimmermann: Solving the maximum clique problem via DNA haiprin formation. Techn. Report, 06.3, TUHH, 2006.
• I. Martinez-Perez, Z. Ignatova, Z. Gong, K.-H. Zimmermann: Solving the Hamiltonian path problem via DNA hairpin formation. Int. J. Bioinform. Res. App., vol. 1, 389-398, 2006.
• I. Martinez-Perez, Z. Ignatova, K.-H. Zimmermann: An autonomous DNA model for stochastic finite state automata. Techn. Report, 06.2, TUHH, 2006.

A computational gene is an autonomous molecular automaton that is able to assemble an anti-drug or a wild-type gene if the mRNA of an aberrant gene has been detected. Computational genes have been successfully tested in vitro.

Patent:

• I. Martinez-Perez, Z. Ignatova, K.-H. Zimmermann: Rechengen/Computer Gene/Gene de Calcul, DE/EN/US, 2007-09. 

A careful design of DNA strands is crucial for several biological applications such as microarray techniques, Polymerase Chain Reaction (PCR), and DNA computing. For this, the important criterion under laboratory conditions is the hybridisation energy of two DNA strands. During the last decade, a thermodynamic model was developed that allows for the calculation of the DNA/DNA hybridisation energy and recently also the cross-hybridisation energy of structural motifs.

We have developed a new algorithm for the secondary structure prediction of DNA/DNA cross-hybridisation complexes called HYBGRAPH. The method is based on Gibbs free energy minimisation and the paradigm of dynamic programming.

Literature:

• S. Torgasin, K.-H. Zimmermann: Algorithm for thermodynamically based prediction of DNA/DNA crosshybridisation. Int. J. Bioinform. Res. App., vol. 6, no. 1, 82-97, 2010.

 DNA computing is an integral part of our teaching activities (rotative seminar in the summer term).

Und wie hoch ist Ihre Erdös-Zahl?

Der Ungar Paul Erdös (1913-1996) war einer der bedeutendsten Mathematiker des zwanzigsten Jahrhunderts. Er galt unter Mathematikern schon zu Lebzeiten als eine Legende. Paul Erdös wuchs in Budapest als Sohn jüdischer Eltern auf. Mit vier Jahren konnte er Freunden der Familie im Kopf ausrechnen, wie alt sie gemessen in Sekunden waren. Paul wurde zuhause unterrichtet, da seine beiden Schwestern früh starben und seine Mutter Angst hatte ihn durch eine ansteckende Krankheit zu verlieren. Schon mit 17 Jahren besuchte er die Universität und nach nur vier Jahren erlangte er den Doktortitel in Mathematik. Da der Antisemitismus immer mehr zunahm, ging er im gleichen Jahr nach England.

Erdös' Arbeitsgebiete waren Kombinatorik und Zahlentheorie. Erdös gilt als Begründer der Diskreten Mathematik, die heute grundlegend für die Informatik ist. Erdös war ein ruheloser Geist, der neben USA, England sowie Niederlande auch Israel bereiste und dort von Universität zu Universität zog, um mit Wissenschaftlern zusammenzuarbeiten. Der polnische Mathematiker Stanislaw Ulam, ein Mitarbeiter des Manhattan Projektes, beschrieb Erdös einmal wie folgt:

He had been a true child prodigy, publishing his first results at the age of eighteen in number theory and in combinatorial analysis. Being Jewish he had to leave Hungary, and as it turned out, this saved his live. In 1941 he was twenty-seven years old, homesick, unhappy, and constantly worried about the fate of his mother who remained in Hungary. ... Erdös is somewhat below medium height, an extremely nervous and agitated person. ... His eyes indicated he was always thinking about mathematics, a process interrupted only by his rather pessimistic statements on world affairs, politics, or human affairs in general, which he viewed darkly. ... His peculiarities are so numerous it is impossible to describe them all. ... Now over sixty, he has more than seven hundred papers to his credit.

Erdös veröffentlichte circa 1.500 Artikel, so viele wie kein anderer Mathematiker. Daraus entstand scherzhaft die Erdös-Zahl. Erdös selbst hat die Erdös-Zahl 0, alle Koautoren, 509 an der Zahl, mit denen Erdös publizierte, haben Erdös-Zahl 1. Autoren, die mit Koautoren von Erdös, aber nicht mit Erdös selber veröffentlicht haben, besitzen Erdös-Zahl 2, usw. Wissenschaftler, die auf diese Weise keine Verbindung zu Erdös herstellen können, haben Erdös-Zahl unendlich. Die Erdös-Zahl der meisten Wissenschaftler ist entweder unendlich oder sehr klein. Der Mittelwert der ungefähr 268.000 Personen mit endlicher Erdös-Zahl liegt bei 4,65.

An der TUHH gibt es drei Wissenschaftler mit Erös-Zahl drei (Gollmann, Rump und Zimmermann) sowie ca. zehn Wissenschaftler mit Erdös-Zahl vier, darunter unser verehrter Uni-Präsident, Prof. Kreuzer. Kollege Mackens fällt nicht diesen Kreis - Angewandte Mathematiker haben oft höhere Erdös-Zahlen.

Die American Mathematical Society (AMS) pflegt eine Webseite, mit deren Hilfe sich Erdös-Zahlen berechnen lassen. Die Erdös-Zahl ist für den einzelnen Mathematiker nicht von Belang. Sie liefert jedoch im Rahmen wissenschaftlicher Publikationen ein Beispiel für ein Bekanntheitsnetzwerk. Derartige soziale Netzwerke gewinnen speziell im Internet immer stärker an Bedeutung (z.B. facebook). Im Bereich der Schauspielerei gibt es eine analog definierte Zahl, die Bacon-Zahl, die kürzeste Distanz zu Kevin Bacon (geb. 1958).

Wer mehr über Erdös erfahren möchte, dem sei der Dokumentarfilm N Is a Number: A Portrait of Paul Erdős von G.P. Csicsery (1993) empfohlen.

Simulation of 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. We are studying 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 comrades in its visible zone given by a compound eye and in this way allows it to navigate in 3D space. An additional input parameter is used to represent the agent’s motivation to form a swarm. Simulations with different motiviation parameters exhibit remarkable agent formations that can be considered as biologically plausable. Several ways to improve the model are currently discussed.

Key Words: computational intelligence - swarm simulation - multi-agent system - neural network - compound eye.

Literature:

• W. Kramper: Simulation von Schwarmverhalten. PhD thesis, 124 p., mbv, Berlin, 2010.

Common work with Wolfgang Kramper and Ralf Wanker.

Bioinformatics Algorithms on Graphics Hardware

Alignment is one of the basic operations in molecular biology to compare sequences. The most widely used methods for multiple-sequence alignment include scalar-product based alignment of groups of sequences. 

We have shown that scalar-product based alignment algorithms can be significantly speeded up by general-purpose computing on a modern commonly available graphics card. This allows to develop high performance solutions for multiple-sequence alignment by utilizing the huge computational power of graphics cards.

Key Words  alignment - progressive alignment - graphics processor card - basic linear algebra subprograms - performance 

Literature

• C.S. Bassoy, M. Yang, S. Torgasin, K.-H. Zimmermann: Accelerating scalar-product based sequence alignment using graphics processor units. J. Sig. Proc. Syst., 1939-8115 (online), 2009.
• GPGPU.org

Groebner Bases for Linear Codes

Error-correcting codes are used to enable reliable delivery of digital data over unreliable communication channels. This typically involves to add extra bits to make the transmission of data more robust to disturbance present on the transmission channel. In particular, linear codes provide an extra structure that allows an efficient encoding of the data.

Recently, Fitzpatrick et al. have associated binomial ideals with binary linear codes. Groebner basis computations were used for decoding and to solve several problems related to graphs associated with the code.

More recently, we have emphasized that linear codes over prime fields can be described by binomial ideals each of which given as the sum of a toric ideal and a non-prime ideal. This description allows to study linear codes by methods from commutative algebra and algebraic geometry. The strength of this approach lies in the fact that the investigations can be made over any field and so particularly over an algebraically closed field of characteristic 0, which is the most comfortable situation in commutative algebra and algebraic geometry.

First, minimal generators of the binomial ideal of a code have been studied. The situation has turned out to be quite similar to the toric case. In the binary situation, the Graver bases, the universal Groebner bases, and the set of circuits of the binomial ideal are essentially equal.

Second, we have shown that the binomial ideal associated with a linear code has a very natural Groebner basis with respect to the lexicographic order requiring that any monomial containing one of the information symbols is larger than any monomial containing only parity check symbols. We have also illustrated that Groebner bases for linear codes provide a very compact representation of the encoding and decoding functions.

Third, we have studied the affine varieties of the binomial ideals associated with linear codes and minimal primary decompositions of these ideals.

Finally, we have described the binomial ideals of linear codes in terms of their syzygy modules and the corresponding finite free resolutions.

By the way, Groebner bases were first used in coding theory by Cooper providing a decoder for cyclic codes. Then the application of Groebner basis computations to the study of linear codes became an active field of study.

Originally, the method of Groebner bases was introduced by Buchberger for the algorithmic solution of some of the fundamental problems in commutative algebra. Today, Groebner bases provide a uniform approach to solving a wide range of problems expressed in terms of sets of multivariate polynomials such as the solvability and solving algebraic systems of equations, ideal and radial membership decision, effective computation in residue class rings modulo polynomial ideals, linear diophantine equations with polynomial coefficients, algebraic relations among polynomials, implicitization, and inverse polynomial mappings.

AMS Subject Classification: 13P10, 94B05

Key Words: commutative polynomial rings - binomial ideals - Groebner bases - linear codes - encoding and decoding.

Literature:

• M. Saleemi, K.-H. Zimmermann: Groebner bases for a class of ideals in commutative polynomial rings. Int. J. Pure Appl. Math., vol. 58, no. 1, 1-9, 2010.
• M. Saleemi, K.-H. Zimmermann: Linear codes as binomial ideals. Int. J. Pure Appl. Math., vol. 61, no. 2, 2010.
• M. Saleemi, K.-H. Zimmermann: Groebner bases for linear codes. Int. J. Pure Appl. Math., vol. 62, no. 4, 481-491, 2010.
• M. Saleemi, K.-H. Zimmermann: Syzygies and free resolutions of linear codes. Int. Electr. J. Pure Appl. Math., to appear
• M. Saleemi, K.-H. Zimmermann: Primary decompositions of linear codes. Int. Electr. J. Pure Appl. Math., submitted.

Permutation Parity Machines for Synchronization and Neural Cryptography

Synchronization of neural networks was studied in recent years as an alternative to cryptographic applications such as the realization of symmetric key exchange protocols. Our research provides a first view of the so-called permutation parity machine, an artificial neural network proposed as a binary variant of the well-known tree parity machine.

First, the dynamics of the synchronization process by mutual learning between permutation parity machines has been studied. By the way, the dynamics can be described by a first-order Markovian process. It has turned out that for neural synchronization, permutation parity machines form a viable alternative to tree parity machines.

Literature:

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

Second, the ability to synchronization between two permutation parity machines has been used to introduce a key-exchange protocol. This approach is quite similar to the case of tree parity machines. We have studied their performance against common attacks (simple, geometric, majority and genetic). It appears that the permutation parity machines (in opposition to tree parity machines) are rather immune against those attacks.

Literature:

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

This paper was awared recently:

We are pleased to inform you that your article, "Permutation parity machines for neural cryptography," published in Physical Review E 81, 066117 (2010), has been selected for the July 1, 2010 issue of Virtual Journal of Biological Physics Research.  The Virtual Journal, which is published by the American Physical Society and the American Institute of Physics in cooperation with numerous other societies and publishers, is an edited compilation of links to articles from participating publishers, covering a focused area of frontier research.  You can access the Virtual Journal at http://www.vjbio.org -- thank you for your contribution. ...

Sincerely,
Robert H. Austin, Editor

Currently, the objective is to apply permutation parity machines to light-weight security, especially RFIDs. At this point, we want to set up several student projects.

MentorIng

MentorIng is a programme of the Department of Electrical and Computer Engineering to bring students and professors together very early in the students' study. It was initiated by Ralf Möller and me for CI students at the beginning of the winter term 2009. But the Dean has wisely decided to extend MentorIng to all students of the Department.

This year, my MentorIng group is consisting of eleven CI students (six first-year and five second-year).

Rettet die Wandtafel

Der Tafelvortrag wird zunehmend durch die Powerpoint-Vorlesung (PPV) verdrängt. Dies gilt zusehends auch für Grundvorlesungen. Ist diese Entwicklung im Sinne der Studierenden?

Das Gerüst einer PPV besteht aus einem festen Satz von Präsentationsgraphiken. Somit ist das Erscheinungsbild der Vorlesung schon vor Beginn bis ins kleinste Detail vorgezeichnet. Eine solche Präsentation lässt sich beliebig oft und mit gleicher Qualität abspielen, während eine Tafelbild stets aufs Neue in Handarbeit entwickelt werden muss. Wie bei Musikaufführungen stehen die Einzigartigkeit und Unverwechselbarkeit der künstlerischen Handarbeit der Vorbestimmtheit und Abspielbarkeit einer Präsentationskonserve gegenüber.

Eine PPV umfasst weit mehr Informationen als ein Tafelvortrag. Nicht selten werden 45 Folien pro Vorlesung präsentiert. Für eine Folie stehen dann durchschnittlich weniger als 2 Minuten zur Verfügung. In einer solch kurzen Zeit ist es den Hörern schlichtweg unmöglich, die auf den Folien abgebildeten Sachverhalte umfassend zu verstehen. Das kreative Denken wird dadurch kaum nicht gefördert. Die Studierenden werden zu passiven Hörern degradiert, weil die Notwendigkeit, den Stoff zu filtern und zu einer eigenen Mitschrift zu verdichten, entfällt.

Das Gesagte macht deutlich, warum zahlreiche Studierende Einförmigkeit, Reizüberflutung und Verflachung als Nachteile der PPV kritisieren. In Anbetracht dieser Lage erscheint es angebracht, sich der guten alten Wandtafel zu erinnern. Es gibt mindestens vier Gründe, warum dieses Medium eine echte Alternative zur PPV darstellt:

• Die Vorlesung wird durch Verwendung der Wandtafel entschleunigt.
• Die Wandtafel zwingt den Dozenten dazu, sich auf das Wesentliche zu beschränken.
• Die Tafel erlaubt in stärkerem Maße eine Skizzierung von Einzelschritten eines Sachverhalts, etwa um verschiedene logische Ebenen eines wissenschaftlichen Konzepts oder eines technischen Systems erlebbar zu machen.
• Der höhere körperliche Einsatz des Dozenten an der Tafel entspricht der Vorstellung, dass Hochschullehrer in ihrem Selbstverständnis einem Künstler auf der Bühne näher stehen als Verbandsfunktionären am Rednerpult.

Frei nach Andre Thess (Ilmenau).

In diesem Sinne werde ich die Wandtafel weiterhin als Präsentationsmedium für meine Grundvorlesungen und anspruchsvollen Master-Vorlesungen verwenden.

Computational Biology (Algebraic Geometry & Statistics)

Computational biology is an interdisciplinary field that applies the techniques of applied mathematics, computer science, and statistics to address biological problems. The main focus lies in the development of computational and statistical data analysis methods and in developing mathematical modeling and computational simulation techniques. By these means it addresses scientific research topics with their theoretical and experimental questions without a laboratory.

The objective of the course is to present techniques from algebraic geometry and statistics so that participants will eventually be able to do research in bioinformatics. The course on bioinformatics is more concerned with practical issues and in some way complements this course.

The class will take place

• Thursday, 16:00-17:30, N - ES40, room 0008

The class will start by October 21.

The labs will be held by Mahwish Saleemi,

• Wednesday, 12:30-13:15, D - SBS95, room D1023.

The labs will start by October 27. In each week, we will assign homework in the form of two or three problems that will be discussed in the labs. The assignments will be available in the form of PDF files via Stud.IP.

The organizer of the course will be Svetlana Torgasin. If you have any questions, please direct them to her.

The course will largely follow the book

• L. Pachter, B. Sturmfels:  Algebraic Statistics for Computational Biology, Cambridge Univ. Press, 2005.

The manuscript that has grown out of the course can be downloaded via Stud.IP,

• K.-H. Zimmermann: Algebraic Statistics, TUHH, 2008.

Contents:

• Basic algebraic statistical models.
• Advanced algebraic statistical models for alignment of biomolecular sequences and phylogenetic data.
• Basic algebraic geometry.
• Invariants for algebraic statistical models.

The exam will be oral.

For recreation, I suggest to read about the life of Charles Darwin.

Introduction to Bioinformatics

Bioinformatics is a discipline that applies discrete mathematics, computer science, and statistics to the field of molecular biology. Over the past few decades, a tremendous amount of information related to molecular biology was produced due to rapid developments in genomic and other molecular research technologies and developments in information technologies.

The objective of bioinformatics is to increase the understanding of biological processes. For this, bioinformatics provides and develops databases, algorithms, computational and statistical techniques and theory to solve formal and practical problems arising from the management and analysis of biological data. In particular, bioinformatics develops and applies computationally intensive techniques (e.g., pattern recognition, machine learning, visualization, data mining) to achieve this goal. Major research areas include sequence alignment, gene finding, genome assembly, protein structure prediction, protein structure alignment, protein-protein interaction, and modeling of evolution.

The course will provide an introduction to the field of bioinformatics. Participants will not need specific previous knowledge.

The class will take place

• Thursday, 12:15-13:45, M - ES42, room 0526.

The class will start by October 21.

The labs will be held by Svetlana Torgasin,

• Tuesday, 13:45-14:30, E - SBS95, room E2009P3a,
• Friday, 11:00-11:45, E - SBS95, room E2054P4.

The labs will start by October 26. In each week, we will assign homework in the form of two or three problems that will be discussed in the labs. The assignments will be available in the form of PDF files via Stud.IP.

The organizer of the course will also be Svetlana Torgasin. If you have any questions, please direct them to her.

The course will partly follow the book

• K.-H. Zimmermann: Introduction to Protein Informatics, Kluwer, Boston, 2003.

The book is available as a set of slides (with courtesy of Kluwer) that can be downloaded (for personal use) via Stud.IP.

Contents:

• Introduction to molecular biology: amino acids, proteins, DNA, genes, genomes.
• Pairwise and multiple alignment of biomolecular sequences.
• Modeling of evolution by phylogenetic tree methods.
• Prediction of secondary protein structure.
• Prediction of tertiary protein structure.

The exam will be written by using computer facilities.

Finally, for recreational purposes, I'd like to recommend to read some books about the life of Charles Darwin, notably The Origin of Species and The Voyage of the Beagle.

Discrete Mathematics I (Discrete Algebraic Structures)

Discrete mathematics studies mathematical structures that are discrete rather than continuous. While the real numbers have the property of varying ''smoothly'', the objects studied in discrete mathematics do not vary in this way. Discrete means finite or countable (i.e., same cardinality as the set of natural numbers).

Research in discrete mathematics proliferated rather fast in the second half of the twentieth century due to the development of digital computers. Notations and concepts from discrete mathematics are particularly useful in studying and describing objects and problems in computer science. Conversely, discrete mathematics significantly benefitted from the invention of computers enabling the solution of difficult problems (e.g., four-coloring problem) or problem instances at a larger scale. Discrete Mathematics has a significant amount of applications in key areas like computer science, logistics, and life sciences.

The course will provide an introduction to discrete mathematics with an emphasis on discrete algebraic structures.

The class will take place

• Friday, 8:00 - 9:30 a.m., SBS 95, H0.16.

The class will start by October 29. By the way, the first-year students of Computational Informatics will have ''Orientierungswoche'' during this time. They will miss the first lecture on propositional calculus.

The labs will be held by Ralf Dittombee,

• Friday, 11:30 - 12:15 a.m., SBS 95, H0.07,

• Tuesday, 9:45 -  10:30 a.m., SBS 95, H0.09.

The labs will start by November 2. In each week, we will assign homework in the form of two or three problems that will be discussed in the labs. The assignments will be available in the form of PDF files via Stud.IP.

The organizer of the course will be Svetlana Torgasin. If you have any questions, please direct them to her.

The course will follow the book

• K.-H. Zimmermann: Diskrete Mathematik, BoD Verlag, Norderstedt, 2006.

There is an errata list and also a document with solutions of exercises. Both can be found at my homepage following the link on books. The TU library will eventually provide enough exemplars of the book.
Further books to be recommended:

• A. Beutelspacher, M. Zschiegner: Diskrete Mathematik für Einsteiger, Verlag Vieweg, 2007.

• N.L. Biggs: Discrete Mathematics, Oxford Univ. Press, 2002.

Contents:

• Introduction to higher mathematics: propositional calculus, first-order logic, sets, relations, equivalence and order relations, functions, natural numbers, countable sets.
• Combinatorics: combinations, permutations, counting principles.
• Algebraic structures: integers, rings, divisibility, residue class rings, polynomial rings, fields, finite fields.
• Applications: cryptography and coding theory.

The exam will be written. There will be a revision course directly before the exam.

Finally, I'd like to recommend some semi-mathematical books for recreation:

• D.R. Hofstadter: Gödel, Escher, Bach: ein Endloses Geflochtenes Band, Klett-Cotta, Stuttgart, 2008.

• S. Singh: Fermats letzter Satz, dtv Verlag, 2000. 

Use of Stud.IP

Stud.IP steht für "Studienbegleitender Internetsupport von Präsenzlehre". Die lizenzkostenfreie Open-Source-Software ist viel mehr als ein Lern-Management-System. Es ist die universelle Web 2.0 Internetplattform für Hochschulen, Unternehmen und Bildungseinrichtungen.

Stud.IP bietet Unterstützung für alle: Studierende im Studium, Lehrende bei der Durchführung von Lehrveranstaltungen und die Verwaltung beim Campusmanagement.

Stud.IP ist keine trockene Verwaltungssoftware. Stud.IP ist das Leben. 

After using this platform for several years I found that the downsides outweigh the advantages. Therefore we'll use Stud.IP only in two ways:

• Maintainance of lists of participants.
• Storage of homework assignments in the form of worksheets.

The students attending our courses need to live with it. By the way the two last sentences speak for themselves.

Blog Introduction

This blog will be about the work (research and teaching) of my group at TUHH.

Followers need to register with their names. Anonymous comments will be deleted.