Theoretical Computer Science 1 WS25/26

Theoretical Computer Science 1 WS25/26

News

Nov 10th - We drop the lecture on tuesday, Nov 11th.

Oct 20th - Tutorial 0 "Introduction to Proving" continues on tuesday, Oct 21st.  Topics: inductive sets and inductive proofs.

Oct 17th - The tutorium will happen biweekly on mondays.  The first tutorium next monday contains general proof methods, as they will be used in this lecture.

July 18th - The information on this page is preliminary.

Organisation

The lecture is held by Prof. Dr. Roland Meyer.  The exercise is held by René Maseli.

On two times per week, the lecture leads through the topics of this course.  Each two weeks, the monday lecture is replaced by an exercise that prepares the students for the homeworks and the exam.

Lecture / Exercise (weekly): [Stud.IP]

  • Mo, 13:15 - 14:45 in PK 11.1
  • Di, 15:00 - 16:30 in PK 11.1

Tutorials (biweekly): [Stud.IP]

  • Mo, 11:30 - 13:00 in IZ 358 with Luca Thomas, starting Nov 10th
  • Tu, 09:45 - 11:15 in IZ 358 with Anton Opaterny, starting Nov 11th
  • Th, 09:45 - 11:15 in IZ 358 with Natalia Gacek, starting Nov 13th
  • Th, 09:45 - 11:15 in SN 20.1 with Thomas Haas, starting Nov 13th
  • Th, 13:15 - 14:45 in IZ 358 with Natalia Gacek, starting Nov 13th
  • Fr, 08:00 - 09:30 in IZ 358 with Luis Höling, starting Nov 14th
  • Fr, 09:45 - 11:15 in IZ 358 with René Maseli, starting Nov 14th

"Lerntreff Theorie" (weekly):

  • Fr, 08:00 - 09:30 in IZ 358 with Max Bierwagen, starting Nov 3rd

To finish this course, you need to fulfill two requirements:

  • Prüfungsleistung: By passing the exam at the end of this semester.
  • Studienleistung: By earning at least 50% of the points on your homework submissions.

The written exam will take place on friday, March 06th 2026, from 11:00 AM to 1:00 PM.

  • The exam will consist of 10 exercieses of 10 points each.  It will take 120 minutes.
  • We allow no auxiliaries other than a dictionary and a both-sided DIN A4 sheet of selfmade handwritten notes.
  • We recommend the past exams below as preparation.

Material

Semester Plan

Date Topic
20. Okt. Exercise 0: Einführung in Beweise
27. Okt. Lattices, Fixed points, Theorem of Knaster & Tarski
28. Okt. Continuity, Theorem of Kleene
3. Nov. While programs
4. Nov. Dataflow analyses
10. Nov. Exercise 1
17. Nov. Exercise 2
18. Nov. Regular languages
24. Nov. Finite automata and Arden's Lemma
25. Nov. Completeness of regular languages
1. Dez. Exercise 3
2. Dez. Theorem of Myhill & Nerode
8. Dez. Minimal DFAs
9. Dez. Pumping-Lemma for regular languages
15. Dez. Exercise 4
16. Dez. History of Computer Science
5. Jan. Formal grammars and contextfree languages
6. Jan. Chomsky normal form and Greibach normal form
12. Jan. Exercise 5
13. Jan. Pumping-Lemma for contextfree languages
19. Jan. CYK-Algorithm
20. Jan. Pushdown automata
27. Jan. Exercise 6
28. Jan. Characterisation of contextfree languages
2. Feb. Completeness of contextfree languages
3. Feb. Exam preparations

Videos

Past Exams

References

  • U. Schöning: Theoretische Informatik - kurz gefasst. Springer, 2008.
  • J. E. Hopcroft, R. Motwani, J. D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley Longman, 2002.
  • M. Sipser: Introduction to the Theory of Computation. Cengage Learning, 2012.
  • M. Nebel: Formale Grundlagen der Programmierung. Vieweg+Teubner, 2012.
    Erhältlich als E-Book (auf den Seiten der Universitätsbibliothek, ggf. nur aus dem Uni-Netz).
Last update: 03.11.2025