AUTOMI E LINGUAGGI (6 CFU) è un insegnamento di base obbligatorio del terzo anno della laurea in Ingegneria Informatica (triennale).
Negli anni accademici precedenti all'A.A. 2023/24 AUTOMI E LINGUAGGI era un insegnamento obbligatorio del secondo anno della laurea triennale. Pertanto, le prove di esame di questo insegnamento in questo anno accademico 2024/25 potranno essere sostenute esclusivamente dagli studenti iscritti al terzo anno della laurea triennale in ingegneria informatica, a meno che
lo studente si è immatricolato nell'A.A. 2022/23 o precedente, oppure
lo studente ha un piano di studi individuale approvato dal quale risulti l'anticipazione dell'insegnamento.
Per gli studenti immatricolati in anni accademici precedenti al 2018/19 AUTOMI E LINGUAGGI è inserito in un gruppo di tre insegnamenti a scelta, insieme a SISTEMI OPERATIVI e a MOBILE PROGRAMMING: ogni studente deve sostenere almeno due esami scelti liberamente da questi tre insegnamenti.
3 marzo 2025 - 14 giugno 2025
(secondo semestre)
L'insegnamento intende fornire una visione introduttiva dell'Informatica Teorica. "Con l'espressione informatica teorica ci si riferisce a un complesso di discipline scientifiche aventi per oggetto lo studio formale degli strumenti, dei metodi e dei processi per la rappresentazione dell'informazione e per la sua elaborazione. Come accade per altre discipline tecnico-scientifiche, anche nel caso dell'informatica esiste un insieme di concetti, di principi, di proprietà logico-matematiche che ne costituiscono il fondamento teorico. Su tale fondamento si basano i progettisti per realizzare modelli formali di sistemi e processi di calcolo, per progettare nuovi strumenti informatici e nuove applicazioni e per analizarne e certificarne le prestazioni." (dalla voce Informatica Teorica nell'Enciclopedia Treccani della Scienza e della Tecnica, 2007). In pratica, AUTOMI E LINGUAGGI fornisce i rudimenti di teoria dei linguaggi, teoria della computabilità e teoria della complessità.
TEORIA DEI LINGUAGGI: Linguaggi regolari e automi finiti deterministici e non deterministici. Espressioni regolari e loro equivalenza con gli automi finiti. Pumping lemma per i linguaggi regolari. Chiusura dei linguaggi regolari rispetto a vari operatori. Linguaggi "context-free" e loro grammatiche. Automi pushdown non deterministici e loro equivalenza con le grammatiche "context-free". Pumping lemma per i linguaggi "context-free". Automi pushdown deterministici, linguaggi "context-free" deterministici e loro proprietà. Grammatiche LR(k), LR(1), LR(0). Il parser di Earley per grammatiche "context-free".
TEORIA DELLA COMPUTABILITÀ: Macchine di Turing. Linguaggi ricorsivamente enumerabili linguaggi ricorsivi. Varianti di macchine di Turing e loro equivalenza. Macchine di Turing non deterministiche. Enumeratori. Definizione di algoritmo e tesi di Church-Turing. Problemi decidibili e indecidibili. Il metodo di diagonalizzazione. Esempi di linguaggi non decidibili. Macchina di Turing universale. Riduzione tra linguaggi. Il problema PCP (Post Correspondence Problem). Riducibilità many-one. Funzioni calcolabili. Teorema di Rice. Teorema della ricorsione. Sistemi formali, modelli e teorie dei modelli. Decidibilità di teorie logiche. Riducibilità di Turing e macchine di Turing ad oracolo. Complessità di Kolmogorov.
TEORIA DELLA COMPLESSITÀ: Complessità temporale. La classe P. La classe NP. Esempi di problemi in P ed in NP. La classe co-NP. La classe EXPTIME. NP-hardness e NP-completezza. Il problema di soddisfacibilità SAT. Teorema di Cook-Levin. Esempi di problemi NP-completi: SAT, 3SAT, CLIQUE, VERTEX COVER, HAMPATH, UHAMPATH, SUBSET SUM. Complessità spaziale. Il teorema di Savitch. Problemi PSPACE-completi e NL-completi.
Gli insegnamenti sono progettati per gli studenti del secondo anno del corso di Laurea in Ingegneria Informatica.
Affinché le prove d'esame siano legalmente valide l'insegnamento deve essere inserito nel piano di studi valido per l'Anno Accademico 2024/25. ATTENZIONE: gli studenti immatricolati nell'A.A. 2023/24 e successivi non possono sostenere nell'anno accademico corrente l'esame di questo insegnamento (a meno che non sia previsto esplicitamente nel piano di studi individuale approvato per lo studente).
Per poter sostenere le prove di verifica e di esame è necessario iscriversi all'insegnamento entro il 15 giugno 2025.
Non sarà accolto alcun reclamo relativo alla (mancata) iscrizione all'insegnamento dopo il 15 giugno 2025.
Studenti già iscritti in precedenti anni accademici devono comunque iscriversi all'insegnamento per questo anno accademico.
Studenti non iscritti potranno comunque partecipare alle prove d'esame, ma non potranno usufruire dei servizi offerti dalla piattaforma GOCU. In particolare non potranno ricevere via posta elettronica avvisi e risultati delle prove d'esame.
Questo insegnamento fa uso di un sistema software (G.O.C.U.) per la gestione delle iscrizioni all'insegnamento e delle prove di esame.
Si deve accedere alla piattaforma GOCU per iscriversi all'insegnamento (è necessario indicare un indirizzo email valido, vedi la sezione sulle 'regole' in GOCU) e per prenotarsi alle prove d'esame. Al termine della procedura di iscrizione si ottiene il proprio codice studente (valido per l'anno accademico 2024/25) necessario per accedere all'area studenti.
Il sistema:
invia un'email con l'esito della prova non appena il docente pubblica i risultati,
riassume l'esito di tutte le prove di esame sostenute,
se necessario calcola la media delle prove e mostra un eventuale voto utile alla verbalizzazione,
permette di richiedere un nuovo invio del vostro codice studente (ad esempio in caso di smarrimento).