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 assessment is based on exercises for each of the four blocks (max. 10 points per block) and a written exam (max. 60 points). In total, the students can achieve 4*10+60=100 points. A positive overall assessment requires at least 20 points for the exercise part and 30 points at the written exam. Positive grades are obtained from the sum of points according to the following table:
- 50-61 points: passed (genügend, 4)
- 62-74 Punkte: satisfactory (befriedigend, 3)
- 75-87 Punkte: good (gut, 2)
- 88-100 Punkte: excellent (sehr gut, 1)
