ID:
SCV0327
Durata (ore):
52
CFU:
6
SSD:
INFORMATICA
Sede:
Como - Università degli Studi dell'Insubria
Anno:
2024
Dati Generali
Periodo di attività
Primo Semestre (23/09/2024 - 20/12/2024)
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. Tali conoscenze sono rivolte a formare e ad aumentare le capacità di astrazione e di formalizzazione, 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:
• avere nozioni di base su stringhe e linguaggi formali (sul monoide libero generato da un alfabeto finito)
• descrivere i principali modelli ad automi per il riconoscimento di classi di linguaggi (automi a stati finiti, automi a pila, macchine di Turing)
• descrivere sistemi di riscrittura/grammatiche alla Chomsky per il riconoscimento di classi di linguaggi
• avere chiara la relazione tra automi a stati finiti, Macchine di Turing e le nozioni base della programmazione sequenziale
• avere chiara la relazione tra automi a stati finiti, e formalizzazione di sistemi discreti sequenziali
• 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;
• applicare in modo appropriato riconoscitori e generatori allo studio di semplici linguaggi;
• riconoscere e utilizzare la terminologia propria della teoria degli automi, dei linguaggi formali e della teoria della computabilità.
Al termine del corso lo studente sarà in grado di:
• avere nozioni di base su stringhe e linguaggi formali (sul monoide libero generato da un alfabeto finito)
• descrivere i principali modelli ad automi per il riconoscimento di classi di linguaggi (automi a stati finiti, automi a pila, macchine di Turing)
• descrivere sistemi di riscrittura/grammatiche alla Chomsky per il riconoscimento di classi di linguaggi
• avere chiara la relazione tra automi a stati finiti, Macchine di Turing e le nozioni base della programmazione sequenziale
• avere chiara la relazione tra automi a stati finiti, e formalizzazione di sistemi discreti sequenziali
• 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;
• applicare in modo appropriato riconoscitori e generatori allo studio di semplici linguaggi;
• 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 e le tecniche dimostrative impartite negli insegnamenti fondamentali di Algebra e Geometria, Programmazione e Algoritmi e Strutture Dati del primo anno di corso, che dunque costituiscono propedeuticità fortemente consigliata.
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 (orale) ha lo scopo di verificare l’acquisizione delle conoscenze oggetto dell’insegnamento e la capacità si applicarle per risolvere semplici problemi. La prova orale è 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) esercizi sullo schema di quelli presentati a lezione.
L’attribuzione del voto finale sarà determinata per il 50% 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 30% dalla capacità di applicare le nozioni apprese nel corso alla soluzione degli esercizi (parte C).
Il voto finale è espresso in trentesimi.
L’esame (orale) ha lo scopo di verificare l’acquisizione delle conoscenze oggetto dell’insegnamento e la capacità si applicarle per risolvere semplici problemi. La prova orale è 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) esercizi sullo schema di quelli presentati a lezione.
L’attribuzione del voto finale sarà determinata per il 50% 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 30% 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)
• Stringhe, linguaggi e loro descrizione finita. (2h)
• Automi a stati finiti deterministici (DFA), automi a stati finiti non-deterministici (NFA), automi a stati finiti con ε-mosse (ε-NFA). Equivalenza fra DFA, NFA, (ε-NFA). (12h)
• Esempi di applicazione. (2h)
• Composizionalità e Teorema di Kleene. (4h)
• Linguaggi regolari: principali proprietà e Pumping Lemma. (4h)
• Grammatiche libere dal contesto: derivazioni, alberi sintattici, grammatiche ambigue. Struttura di un parser (8h)
• 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 (2h).
• Linguaggi ricorsivamente enumerabili e problemi indecidibili. (4h)
Prodotto di automi e modelli non sequenziali (4h)
• Stringhe, linguaggi e loro descrizione finita. (2h)
• Automi a stati finiti deterministici (DFA), automi a stati finiti non-deterministici (NFA), automi a stati finiti con ε-mosse (ε-NFA). Equivalenza fra DFA, NFA, (ε-NFA). (12h)
• Esempi di applicazione. (2h)
• Composizionalità e Teorema di Kleene. (4h)
• Linguaggi regolari: principali proprietà e Pumping Lemma. (4h)
• Grammatiche libere dal contesto: derivazioni, alberi sintattici, grammatiche ambigue. Struttura di un parser (8h)
• 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 (2h).
• Linguaggi ricorsivamente enumerabili e problemi indecidibili. (4h)
Prodotto di automi e modelli non sequenziali (4h)
Lingua Insegnamento
Italiano
Altre informazioni
La docente riceve su appuntamento, anche via Teams, previa richiesta via e-mail a nicoletta.sabadini@uninsubria.it. La docente risponde solo alle e-mail firmate e provenienti dal dominio studenti.uninsubria.it.
Sono disponibili tesi su argomenti attinenti.
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Automi, linguaggi e calcolabilità, Pearson Paravia Bruno Mondadori, Terza Edizione, 2009.
A. Bertoni, B. Palano, Linguaggi formali e automi, http://bertoni.di.unimi.it/Linguaggi_e_Automi.pdf
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.
Sono disponibili tesi su argomenti attinenti.
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Automi, linguaggi e calcolabilità, Pearson Paravia Bruno Mondadori, Terza Edizione, 2009.
A. Bertoni, B. Palano, Linguaggi formali e automi, http://bertoni.di.unimi.it/Linguaggi_e_Automi.pdf
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.
Corsi
Corsi
INFORMATICA
Laurea
3 anni
No Results Found
Persone
Persone
No Results Found