Università degli studi dell'Insubria

AUTOMI E LINGUAGGI

A.A. di erogazione 2016/2017

Laurea triennale in INFORMATICA (A.A. 2014/2015)
Docenti
Anno di corso: 
3
Tipologia di insegnamento: 
Caratterizzante
Settore disciplinare: 
INFORMATICA (INF/01)
Crediti: 
6
Ciclo: 
Primo Semestre
Ore di attivita' frontale: 
48
Dettaglio ore: 
Lezione (48 ore)

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 è 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 importanti applicazioni 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: 

Il corso non richiede prerequisiti. E’ utile comunque aver frequentato i corsi di Algoritmi e Strutture Dati e Programmazione, ed avere nozioni di base di Logica e e di Algebra.

Contenuti e programma del corso
Automi a stati finiti deterministici (DFA) e non-deterministici (NFA): definizione, nozione di computazione e linguaggio riconosciuto. Equivalenza fra i modelli.
NFA con epsilon-mosse (ε-NFA) ed equivalenza fra NFA e ε-NFA.
Espressioni regolari. Equivalenza fra espressioni regolari e ε-NFA.
Linguaggi regolari: principali proprietà e Pumping Lemma.
Grammatiche libere dal contesto: derivazioni, alberi sintattici, grammatiche ambigue.
Automi a pila (PDA): accettazione per stack vuoto e stato finale (equivalenza). Equivalenza fra I linguaggi liberi dal contesto e I linguaggi accettati da PDA.
Linguaggi liberi dal contesto: principali proprietà e Pumping Lemma.
La gerarchia di Chomsky.
Macchine di Turing deterministiche e non-deterministiche.
Linguaggi ricorsivamente enumerabili e problemi indecidibili.

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 della corretta comprensione dei contenuti dell’insegnamento, dell’acquisizione di un adeguata capacità di formalizzazione e del ragionamento analitico necessario a ragionare sui problemi discussi nell’insegnamento.

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. 2015/2016

Anno di corso: 3
Curriculum: PERCORSO COMUNE

A.A. 2013/2014

Anno di corso: 3
Curriculum: PERCORSO COMUNE