Università degli studi dell'Insubria

AUTOMI E LINGUAGGI

A.A. di erogazione 2019/2020
Insegnamento obbligatorio

Laurea triennale in INFORMATICA
 (A.A. 2017/2018)

Docenti

Anno di corso: 
3
Tipologia di insegnamento: 
Caratterizzante
Settore disciplinare: 
INFORMATICA (INF/01)
Crediti: 
6
Ciclo: 
Primo Semestre
Ore di attivita' frontale: 
52
Dettaglio ore: 
Lezione (40 ore), Esercitazione (12 ore)

Il corso, di carattere teorico, ha come obiettivo l'acquisizione da parte dello studente delle nozioni basilari relative alla teoria degli automi e dei linguaggi formali, compresi i principali risultati
limitativi nell'ambito della teoria della calcolabilità. Tali conoscenze sono rivolte a formare e ad aumentare la capacità di astrazione attraverso la rappresentazione simbolica e quindi la capacità della comprensione di un linguaggio scientifico astratto e simbolico che hanno un ruolo fondamentale in vari ambiti dell'informatica come, ad esempio, nello sviluppo dei compilatori, nella modellazione di sistemi complessi e nell'ingegneria del software. Lo studente svilupperà inoltre la conoscenza della terminologia specifica usata nell'ambito della teoria degli automi, dei linguaggi formali e della teoria della calcolabilità.

Per un proficuo apprendimento di questo insegnamento lo studente deve padroneggiare le nozioni matematiche e le tecniche dimostrative impartite nell’insegnamento fondamentale di Algebra e Geometria del primo anno, che dunque costituisce propedeuticità obbligatoria. Inoltre, è consigliabile che lo studente abbia frequentato e sostenuto gli insegnamenti fondamentali di Programmazione e Algoritmi e Strutture Dati del primo anno di corso.

• Prerequisiti matematici. (4h)
• Automi a stati finiti deterministici (DFA), automi a stati finiti non-deterministici (NFA). Equivalenza fra DFA, NFA. (10h)
• Automi a stati finiti con ε-mosse (ε-NFA). Equivalenza fra NFA e ε-NFA. (4h)
• Espressioni regolari. Equivalenza fra espressioni regolari e ε-NFA. (4h)
• Linguaggi regolari: principali proprietà e Pumping Lemma. (4h)
• Grammatiche libere dal contesto: derivazioni, alberi sintattici, grammatiche ambigue. Struttura di un parser (6h)
• 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. (4h)
• Linguaggi liberi dal contesto: principali proprietà e Pumping Lemma. (4h)
• La gerarchia di Chomsky. (2h)
• Macchine di Turing deterministiche e non-deterministiche (4h).
• Linguaggi ricorsivamente enumerabili e problemi indecidibili. (6h)

Il corso si articola in lezioni frontali (40 ore) ed esercitazioni (12 ore). Gli argomenti presentati a lezione sono applicati nelle esercitazioni in aula che prevedono la partecipazione attiva degli studenti. Gli esercizi presentati costituiscono una fondamentale linea guida per la preparazione dell’esame.

L’obiettivo della prova d’esame è l'accertamento dell’acquisizione delle conoscenze e delle abilità descritte nella sezione “Obiettivi del corso”, valutando il livello di conoscenza e la capacità di applicare le nozioni e le tecniche dimostrative viste a lezione.

L’esame consiste in una prova scritta articolata secondo il seguente schema: (parte A) due domande relative alla presentazione e applicazione delle nozioni presentate nell’insegnamento; (parte B) dimostrazione di uno dei teoremi presentati a lezione; (parte C) cinque esercizi sullo schema di quelli presentati a lezione.

L’attribuzione del voto finale sarà determinata per il 30% dalla conoscenza delle definizioni e dalla capacità di applicarle (parte A), pre il 20% dalla conoscenza e comprensione delle dimostrazioni dei teoremi (parte B), per il 50% dalla capacità di applicare le nozioni apprese nel corso alla soluzione degli esercizi (parte C).

Il voto finale è espresso in trentesimi.

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Automi, linguaggi e calcolabilità, Pearson Paravia Bruno Mondadori, Terza Edizione, 2009.

Le slide delle lezioni in formato PDF sono messe a disposizione sulla piattaforma e-learning di Ateneo ove sono disponibili anche il testo dei problemi visti durante le esercitazioni e le soluzioni proposte.

Il docente riceve su appuntamento, previa richiesta via e-mail a mauro.ferrari@uninsubria.it. Il docente risponde solo alle e-mail firmate e provenienti dal dominio studenti.uninsubria.it.

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. 2019/2020

Anno di corso: 3
Curriculum: PERCORSO COMUNE

A.A. 2018/2019

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

Anno di corso: 3
Curriculum: PERCORSO COMUNE

A.A. 2013/2014

Anno di corso: 3
Curriculum: PERCORSO COMUNE