Università degli studi dell'Insubria

MODELLI DI CALCOLO

A.A. di erogazione 2017/2018

Laurea triennale in MATEMATICA
 (A.A. 2015/2016)
Anno di corso: 
3
Tipologia di insegnamento: 
Affine/Integrativa
Settore disciplinare: 
INFORMATICA (INF/01)
Crediti: 
8
Ciclo: 
Secondo Semestre
Ore di attivita' frontale: 
80
Dettaglio ore: 
Lezione (80 ore)

Obiettivi dell’insegnamento e risultati di apprendimento attesi
Il corso, di carattere teorico, ha come obiettivo principale l'acquisizione di nozioni di base su modelli di calcolo sequenziali e non sequenziali, e lo sviluppo delle capacità di formalizzazione, astrazione, modellazione di sistemi e analisi di problemi complessi.

Conoscenza e capacità di comprensione
Il corso si propone in primo luogo di presentare in modo rigoroso modelli di calcolo sequenziali e paralleli (macchine di Turing deterministiche, nondeterministiche, alternanti). Verranno poi analizzati modelli distribuiti a rete, sia sincroni che asincroni, ponendo particolare attenzione ai modelli basati su automi, anche temporizzati e probabilistici.
Lo studio di questi formalismi è indispensabile per la chiara comprensione di nozioni, risultati e concetti fondamentali per un informatico, tra i quali:
- la Tesi di Church-Turing e l’esistenza di classi di problemi non risolubili;
- la differenza tra aspetti sintattici e semantici;
- il ruolo delle risorse di calcolo, del nondeterminismo e del parallelismo, e l’esistenza di problemi di difficile soluzione, come i problemi di gioco;
- le varie tipologie di comunicazione in ambiente distribuito (Input/Output, sincrona, asincrona, broadcasting) e la formalizzazione e verifica di protocolli in rete;
- l’origine del Problema dell’esplosione combinatoria nella verifica di sistemi distribuiti ed eventuali tecniche euristiche per la sua soluzione;
- l’importanza di un approccio composizionale alla specifica di sistemi complessi e il ruolo delle interfacce di comunicazione in sistemi aperti.

Conoscenza e capacità di comprensione applicate
Il corso, anche se di carattere fondamentalmente teorico, ha una notevole valenza applicativa. In particolare, le basi teoriche apprese permettono di affrontare in modo matematicamente chiaro e rigoroso numerosi problemi di carattere applicativo:
verifica di protocolli e di circuiti, problematiche di sicurezza in rete, planning, analisi di proprietà legate al tempo e alle probabilità in sistemi critici apprendimento computazionale.

Autonomia di giudizio e abilità comunicative
I risultati di apprendimento attesi sono legati alla capacità di utilizzare gli strumenti formali più opportuni in diversi contesti applicativi, motivandone adeguatamente la scelta.

Capacità di apprendere
I concetti e gli strumenti formali presentati nel corso favoriscono l'approfondimento individuale delle proprie conoscenze in diversi ambiti sia teorici sia applicativi, e la comprensione di argomenti trattati in altri corsi, come ad esempio le problematiche legate alla specifica, implementazione e verifica di sistemi complessi, sia software che hardware.

Prerequisiti: 

Il corso sarà il più possibile autocontenuto. Le nozioni di base su argomenti di solito trattati nei corsi di Algoritmi e Strutture Dati e Linguaggi e Automi (linguaggi, automi a stati finiti, Macchine di Turing, grammatiche) verranno se necessario riprese nel corso.

