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 edX.

Visit the link to the online course below. Register there and enroll in the edX 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)
PD Dr. Walter Unger

Students are encouraged to ask and answer any questions related to the course on the mailinglist. You can always post on 22us-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.

For meetings with your fellows you can use this free BBB room.

The exam will happen after all four weeks of the course, thus some time next spring or summer. Due to the imponderabilia of the pandemic we do not even fix the form of the exam. It may be a classical presence exam or it may be online oral exams. We wil decide details next spring and publish them via the mailing list — so sign up, see above.

• Kick-off: Monday, 10 October 2022, 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 10 - Fri 14 October 2022, online course (Michael Nüsken).
  Online room, daily collect/kickoff 09⁰⁰.
• Week 2: Mon 17 - Fri 21 October 2022, online course (Michael Nüsken).
  Online room, daily collect/kickoff 09⁰⁰.
• Week 3: Mon 6 - Fri 10 March 2023, online course (Thomas Noll).
  Kick-off and daily Q&E meetings: 09⁰⁰ Zoom, see third weeks page.
• Week 4: Mon 13 - Fri 17 March 2023, online course (Walter Unger).
  Kick-off ahd daily session start; 09⁰⁰, zoom. Afternoon sessions including Q&E Mon-Thu 13⁰⁰, zoom.

All material for week 1 and week 2 is in the online course which is available from July 2022 to December 2023.

You find a version of the slides on sciebo until September 2023. [Registering at sciebo and installing the client helps here and later.]

• At least week 1 & 2 of the course take place 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).
  (For the Uni ID at Bonn you will need to fill in your data online [choose "guest", "Cooperation study program media informatics Aachen"] and then send an email with a scan of your student card and some identity card. In return, you will obtain credentials via standard mail. This is then enough to apply for a b-it account.)

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, ...).

You might enjoy solving the geocache Felix Bauklötze.

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

Kick-off ahd daily session start; 09⁰⁰, zoom. Afternoon sessions including Q&E Mon-Thu 13⁰⁰, zoom.

Slides.

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