- Sistemi Complessi e Incerti
- Introduzione
Syllabus del corso
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.
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à, fuzzy sets, rough
set, belief functions, teoria della possibilità, applicazioni all'apprendimento automatico.
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) Introduzione all'incertezza, Logica e Algebra Booleana
7) 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
8)Introduzione alle rappresentazione della conoscenza con logiche modali ed epistemiche
9) Rough Sets:
- Approssimazione di concetti
- Apprendimento di regole, feature selection e applicazione al data mining
- Legame con logiche modali e multivalore
- Ortocoppie e ortopartizioni con applicazioni al machine learning10) Altri formalismi
- Teoria della Possibilità
- Belief Functions
Prerequisiti
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.
Nel periodo di emergenza Covid-19 le lezioni ed esercitazioni saranno videoregistrate (alcune di esse potranno essere trasmesse in modalità sincrona);
ci saranno inoltre dei momenti sincroni (in streaming, non registrati)
di discussione e risposta alle domande degli studenti.
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 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.
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, fuzzy sets, rough sets, possibility theory, belief functions and application to machine learning.
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
6) Introduction to uncertainty, Boolean logic and algebra.
7) Many valued logics and Fuzzy Sets- 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, linguistic variables and fuzzy control
8) Introduction to knowledge representation with modal and epistemic logics
9) Rough Sets:
- Concept Approximation
- Learning of rules and feature selections with applications in data mining
- Link with modal and many-valued logics
- Orthopair, orthopartitions and their application to machine learning10) Other formalisms:
- Possibility theory
- Belief functions
Prerequisites
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 recorded (some of them could be online). There will be some
discussions and answers to questions in streaming and not 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 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