Anno di corso: 1

Anno di corso: 2

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

SISTEMI COMPLESSI E INCERTI

Scheda dell'insegnamento

Anno accademico di regolamento: 
2017/2018
Anno di corso: 
2
Anno accademico di erogazione: 
2018/2019
Tipo di attività: 
Obbligatorio a scelta
Lingua: 
Italiano
Crediti: 
6
Ciclo: 
Secondo Semestre
Ore di attivita' didattica: 
48
Prerequisiti: 

Conoscenze acquisite nei corsi base della Laurea Triennale in Informatica.

Moduli

Metodi di valutazione

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

L'esame consiste di due parti.

parte 1. Esame orale su tutti gli argomenti riguardanti i Sistemi Complessi (punti 1, 2, 3, 4 e 5 del programma dettagliato). Le dimostrazioni dei teoremi saranno richieste solo una parte scelta dal candidato.

parte 2. Il candidato può scegliere tra un esame orale su su tutti gli argomenti riguardanti i Sistemi Incerti (punti 1,6,7 e 8 del programma dettagliato) oppure un approfondimento riguardante i Sistemi Incerti da discutere in un esame orale. L'approfondimento richiedere la presentazione di una relazione scritta su un argomento concordato con il docente, tra quelli proposti dal docente stesso o suggerito dallo studente.

La valutazione finale tiene conto di entrambe le parti.

Valutazione: 
Voto Finale

Obiettivi formativi

Il corso fornisce gli strumenti per trattare in modo formale i modelli che descrivono sistemi complessi e sistemi incerti. Lo studente sarà, inoltre, in grado di affrontare problemi concreti anche con tecniche tipiche della soft computing.

Contenuti

Trattamento formale e applicazioni dei sistemi complessi e incerti.

Automi cellulari , Tiling e applicazioni (modellazione di di fenomeni reali, crittografia), dinamica simbolica e applicazioni (coding, memorizzazione di dati su dispositivi fisici, algoritmo PageRank di Google), decidibilità/indecidibilità di proprietà formali, logiche a più valori di verità, logiche epistemiche, fuzzy sets, rough set.

Programma esteso

1 ) Introduzione

- cosa è un sistema complesso, cosa è l’incertezza e da quali diverse fonti deriva

- ripasso di logica proposizionale classica, insiemi parzialmente ordinati e algebra booleana

2) Automi Cellulari come modelli di sistemi complessi:

- proprietà formali associate a raggiungibilità, reversibilità, stabilità, instabilità e caos. Relative classificazioni.

- algoritmi di decisione/indecidibilità di proprietà formali

- esempi di Automi Cellulari significativi

3) Tiling:

- Tile set, tiling, simulazione di una macchina di Turing e Domino Problem

- proprietà indecidibili in Automi Cellulari

- cenni al self-assembly (DNA computing)

4) Dinamica simbolica:

- subshifts e linguaggi

- subshifts di tipo finito e sofici con relative rappresentazioni

- entropia di un subshift, Teorema di Perron Frobenius, schemi di codifica/decodifica di dati basati su subshift

5) Applicazioni (Sistemi Complessi):

- crittografia (secret sharing schemes e generazione di numeri pseudo-casuali) mediante Automi Cellulari

- simulazione di un fluido, del traffico veicolare, ... mediante Automi Cellulari

- l'algoritmo PageRank di Google e data storage (subshifts)

- Reaction Systems come modello per simulare reazioni biochimiche

6) Logiche Multivalore e Fuzzy Sets

- Logiche a tre valori e loro applicazioni (valore NULL in database)

- Logiche a valori di verità nell'intervallo [0,1]: t-norme, t-conorme, reticoli residuati.

- Fuzzy sets, variabili linguistiche e controllo fuzzy

7)Introduzione alle rappresentazione della conoscenza con logiche modali ed epistemiche

8) Rough Sets:

- Approssimazione di concetti

- Apprendimento di regole, feature selection e applicazione al data mining

- Legame con logiche modali e multivalore

Bibliografia consigliata

P. Kurka. Topological and symbolic dynamics. Société Mathématique de France, 2004.

D. Lind, B. Marcus. An introduction to Symbolic dynamics and coding. Cambridge University Press, 1995.

J. Kari. Cellular Automata. Lecture Notes. http://users.utu.fi/jkari/ca/

D. Palladino, C. Palladino, “Logiche non classiche. Un’introduzione”, Carocci, 2007

G. Gerla, “Logica fuzzy. I paradossi della vaghezza”, 2011

D. Ciucci, "Rough Sets and Non-Classical Logics”, Dispense

Metodi didattici

Lezioni ed esercitazioni in aula. Supporto in e-learning allo studio individuale con materiale fornito dai docenti.