Contenuti e programma del corso
Il modello degli Automi a Stati finiti, capace di descrivere la struttura di controllo di un programma sequenziale o, più in generale, di un sistema stati/transizioni, e il modello della Macchina di Turing, capace di simulare ogni altro modello di calcolo e (in base alla Tesi di Church-Turing) di descrivere una qualunque computazione, sono le pietre angolari di tutta l’informatica moderna.
Entrambi i modelli però descrivono in modo naturale computazioni sequenziali, e non sono in grado di rappresentare adeguatamente sistemi distribuiti se non attraverso una nozione di nondeterminismo. Fin dal loro apparire però gli automi a stati finiti (che, singolarmente, rappresentano come si è detto un sistema sequenziale) sono stati associati all’idea di rete. Il fondamentale lavoro di McCulloch e Pitts introduce infatti gli Automi a stati finiti per modellare astrattamente neuroni, con l’obiettivo di descrivere una rete di neuroni formali. Von Neumann poi estenderà questo approccio introducendo gli Automi cellulari come modello di rete sincrona e a topologia fissa. Analogamente, nell’idea di Turing di Macchine con Oracolo si possono osservare i germi di una idea di comunicazione tra entità connesse attraverso un canale di comunicazione.
Nel corso verranno ripresi i modelli di calcolo sequenziali: Automi a stati finiti, come modello per il controllo finito di un programma/sistema discreto, Macchine di Turing deterministiche e con Oracolo, come modello di calcolo generale. Verranno poi introdotte le Macchine di Turing non deterministiche e Alternanti, come modelli di calcolo parallelo, studiando la relazione tra questi modelli e le importanti classi di problemi computazionali P, NP, PSpazio, con accenni alla complessità di problemi di gioco e alla Teoria dei Giochi.
Si considereranno poi modelli di calcolo distribuiti sia sincroni, come il modello degli Automi Cellulari di Von Neumann, storicamente interessante ed ancora oggi importante per le sue applicazioni pratiche, sia asincroni: dalle reti di Petri, fino ai modelli basati su prodotto di automi, tra i quali presenteremo gli Automi Asincroni di Zielonka.
Naturalmente, sia i modelli sequenziali sia quelli distribuiti (sincroni o asincroni) possono essere arricchiti introducendo per esempio il tempo, per rappresentare più adeguatamente sistemi critici, oppure le probabilità, gli aspetti gerarchici, ecc. Considereremo in particolare modelli probabilistici: automi di Rabin, catene di Markov.
Parallelamente allo sviluppo di modelli ad automi per sistemi distribuiti e reti, si è assistito negli ultimi anni alla nascita di formalismi che descrivono computazioni “parallele” o “concorrenti” privilegiando l’idea di riscrittura e di approccio algebrico tipico delle Espressioni regolari e del Term rewriting. Tra questi, accenneremo ai Sistemi di Lindenmayer, ed al modello CCS di Milner, che ha dato origine ad una pletora di Algebre di Processi, tra loro difficilmente confrontabili.
Discuteremo infine in modo approfondito l’importanza di un approccio composizionale alla costruzione di sistemi a rete, partendo dal fondamentale risultato di Kleene per arrivare, attraverso la definizione di opportune operazioni di composizione in serie, parallelo con o senza comunicazione, feedback tra sistemi aperti, alla descrizione matematica di reti a topologia variabile, dove le componenti sono chiaramente individuate insieme ai loro canali di connessione.

Tipologia delle attività didattiche
Lezioni frontali, tenute anche in modalità a distanza.

Lezioni frontali in modalità teledidattica, tenute alternativamente a Como e Varese

Modalita' di verifica dell'apprendimento: 

Esame orale.
E' possibile portare un argomento a scelta dello studente, come introduzione alla prova.

Testi e materiale didattico
Dispense in rete: Calcolabilità (testo che verrà trattato parzialmente), Complessità e Teoria dei Giochi (testo che verrà trattato parzialmente).
R.F.C. Walters, Categories and Computer Science, Cambridge University Press, 1992 (testo trattato parzialmente)
Essendo il corso fortemente innovativo, non esiste al momento un testo che riassuma e presenti in modo coerente il materiale trattato a lezione; saranno quindi preparate dispense e slide delle lezioni e messe a disposizione sul sito di e-learning. Verranno inoltre proposti articoli scientifici di approfondimento.

Modalità di verifica dell’apprendimento
L’esame consiste in un colloquio orale teso all'accertamento dell’acquisizione e della corretta comprensione dei contenuti dei testi indicati; su tali contenuti saranno formulate almeno due domande. E’ previsto un accertamento della capacità di analisi critica interdisciplinare e di autonomia di giudizio sugli argomenti principali del corso (almeno due domande); in particolare, si terrà conto della comprensione delle motivazioni e delle applicazioni – anche pratiche- del materiale teorico introdotto nel corso. Inoltre sarà richiesta la conoscenza degli argomenti eventualmente trattati a lezione e non presenti nei testi consigliati, riassunti nel materiale didattico disponibile sul sito e-learning (almeno una domanda). Il voto finale, espresso in trentesimi, terrà conto dell’esattezza e della qualità delle risposte (70%), nonché dell’abilità comunicativa mostrata durante il colloquio (10%) e della capacità di motivare adeguatamente affermazioni, analisi e giudizi (20%).

Verrà comunicato dalla Segreteria l'orario di ricevimento del docente.
Su appuntamento, o prima/dopo le lezioni, sarà possibile contattare il docente per chiarimenti, sia a Varese sia a Como.

clicca sulla scheda dell'attività mutataria per vedere ulteriori informazioni, quali il docente e testi descrittivi.

corso di studio in: INFORMATICA

Cerchi il programma? Potrebbe non essere ancora stato caricato o riferirsi ad insegnamenti che verranno erogati in futuro.
Seleziona l‘anno in cui ti sei immatricolato e troverai le informazioni relative all'insegnamento del tuo piano di studio.

A.A. 2017/2018

Anno di corso: 3
Curriculum: PERCORSO COMUNE

A.A. 2016/2017

Anno di corso: 3
Curriculum: PERCORSO COMUNE

A.A. 2014/2015

Anno di corso: 3
Curriculum: PERCORSO COMUNE

A.A. 2013/2014

Anno di corso: 3
Curriculum: PERCORSO COMUNE