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.