Automi e Linguaggi
Anno Accademico: 2022-2023 - Docente: Marco Cesati - Tutor: Sara Da Canal
Insegnamenti da 6 CFU dell'ordinamento DM270/2004
Secondo anno del corso di Laurea in Ingegneria Informatica
AUTOMI E LINGUAGGI (6 CFU) è un insegnamento di base obbligatorio del secondo anno della laurea in Ingegneria Informatica (triennale).
Per gli studenti immatricolati in anni accademici precedenti al 2018-2019 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.
Svolgimento
6 marzo 2023 - 17 giugno 2023
(secondo semestre)
Obiettivo dell'insegnamento
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à.
Programma sintetico
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 NL-completi.
Pre-requisiti
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 2022/23.
Informazioni generali sull'insegnamento
Iscrizione
Per poter sostenere le prove di verifica e di esame è necessario iscriversi all'insegnamento entro il 17 giugno 2023.
Non sarà accolto alcun reclamo relativo alla (mancata) iscrizione all'insegnamento dopo il 17 giugno 2023.
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.
Sistema di gestione online dell'insegnamento
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 2022/23) 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).
ATTENZIONE!
- Non è possibile registrarsi su GOCU con indirizzi di posta elettronica di tipo "@students.uniroma2.eu", perché il relativo server rifiuta sistematicamente tutti i messaggi spediti da GOCU
- Talvolta i messaggi di posta elettronica provenienti da GOCU sono identificati come "spam" e finiscono quindi automaticamente in una cartella diversa dalla "inbox", oppure sono semplicemente cancellati. Apparentemente questo si verifica più frequentemente con il provider "hotmail"
- La procedura di registrazione richiede la ricezione di un codice di conferma da parte del sistema GOCU via posta elettronica: se lo studente non inserisce il codice di controllo ricevuto su GOCU entro 24 ore dall'iscrizione, il sistema considera l'iscrizione non avvenuta e cancella completamente i dati immessi dallo studente.