ID:
SCV0327
Durata (ore):
52
CFU:
6
SSD:
INFORMATICA
Sede:
Varese - Università degli Studi dell'Insubria
Anno:
2026
Dati Generali
Periodo di attività
Primo Semestre (21/09/2026 - 23/12/2026)
Syllabus
Obiettivi Formativi
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 le capacità di astrazione attraverso la rappresentazione simbolica e di comprensione di un linguaggio scientifico astratto e simbolico, capacità 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.
Al termine del corso lo studente sarà in grado di.
(1) descrivere i principali modelli computazionali (automi a stati finiti, automi a pila, macchine di Turing), le loro caratteristiche e la loro potenza computazionale in termini di linguaggi riconosciuti;
(2) definire formalmente la nozione di computazione nei vari modelli studiati;
(3) identificare il ruolo dei vari linguaggi (in particolare per i linguaggi regolari e context-free) nel processo di compilazione dei linguaggi di programmazione e in altre applicazioni di base dei linguaggi;
(4) identificare e utilizzare le notazioni (generatori) per la descrizione dei linguaggi regolari e i linguaggi context-free;
(5) applicare in modo appropriato riconoscitori e generatori allo studio di semplici linguaggi;
(6) dimostrare un’appropriata comprensione dei limiti dei vari modelli computazionali;
(7) riconoscere e utilizzare la terminologia propria della teoria degli automi, dei linguaggi formali e della teoria della computabilità.
limitativi nell'ambito della teoria della calcolabilità. Tali conoscenze sono rivolte a formare e ad aumentare le capacità di astrazione attraverso la rappresentazione simbolica e di comprensione di un linguaggio scientifico astratto e simbolico, capacità 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.
Al termine del corso lo studente sarà in grado di.
(1) descrivere i principali modelli computazionali (automi a stati finiti, automi a pila, macchine di Turing), le loro caratteristiche e la loro potenza computazionale in termini di linguaggi riconosciuti;
(2) definire formalmente la nozione di computazione nei vari modelli studiati;
(3) identificare il ruolo dei vari linguaggi (in particolare per i linguaggi regolari e context-free) nel processo di compilazione dei linguaggi di programmazione e in altre applicazioni di base dei linguaggi;
(4) identificare e utilizzare le notazioni (generatori) per la descrizione dei linguaggi regolari e i linguaggi context-free;
(5) applicare in modo appropriato riconoscitori e generatori allo studio di semplici linguaggi;
(6) dimostrare un’appropriata comprensione dei limiti dei vari modelli computazionali;
(7) riconoscere e utilizzare la terminologia propria della teoria degli automi, dei linguaggi formali e della teoria della computabilità.
Prerequisiti
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.
Metodi didattici
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.
Verifica Apprendimento
L’esame consiste unicamente in una prova scritta. La prova scritta, della durata di 110 minuti, ha l’obiettivo di accertare l’acquisizione delle conoscenze e delle abilità descritte nella sezione “Obiettivi del corso”, valutando sia la comprensione delle nozioni teoriche sia la capacità di applicare le tecniche dimostrative e gli strumenti presentati a lezione alla risoluzione di semplici problemi.
La prova è articolata secondo il seguente schema:
parte A: due domande relative alla presentazione e all’applicazione delle nozioni introdotte nell’insegnamento;
parte B: dimostrazione di uno dei teoremi presentati a lezione;
parte C: cinque esercizi sul modello di quelli svolti durante il corso.
Ciascuna domanda della parte A è valutata fino a un massimo di 3 punti; la dimostrazione della parte B e ciascun esercizio della parte C sono valutati fino a un massimo di 4 punti. Il punteggio complessivo massimo della prova è pari a 30 punti.
Il voto finale è espresso in trentesimi. La lode può essere attribuita agli studenti che conseguano il punteggio massimo nella prova e che dimostrino piena padronanza degli argomenti, rigore nell’esposizione e nelle dimostrazioni, correttezza completa nello svolgimento degli esercizi e capacità di utilizzare in modo autonomo e consapevole le tecniche apprese durante il corso.
La prova è articolata secondo il seguente schema:
parte A: due domande relative alla presentazione e all’applicazione delle nozioni introdotte nell’insegnamento;
parte B: dimostrazione di uno dei teoremi presentati a lezione;
parte C: cinque esercizi sul modello di quelli svolti durante il corso.
Ciascuna domanda della parte A è valutata fino a un massimo di 3 punti; la dimostrazione della parte B e ciascun esercizio della parte C sono valutati fino a un massimo di 4 punti. Il punteggio complessivo massimo della prova è pari a 30 punti.
Il voto finale è espresso in trentesimi. La lode può essere attribuita agli studenti che conseguano il punteggio massimo nella prova e che dimostrino piena padronanza degli argomenti, rigore nell’esposizione e nelle dimostrazioni, correttezza completa nello svolgimento degli esercizi e capacità di utilizzare in modo autonomo e consapevole le tecniche apprese durante il corso.
Contenuti
• Prerequisiti matematici. (4h)
• Automi a stati finiti deterministici (DFA), automi a stati finiti non-deterministici (NFA). Equivalenza fra DFA, NFA. (10h, obiettivi 1,2,7)
• Automi a stati finiti con ε-mosse (ε-NFA). Equivalenza fra NFA e ε-NFA. (4h, obiettivi 1,5,6)
• Espressioni regolari. Equivalenza fra espressioni regolari e ε-NFA. (4h, obiettivi 1,5)
• Linguaggi regolari: principali proprietà e Pumping Lemma. (4h, obiettivi 5,6)
• Grammatiche libere dal contesto: derivazioni, alberi sintattici, grammatiche ambigue. Struttura di un parser (6h, obiettivi 3,4,5)
• 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, obiettivi 1, 3, 5, 7)
• Linguaggi liberi dal contesto: principali proprietà e Pumping Lemma. (4h, obiettivi 1,5,7)
• La gerarchia di Chomsky. (2h, obiettivi 4, 7)
• Macchine di Turing deterministiche e non-deterministiche (4h, obiettivo 1, 3).
• Linguaggi ricorsivamente enumerabili e problemi indecidibili. (6h, obiettivo 1, 6, 7)
• Automi a stati finiti deterministici (DFA), automi a stati finiti non-deterministici (NFA). Equivalenza fra DFA, NFA. (10h, obiettivi 1,2,7)
• Automi a stati finiti con ε-mosse (ε-NFA). Equivalenza fra NFA e ε-NFA. (4h, obiettivi 1,5,6)
• Espressioni regolari. Equivalenza fra espressioni regolari e ε-NFA. (4h, obiettivi 1,5)
• Linguaggi regolari: principali proprietà e Pumping Lemma. (4h, obiettivi 5,6)
• Grammatiche libere dal contesto: derivazioni, alberi sintattici, grammatiche ambigue. Struttura di un parser (6h, obiettivi 3,4,5)
• 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, obiettivi 1, 3, 5, 7)
• Linguaggi liberi dal contesto: principali proprietà e Pumping Lemma. (4h, obiettivi 1,5,7)
• La gerarchia di Chomsky. (2h, obiettivi 4, 7)
• Macchine di Turing deterministiche e non-deterministiche (4h, obiettivo 1, 3).
• Linguaggi ricorsivamente enumerabili e problemi indecidibili. (6h, obiettivo 1, 6, 7)
Lingua Insegnamento
ITALIANO
Altre informazioni
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.
Corsi
Corsi
INFORMATICA
Laurea
3 anni
No Results Found
Persone
Persone
Docenti di ruolo di Ia fascia
No Results Found