Verifica automatica di sistemi (2017/2018)

Codice insegnamento
4S003252
Docente
Andrea Masini
Coordinatore
Andrea Masini
crediti
6
Settore disciplinare
INF/01 - INFORMATICA
Lingua di erogazione
Italiano
Sede
VERONA
Periodo
II sem. dal 1-mar-2018 al 15-giu-2018.

Orario lezioni

Vai all'orario delle lezioni

Obiettivi formativi

Il corso si propone di fornire le basi teoriche delle principali tecniche di specifica e verifica di sistemi a stati finiti. In particolare, con riferimento ai sistemi di transizione, tecniche basate sulle tracce, sulla logica del tempo lineare e sulla logica del tempo ramificato.

Al termine del corso lo studente dovrà dimostrare di avere acquisito le conoscenze necessarie per ragionare formalmente su sistemi a stati finiti, con enfasi sui problemi di correttezza risolti in modo automatico (model-checking), attraverso metodi operazionali (tracce) logici (logiche temporali) ed algoritmici.

Queste conoscenze consentiranno allo studente di: i) specificare e provare formalmente proprietà di correttezza di semplici sistemi presentati come sistemi di transizione; ii) utilizzare logiche temporali (lineari e ramificate) per la specifica di proprietà; iii) padroneggiare metodi semantici per le logiche temporali.

Al termine del corso lo studente sarà in grado di: i) confrontare logiche temporali per la verifica automatica e scegliere tra queste le più adeguate a seconda del contesto d'uso; in fase di definizione di un processo di verifica fare le scelte progettuali più appropriate; ii) proseguire gli studi in modo autonomo nell’ambito della verifica formale.

Programma

Verifica dei sistemi:
l’approccio basato sul model checking
Sistemi di modellazione concorrenti:
sistemi di transizione,
parallelismo e comunicazione,
esplosione degli stati
Proprietà del tempo lineare:
safety e invarianti,
liveness,
fairness
Linear Temporal Logic:
sintassi,
semantica,
fairness,
model checking
Computation Tree Logic:
sintassi,
semantica,
espressività di CTL vs LTL,
fairness,
model checking simbolico
CTL *
Equivalenza e astrazione:
bisimulazione,
bisimulazione e equivalenza in CTL *

Testi di riferimento
Autore Titolo Casa editrice Anno ISBN Note
Christel Baier and Joost-Pieter Katoen Principles of Model Checking MIT press 2008

Modalità d'esame

Esame scritto (un'ora e mezzo per svolgere il compito).
Al fine di superare l'esame lo studente deve avere una conoscenza sufficiente di tutti gli argomenti (incluse le prove dei teoremi) e la capacità di risolvere esercizi simili a quelli visti durente le lezioni.
Migliore è la conoscenza degli argomenti del corso, migliore è il risultato dell'esame.

Opinione studenti frequentanti - 2017/2018