Foundations of informatics - a bridging course
This course is listed in Aachen online as Foundations of informatics - a bridging course and listed in Bonn Basis as Foundations of Informatics - a bridging course.
Lecture
Dr .Michael Nüsken (contact person)
Prof. Dr. Thomas Noll
PD Dr. Walter Unger
Exam
Due to the corona pandemic the exams will be performed orally in a remote setting. Updated plans are as of 24 June 2020. Still treat this info with care as no one knows the future. Stay tuned.
Exams will be performed orally in a remote setting.
Each student registered in RWTHonline has been contacted individually for making an appointment and informed about the precise procedure.
Each oral examination will take about 40 minutes in some 1 hour time slot via zoom.
For preparing to such an oral examination it is always a good idea, to identify for oneself which are the most important corner stones within each topic. And you should be able to answer the question which topic/result/issue is your favorite within such a week.
- Pre-Exam meeting: Friday, 10 July 2020, 1000-1200, digital zoom room (meeting ID: 992 8410 8809 and password: 328956).
- First exam period: 25-27 August, 1 September 2020.
- Second exam period: second half of September.
The exam is about the entire course.
The exam is offered twice a year. There is no further limit on the number of attempts.
Time & Place
- 7 - 11 October 2019, b-it 0.109 (Michael Nüsken) and online.
- 14 - 18 October 2019, b-it 0.109 (Michael Nüsken) and online.
- 02 - 06 March 2020, room see below (Thomas Noll).
- 09 - 13 March 2020, room see below (Walter Unger).
First meeting: Monday, 7 October, 900.
Schedule as planned so far:
Week 1/2
- Kick-Off meeting: Mon, 7 October 2019, 0900-1100, b-it 0.109.
Bring your own devices and make sure that you have access to the computer science network, pools and computers. - Collect meeting 1: Fri, 11 October 2019, 1100-1300, b-it 0.109.
- Collect meeting 2: Fri, 18 October 2019, 1100-1300, b-it 0.109.
All other teaching in this part is online. To participate
- either come to the kick-off
- or email me explaining your reasons.
Week 3
Mon 1000 - 1230 and 1400 - 1700, b-it 0.109, each block includes 30 minutes break.
Tuesday is a self-learning day.
Wed-Fri 1000 - 1230 and 1400 - 1700, RWTH, each block includes 30 minutes break.
Week 4
Mon 1000 - 1230 and 1400 - 1700, b-it 0.109, each block includes 30 minutes break.
Tue-Fri 1000 - 1230 and 1400 - 1700, RWTH Aachen, Ahornstrasse 55, Building E1, Raum 4017 (Seminarraum des i1) , each block includes 30 minutes break.
Network access at Bonn
Possibly, your study advisor cares for first network access.
You may use eduroam.
For b-it accounts:
- You need to be inscribed at Aachen or Bonn in the first place.
- Next, you need to get a Uni Bonn ID at the HRZ.
- Finally, you may apply for a Student Account for Media Informatics or Guest to gain access at Bonn.
Some clarifications
- The course takes place at the b-it on Campus Poppelsdorf, Bonn and some parts online.
- The courses of the Media Informatics program only start after the first two weeks of the bridging course.
- A similar agreement for the Software Systems Engineering program 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. To write it you have two occasions every year, typically in April and June.
- You have to register for the exam in your respective program (ie. not with us!).
Online course
All material for Week 1/2 is in the online course which is available from September 2019 to June December 2020.
Week 1 - Mathematical tools
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, ...).
All material for Week 1/2 is in the online course which is available from September 2019 to June December 2020.
Addon
You might enjoy solving the geocache Felix Bauklötze.
Week 2 - Analysis of Algorithms
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.
All material for Week 1/2 is in the online course which is available from September 2019 to June December 2020.
Week 3 - Regular Languages, Context-Free Languages, Processes and Concurrency
For organisational details, please refer to this web site.
Regular Languages
- Formal Languages
- Finite Automata
- Regular Expressions
- Minimization of Deterministic Finite Automata
- The Pumping Lemma
Context-Free Languages
- Context-Free Grammars and Languages
- Context-Free and Regular Languages
- Decidability Problems of Context-Free Languages
- Closure Properties of Context-Free Languages
- Pushdown Automata
Week 4 - Complexity
- Introduction to computability
- Undecidable problems; halting problem; theorem of Rice
- Recursive enumerability; PCP; Hilbert's tenth problem
- Introduction to complexity
- NP-completeness of selected graph problems
- NP-completeness of selected number problems
For slides email Walter Unger.
Allocation
Equivalent V4+Ü4.
Note that all Media informatics courses only start in the third week of the lecturing period, so that everybody can participate in this course.
For some MI-students this course is obligatory, for the others it's optional. There are no credits for this course.