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