Anno di corso: 1

Anno di corso: 2

Crediti: 6
Crediti: 6
Crediti: 6
Crediti: 6
Crediti: 6
Crediti: 6
Crediti: 12
Tipo: A scelta dello studente
Crediti: 3
Tipo: Lingua/Prova Finale
Crediti: 33
Tipo: Lingua/Prova Finale

MODELLI E COMPUTAZIONE

Scheda dell'insegnamento

Anno accademico di regolamento: 
2015/2016
Anno di corso: 
1
Anno accademico di erogazione: 
2015/2016
Tipo di attività: 
Obbligatorio
Crediti: 
12
Ciclo: 
Primo Semestre
Ore di attivita' didattica: 
104
Prerequisiti: 

nessuno

Moduli

Metodi di valutazione

Tipo di esame: 
Orale
Modalita' di verifica dell'apprendimento: 

scritto, orale

Valutazione: 
Voto Finale

Obiettivi formativi

Il corso ha come obiettivo l'acquisizione di capacità di analisi e di sintesi in riferimento ai modelli e metodi computazionali utilizzati dall'informatica. In particolare lo studente dovrà acquisire capacità di formalizzare e modellare problemi utilizzando anche approcci teorici moderni sviluppati per poter trattare problematiche computazionali nel mondo web e nell'ambito della analisi e verifica di sistemi software.
Il corso si compone di due moduli, il primo denominato Modelli della concorrenza fornisce gli strumenti teorici di base per comprendere e manipolare concetti di base dell'informatica relativi al comportamento e descrizione di processi, quali ad esempio la concorrenza.
Il secondo modulo, denominato Teoria della Computazione ha come obiettivo l'acquisizione di strumentalità di base dell'informatica volte alla comprensione della complessità computazionale dei problemi, alla loro classificazione e alle metodologie algoritmiche per la loro soluzione.
Inoltre, si intendono fornire capacità in merito alla soluzione di problematiche teoriche poste dalle nuove tecnologie (web, flusso di dati, reti complesse, etc.) mediante strutture dati recentemente proposte.

Contenuti

Teoria della Computazione
Nozioni di base di teoria della computazione (decidibilità, intrattabilità, riduzioni). Classificazione dei problemi in funzione della complessità computazionale. Complessità di approssimazione.
Approcci moderni per la gestione, indicizzazione, compressione di grandi mole di dati, sia con strutture dati che con tecniche algoritmiche avanzate.
Strutture dati di indicizzazione (es. suffix-tree, trie, hashing), pattern matching, paradigma shift-And, compressione dati.
Applicazioni ed esemplificazioni all'analisi del web (reti complesse).

Modelli della concorrenza
Modelli formali per la specifica e la verifica di correttezza.
Modelli della concorrenza: modelli interattivi e reattivi, calcoli di processi e reti di Petri.
Sintassi e semantica a interleaving (sistemi di transizioni) e a ordini parziali (reti di Petri), semantica osservazionale e bisimulazione.
La specifica di proprietà e la loro verifica (logiche modali e temporali, tool di verifica).

Programma esteso

argomento
1 Nozioni di base di teoria della computazione (decidibilità, intrattabilità, riduzioni). Classificazione dei problemi in funzione della complessità computazionale. Complessità di approssimazione.

2 Approcci moderni per la gestione, indicizzazione, compressione di grandi mole di dati, sia con strutture dati che con tecniche algoritmiche avanzate.

3 Strutture dati di indicizzazione (es. suffix-tree, trie, hashing), pattern matching, paradigma shift-And, compressione dati.

4 Applicazioni ed esemplificazioni all'analisi del web (reti complesse).

5 Modelli formali per la specifica e la verifica di correttezza. La semantica assiomatica dei programmi sequenziali

6 Modelli della concorrenza: modelli interattivi e reattivi, calcoli di processi e reti di Petri.

7 Sintassi e semantica a interleaving (sistemi di transizioni) e a ordini parziali (reti di Petri), semantica osservazionale e bisimulazione

8 La specifica di proprietà e la loro verifica (logiche modali e temporali, tool di verifica)

Bibliografia consigliata

Verranno distribuite dispense varie. Si segnala inoltre il seguente testo di riferimento:
L. Aceto, A. Ingolfsdottir, K.G. Larsen, J. Srba, Reactive Systems, modelling, Specification and verification, Cambridge Univ. Press, 2007.
http://rsbook.cs.aau.dk/index.php/Main_Page

Metodi didattici

Lezione frontale, esercitazione