Foundations of informatics - a bridging course

Corresponding entry in b-it IPEC, Aachen Campus, Bonn Computer Science, Bonn Mathematics, Bonn University.

Responsible

Prof. Dr. Joachim von zur Gathen
Prof. Dr. Berthold Vöcking

Lecture

Michael Nüsken
Laila El Aimani
Thomas Noll
Walter Unger

Time & Place

14 - 24 October 2008, b-it bitmax, and
30 March - 9? April 2009, (probably) b-it ??.

Schedule: Mon-Fri 9⁰⁰ - 12³⁰ and 14⁰⁰ - 16⁰⁰, each block includes 30 minutes break. (If a course week advances fast, Friday afternoon may be free.)

Exam

Exam 1: Thursday, 30 April 2009, in the time between 16⁰⁰ and 19⁰⁰, b-it Rheinsaal.
Post-exam 1: Tuesday, 26 May 2009, in the time 16⁰⁰-17⁰⁰, b-it 1.25.
Exam 2: Wednesday, 24 June 2009, in the time between 15³⁰ and 18³⁰, b-it Rheinsaal.
Post-exam 2: Just pass by...

There will be no further exam option till next year. At the post-exam meetings you can have a look at your corrected exam.

Credits

For some MI-students this course is obligatory, for the others it's optional. There are no credits for this course.
There will be a written exam after the end of the complete course.

Week 1 - Mathematical tools

This week will deal essentially with three subjects:

Linear Algebra (Gaussian elimination, Gauß-Jordan-algorithm, expansion, dim ker A + dim im A = n, ...),
Probabilities (Definitions, conditional probabilities, random variables, expected runtime of a random exit loop, some applications, ...),
Integers modulo N (Definition, inversion and extended Euclidean algorithm, square and multiply, exponentiation, Theorem of Lagrange, of Euler and Fermat's little theorem, RSA correctness and efficiency, ...).

You can download the screen notes as PDF.

Week 2 - Algorithms and Analysis

Week 3 - Regular Languages, Context-Free Languages, Processes and Concurrency

Slides:

Regular languages (PDF),
Context-free languages (PDF),
Processes and concurrency (PDF).

Week 4 - Complexity

Allocation

equivalent V4+Ü4
Note thar all Media informatics courses only start on 27th of October, so that everybody can participate in this course.