Course Syllabus
Obiettivi
Coerentemente con gli obiettivi formativi del Corso di Studio, l'insegnamento si propone di fornire allo studente le conoscenze 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 e dell’apprendimento automatico.
Contenuti sintetici
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à, teoria dell’evidenza, 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 e variabili linguistiche
7)Introduzione alle rappresentazione della conoscenza con teoria della possibilità e teoria dell’evidenza
8) Rough Sets:
- Approssimazione di concetti
- Apprendimento di regole, feature selection e applicazione al data mining
- Legame con logiche multivalore
9) Introduzione alla gestione dell’incertezza nell’apprendimento automaticoPrerequisiti
Conoscenze acquisite nei corsi base della Laurea Triennale in Informatica.
Modalità didattica
Lezioni ed esercitazioni in aula. Supporto in e-learning allo studio individuale con materiale fornito dai docenti. Il corso viene erogato in italiano, ma se uno studente straniero è presente, il corso può essere erogato in inglese.
Qualora perdurasse il periodo di emergenza Covid-19, le lezioni ed esercitazioni saranno videoregistrate e generalmente trasmesse in modalità sincrona.
Materiale didattico
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”, DispensePeriodo di erogazione dell'insegnamento
Secondo Semestre
Modalità di verifica del profitto e valutazione
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. Per quanto riguarda la parte sull'incertezza, verranno assegnati esercizi (solitamente 3) da consegnare su vari argomenti del corso, tra cui un approfondimento 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 in egual misura.
Orario di ricevimento
Su appuntamento
Aims
In line with the educational objectives of the Master Degree in Computer Science, the course aims at providing the knowledge to formally face models describing complex systems and uncertain systems. Moreover, the student will be able to deal with real problems also by techniques from soft computing and machine learning.
Contents
Formal treatment and applications of complex and uncertain systems.
Cellular Automata, Tiling and applications (modelling of real systems and cryptography), symbolic dynamics and applications (coding, data storage, Google's PageRank algorithm), many-valued logics, evidence theory, fuzzy sets, rough sets.
Detailed program
1) Introduction
- what a complex system is, what the uncertainty is and from which different sources it comes
- revision of basic notions: classical propositional logic, partially ordered sets and Boolean algebra
2) Cellular Automata as models for complex systems:
- formal properties associated to reachability, reversibility, stability, instability, and chaos. Related classifications
- decision algorithms/undecidability of formal properties
3) Tilings:
- Tile set, tiling, simulation of a Turing machine, and Domino Problem
- undecidable properties of Cellular Automata
- hint of self-assembly (DNA computing)
4) Symbolic Dynamics:
- subshifts and languages
- subshifts of finite type, sofic subshifts and related representations
- entropy of a subshift, Perron Frobenius Theorem, data coding/decoding schemas based on subshifts
5) Applications (Complex Systems):
- cryptography (secret sharing schemes and pseudo-random number generation) by Cellular Automata
- fluid simulation, traffic simulation,... by CA
- Google's PageRank algorithm and data storage (subshifts)
- Reaction Systems as a model for simulations of biochemical reactions
- Three valued logics and applications (NULL value in database)
- Logics with truth values in [0,1]: t-norms, t-conorms and residuated lattices
- Fuzzy sets and linguistic variables
7) Introduction to knowledge representation with evidence theory and possibility theory
8) Rough Sets:
- Concept Approximation
- Learning of rules and feature selections with applications in data mining
- Link with many-valued logics
9) Introduction to uncertainty handling in machine learningPrerequisites
Basic Knowledge from the
Computer Science Degree.
Teaching form
Lectures and practice exercises. E-learning support for individual study with material provided by the instructors. The teaching language is Italian. However, the course may be provided in English language if a foreign student attends lectures and exercises.
During the Covid-19 emergency, lectures and practice
exercises will be online and recorded.
Textbook and teaching resource
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”, Lecture NotesSemester
Spring Semester
Assessment method
The exam consists of two parts.
part
1. An oral exam on all the topics concerning the Complex Systems (items
1, 2, 3, 4, and 5 of the detailed program). The Theorem's proofs will
be required only on a part choosen by the candidate.
part 2. Regards to the uncertainty part, some exercises (usually 3) will be assigned on different topics of the course, including a written dissertation on a topic agreed with the lecturer, proposed by the lecturer himself or by the student.
The final assessment takes into account equally the assessments of both the parts.
Office hours
On appointment