Foundations of informatics - a bridging course

This course is listed

• in Aachen RWTHonline as Foundations of informatics - a bridging course,
• in Bonn Basis as Foundations of Informatics - a bridging course.

To participate in week 1 and 2 of this course, you must register at *.

Visit the link to the online course below. Register there and enroll in the * course. Once you have done that you can reenter similarly at any time. This is self-paced, you do not need to wait for the kick-off.

Dr. Michael Nüsken
Prof. Dr. Thomas Noll (contact person)
Prof. Dr. Martin Hoefer

NOW: Students are encouraged to ask and answer any questions related to the course on the mailinglist. You can always post on 25us-brico-at-lists.bit.uni-bonn.de. We will use it for announcements regarding the course and exams(!). To subscribe to or unsubscribe from the mailing list visit the list's Info page.

• Kick-off: Monday, 13 October 2025, 09⁰⁰-09³⁰, hybrid: b-it-max 0.109 and online room.
  Just afterwards, we will perform a speed grouping. 09³⁰-11³⁰.
• All teaching in week 1/2 is online. To participate
  • either join the kick-off
  • or email me explaining your reasons.
• Week 1: Mon 13 - Fri 17 October 2025, online course (Michael Nüsken).
  Online room, daily collect/kickoff 09⁰⁰.
• Week 2: Mon 20 - Fri 24 October 2025, online course (Michael Nüsken).
  Online room, daily collect/kickoff 09⁰⁰.
• Week 3: Mon 23 - Fri 27 March 2026, online course (Thomas Noll).
  Kick-off and daily Q&E meetings: 09⁰⁰ Zoom, see third week's page.
• Week 4: Mon 30 March - Thu 2 April 2026 and Tue 7 April 2026, online course (Martin Hoefer).
  Kick-off and daily meetings: 09⁰⁰ Zoom, see fourth week's page.

• At least week 1 & 2 of the course take place mostly online. This is mainly self-paced and can be performed at any time. There will be kick-offs in the respective time for getting  to know each other, keeping pace and asking questions.
• The courses of the Media Informatics programme only start after the first two weeks of the bridging course. A similar agreement for the Software Systems Engineering programme does not exist, you have to arrange with the collision.
• For some students this course is compulsary. That means: you have to pass the exam eventually. You have two occasions for the exam every year, typically in April and June. In particular, for receiving in-time messages about exam form and schedule please sign up to the mailing list.
• You have to register for the exam in your respective program (ie. not with us!).

Possibly, your study advisor cares for first network access.

• You may use eduroam.
• Apply for a b-it account (includes applying for a Uni ID at Bonn).
• WARNING: Make sure that you read the email associated with your Uni ID!

This week will deal essentially with three subjects:

• Linear Algebra (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, ...).

Agenda

• foundations (first examples, asymptotic notation, solving recurrence equation)
• sorting (QUICKSORT, sorting in linear time)
• data structures (linked lists, binary search trees)
• graph algorithms (elementary (breadth-first, depth-first), single-source shortest path)

Literature

• Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 3rd edition, MIT Press, 2009.
• Goldreich, Computational Complexity: A conceptual perspective, Cambridge University Press, 2008.
• Knuth, TAOCP, Vol. 1 -- Fundamental Algorithms, 3rd edition, Addison-Wesley.

Regular Languages

• Introduction to Formal Languages
• Deterministic and Nondeterministic Finite Automata
• Regular Expressions and Languages
• Closure and Decidability Properties

Context-Free Languages

• Context-Free Grammars and Languages
• Relation to Regular Languages
• Pushdown Automata
• Closure and Decidability Properties

Find details about this week on Third week's page:

1. Introduction to computability
2. Undecidable problems; halting problem; theorem of Rice
3. Recursive enumerability; PCP; Hilbert's tenth problem
4. Introduction to complexity
5. NP-completeness of selected graph problems
6. NP-completeness of selected number problems

Find details about this week on fourth week's page:

Equivalent V4+Ü4.
For some MI-students this course is obligatory, for the others it's optional. There are no credits for this course.