Introduction to complexity theory: problem reductions, P versus NP, undecidability; SAT solving and its applications in computer science; introduction to the formal semantics of programming languages; formal verification of programs; model checking and its applications in hard- and software verification.
The course is organized 4 blocks; each block consists of a lecture and consolidation part.
Lectures are provided via pre-recorded videos.
The consolidation part of each block has 3 live-lectures, in order to dicuss and solve examples. Students receive for each block a set of examples they have to solve. They receive individual feedback to their solutions.
Three additional classes are provided to recall basic proof techniques.
Please note: Depending on the currently required Covid measures, Q+A sessions might be online via Tuwel instead of in the lecture hall. Exams might be postponed or done via TUWEL.
Ects breakdown
2 h introduction (first meeting)
60 h lecture (20 dates à 2h + 1h preparation)
40 h exercise sheets (4 sheets, 10 exercises/sheet, 1h/exercise)
16 h discussion of exercises (8 dates à 2h)
30 h preparation for written exam
2 h written exam
-----------------------------------------------------------
150 h = 6 Ects