Tu sei qui

Automi e Linguaggi

Automi e Linguaggi

Corso di Laurea Triennale in Informatica F004

SCV0327
Docente: Mauro Ferrari


CFU SSD LEZIONI ANNO LINGUA
6 INF/01 48 III Italiano


Obiettivi dell’insegnamento e risultati di apprendimento attesi
Il corso, di carattere teorico, ha come obiettivo principale l'acquisizione delle nozioni basilari su automi e linguaggi, 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 di fornire le conoscenze di base di Teoria degli Automi e dei Linguaggi , con particolare attenzione agli Automi a stati finiti visti come descrizione matematica del controllo finito di un programma o, più in generale, di un sistema discreto sequenziale, e alle Macchine di Turing, viste come modello generale di computazione. Lo studio di questi formalismi, pietre angolari di tutta l’informatica moderna, è indispensabile per la comprensione di nozioni, risultati e concetti fondamentali per un informatico, tra i quali: le nozioni di algoritmo o procedura sequenziali e la possibilità di una loro descrizione astratta attraverso sequenze, scelte e cicli, risultato alla base della programmazione sequenziale; l’esistenza di problemi non risolubili o di problemi “difficilmente” risolubili, in termini di risorse di calcolo, e quindi la necessità di una loro classificazione in classi di complessità; la chiara distinzione tra aspetti sintattici e semantici e la nozione di simulazione e riduzione, come strumento di confronto semantico tra formalismi o problemi sintatticamente diversi. 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: le applicazioni della Teoria degli Automi e dei Linguaggi
spaziano infatti dal riconoscimento di linguaggi artificiali e naturali, attraverso la teoria della compilazione, al pattern matching di stringhe (con applicazioni importanti alla bioinformatica), alla
descrizione e verifica di sistemi complessi software e hardware (Model Checking), alla teoria dei giochi. 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 e la comprensione di argomenti trattati in altri corsi, come ad esempio le problematiche legate alla specifica, implementazione e verifica di sistemi, sia software che hardware.

Prerequisiti
Propedeuticità: Algebra e geometria. E’ comunque utile aver sostenuto anche gli esami relativi ai i corsi di Programmazione, Algoritmi e Strutture Dati e Logica.

Contenuti e programma del corso
Fin dagli anni ’30 del secolo scorso l’attenzione di matematici e logici si è concentrata sulla definizione di modelli di calcolo che permettessero una più profonda comprensione delle nozioni di algoritmo, procedura, problema decidibile, quantità di risorse necessarie per la soluzione di un problema. I fondamentali lavori di Turing, Church, Von Neumann, Kleene e altri autori, che dimostrano l’equivalenza semantica di vari modelli di calcolo, hanno posto solide basi alla Teoria della Ricorsività e alla Teoria degli Automi e dei Linguaggi. 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 quindi le pietre angolari di tutta l’informatica moderna. Nel corso, dopo aver definito il monoide libero delle stringhe o parole su un alfabeto finito, si introdurranno le nozioni di base su linguaggi e grammatiche, con la classificazione di Chomsky. Si presenteranno i principali risultati sul modello degli Automi a Stati Finiti, visti come riconoscitori di linguaggi: il “Pumping Lemma” e le sue applicazioni, il teorema di minimizzazione di Nerode, l’equivalenza tra modelli deterministici e non deterministici e tra automi e grammatiche regolari. Particolare attenzione verrà dedicata al problema della descrizione composizionale di un sistema discreto, risolto nel caso sequenziale dal teorema di Kleene. L’esistenza di linguaggi non riconoscibili da automi a stati finiti porta immediatamente a considerare modelli di calcolo con memoria non limitata; tra questi, particolarmente interessanti sono gli Automi a Pila, deterministici e non deterministici, capaci di riconoscere linguaggi liberi dal contesto e quindi di fondamentale importanza per la teoria della compilazione; verranno accennate le tecniche di parsing LL(k) e LR(K). Nell’ultima parte del corso si introdurrà il modello della Macchina di Turing (deterministica, non deterministica), accennando ad altri modelli di calcolo sequenziali (Macchine a Registri, Linguaggio WHILE, Funzioni Ricorsive Parziali) per arrivare a motivare la fondamentale Tesi di Church –Turing e i principali risultati della Teoria della Ricorsività e della Complessità: problemi decidibili, esistenza di problemi non decidibili (Problema dell’Arresto), teorema di Rice (senza dimostrazione) e sue applicazioni; si introdurranno poi le fondamentali classi di complessità P, NP, PSpazio, la nozione di riduzione polinomiale e il Teorema di Cook (senza dimostrazione), ed esempi di problema NP-completi.

Tipologia delle attività didattiche
Lezioni frontali.

Testi e materiale didattico
Libro di testo: John E. Hopcroft, Rajeev Motwani, Jeffrey D Ullman. Automi, linguaggi e calcolabilità , Pearson Paravia Bruno Mondadori S.p.A. Terza Edizione, Marzo 2009.
Altro materiale (disponibile sul sito e-learning): slides, dispense.

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%).

Orario di ricevimento
Il ricevimento studenti si svolge su richiesta degli studenti.

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer