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.
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.
*********Distance Learning*************
Due to the COVID-19 crisis, this course will be held on-line using the TUWEL platform. Students will receive videos of lectures on all topics of the course. The lectures will be discussed in Q+A Session (2 per block) via Zoom. Exercises will be managed using TUWEL. Solution to the exercises will be presented in Q+A Session (1 per block) via Zoom.
A discussion forum on TUWEL will be used to answer student questions and to clarify issues.
Examination form: Online written exam via TUWEL. The examiners and the students are permanently connected via audio and video in a online meeting. Solutions can be provided directly to TUWEL or scanned and uploaded by the student within the time specified by the examiner (approx. 5 minutes).
******************************************
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