Automated program verification (2010/2011)

Course code
Name of lecturer
Maria Paola Bonacina
Maria Paola Bonacina
Number of ECTS credits allocated
Academic sector
Language of instruction
II semestre dal Mar 1, 2011 al Jun 15, 2011.

Lesson timetable

II semestre
Day Time Type Place Note
Tuesday 2:30 PM - 4:30 PM lesson Lecture Hall I  
Thursday 11:30 AM - 1:30 PM lesson Lecture Hall G  

Learning outcomes

The class presents problems and methods for program analysis and verification, by automated reasoning techniques such as theorem proving or model checking. Objective of the class is that the student understands the problems arising on one hand
in expressing the behavior of programs in logical formulae, and on the other hand in designing automated reasoners capable to handle such formulae efficiently.


Theorem proving in propositional logic: the Davis-Putnam-Logemann-Loveland procedure. Theorem proving in first-order logic: resolution and superposition. First-order theories. Hoare logic, annotations, partial and total correctness, states, paths, invariants. Invariant generation. Decision procedures for satisfiability modulo theories: equality, data structures, combination of theories by equality sharing, decision procedures based on resolution and superposition.

Assessment methods and criteria

For master students:
the exam consists of a written exam (C) and an individual project (P). The grade is given by 50% C + 50% P. This applies to the final exam at the end of the course.
In the following sessions, the exam consists of a written exam (E), whose difficulty is such to be equivalent to that of C+P, and whose grade determines alone the final grade.
Cheating is forbidden and will determine loss of points. Students may withdraw only by not handing-in the exam.
For PhD students:
oral exam consisting in the presentation of one or more papers from the literature.