Automi e Linguaggi

Anno Accademico: 2021-2022 - Docente: Marco Cesati

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

28 febbraio 2022 - 11 giugno 2022

(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 EXP-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 2021/22.

Informazioni generali sull'insegnamento

Iscrizione

Per poter sostenere le prove di verifica e di esame è necessario iscriversi all'insegnamento entro il 30 giugno 2022.

Non sarà accolto alcun reclamo relativo alla (mancata) iscrizione all'insegnamento dopo il 30 giugno 2022.

Studenti già iscritti in precedenti anni accademici devono comunque iscriversi all'insegnamento per questo anno accademico.

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 2021/22) necessario per accedere all'area studenti.

Il sistema:

  • permette di prenotarsi alle prove di esame ed invia un'email di conferma,

  • 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.