ID:
SCV0327
Durata (ore):
52
CFU:
6
SSD:
INFORMATICA
Sede:
Varese - Università degli Studi dell'Insubria
Anno:
2025
Dati Generali
Periodo di attività
Primo Semestre (22/09/2025 - 19/12/2025)
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’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 scritto ha lo scopo di verificare l’acquisizione delle conoscenze oggetto dell’insegnamento e la capacità si applicarle per risolvere semplici problemi. La prova scritta dura 110 minuti ed è 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 descriverle con il linguaggio appropriato (parte A), per 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.
L’esame scritto ha lo scopo di verificare l’acquisizione delle conoscenze oggetto dell’insegnamento e la capacità si applicarle per risolvere semplici problemi. La prova scritta dura 110 minuti ed è 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 descriverle con il linguaggio appropriato (parte A), per 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.
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