AUTOMI E LINGUAGGI FORMALI

Informatica AUTOMI E LINGUAGGI FORMALI

0522500142
DIPARTIMENTO DI INFORMATICA
CORSO DI LAUREA MAGISTRALE
INFORMATICA
2021/2022



ANNO CORSO 1
ANNO ORDINAMENTO 2016
PRIMO SEMESTRE
CFUOREATTIVITÀ
1AUTOMI E LINGUAGGI FORMALI
324LEZIONE
2AUTOMI E LINGUAGGI FORMALI
324LEZIONE
Obiettivi
CONOSCENZA E CAPACITÀ DI COMPRENSIONE.
LO STUDENTE DOVRÀ AVERE CONOSCENZA DI MODELLI DI COMPUTAZIONE E MECCANISMI GENERATIVI. DELLE POTENZIALITÀ, LIMITI, ASPETTI MATEMATICI E CAMPI DI APPLICAZIONE DI TALI MODELLI.

CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE.
LO STUDENTE DOVRÀ AVERE CAPACITÀ
•DI RICONOSCERE I PROBLEMI CHE POSSONO ESSERE RISOLTI UTILIZZANDO SOLUZIONI BASATE SUI MODELLI DI CALCOLO STUDIATI.
•DI STUDIARE PROBLEMI APERTI DELLA TEORIA DEI LINGUAGGI FORMALI UTILIZZANDO LE CONOSCENZE ACQUISITE.

Prerequisiti
MATEMATICA DISCRETA: INSIEMI, OPERAZIONI SU INSIEMI, CARDINALITÀ, PRODOTTO CARTESIANO, FUNZIONI.

LOGICA: PREDICATI E QUANTIFICATORI. METODI E STRATEGIE DI DIMOSTRAZIONE.

ALGORITMI: NOTAZIONI ASINTOTICHE
Contenuti
AUTOMI FINITI DETERMINISTICI E NON DETERMINISTICI. ESPRESSIONI E LINGUAGGI REGOLARI. PROBLEMI DI DECISIONE PER I LINGUAGGI REGOLARI. EQUIVALENZA E MINIMIZZAZIONE DI AUTOMI. GRAMMATICHE REGOLARI.

GRAMMATICHE E LINGUAGGI LIBERI DAL CONTESTO. ALBERI SINTATTICI. AUTOMI A PILA. PROBLEMI DI DECISIONE PER I LINGUAGGI LIBERI DAL CONTESTO.

MACCHINE DI TURING. DECIDIBILITÀ.

GERARCHIA DI CHOMSKY.

CENNI DI TEORIA DEI CODICI E DELLA COMBINATORIA DELLE PAROLE.
Metodi Didattici
LEZIONI FRONTALI TESE A TRASFERIRE I CONCETTI ELENCATI NELLA SEZIONE “CONTENUTI DEL CORSO”. LE LEZIONI SONO COMPRENSIVE DI ESERCITAZIONI IN CUI VERRANNO PRESENTATI ESEMPI DI APPLICAZIONI DI TALI CONCETTI, ALLO SCOPO DI RENDERE LO STUDENTE IN GRADO DI APPLICARE LA CONOSCENZA ACQUISITA.
Verifica dell'apprendimento
L'ESAME PREVEDE UNA PROVA ORALE. LA PROVA ORALE CONSISTE DI DOMANDE SU ARGOMENTI DEL CORSO ED ESERCIZI LA CUI SOLUZIONE PREVEDE L’APPLICAZIONE DI TALI ARGOMENTI. PARTE DELLA PROVA ORALE POTRÀ ESSERE SOSTITUITA DA UN SEMINARIO O UNA DISSERTAZIONE SCRITTA SU ARTICOLI SCIENTIFICI RELATIVI AD ARGOMENTI AVANZATI.

LA PROVA È TESA A VALUTARE IL LIVELLO DELLE CONOSCENZE TEORICHE E DELLA CAPACITÀ DI APPLICARE TALI CONOSCENZE, L’AUTONOMIA DI ANALISI E GIUDIZIO, NONCHÉ LE CAPACITÀ ESPOSITIVE DELL’ALLIEVO.

IL LIVELLO DI VALUTAZIONE DELLE PROVE TIENE CONTO DELLA CORRETTEZZA DEI METODI UTILIZZATI, DELLA COMPLETEZZA ED ESATTEZZA DELLE RISPOSTE, NONCHÉ DELLA CHIAREZZA NELLA PRESENTAZIONE.

IL LIVELLO DI VALUTAZIONE MINIMO (18) È ATTRIBUITO QUANDO LO STUDENTE DIMOSTRA INCERTEZZE NELL’APPLICAZIONE DEI METODI STUDIATI E HA UNA LIMITATA CONOSCENZA DEI MODELLI DI COMPUTAZIONE PRESENTATI.

IL LIVELLO MASSIMO (30) È ATTRIBUITO QUANDO LO STUDENTE DIMOSTRA UNA CONOSCENZA COMPLETA E APPROFONDITA DEI CONCETTI E DEI METODI STUDIATI. INOLTRE È IN GRADO DI RISOLVERE I PROBLEMI PROPOSTI E MOSTRA CAPACITÀ DI COLLEGARE TRA LORO CONCETTI DIVERSI.

LA LODE È ATTRIBUITA QUANDO IL CANDIDATO DIMOSTRA SIGNIFICATIVA PADRONANZA DEI CONTENUTI TEORICI E MOSTRA DI SAPER PRESENTARE GLI ARGOMENTI CON NOTEVOLE PROPRIETÀ DI LINGUAGGIO E CAPACITÀ DI ELABORAZIONE AUTONOMA.
Testi
•M. SIPSER, INTRODUZIONE ALLA TEORIA DELLA COMPUTAZIONE, APOGEO, 2016
•J. HOPCROFT, R. MOTWANI, J. ULLMAN, AUTOMI, LINGUAGGI E CALCOLABILITÀ, ADDISON WESLEY PEARSON EDUCATION ITALIA S.R.L, TERZA EDIZIONE, 2009.
Altre Informazioni
SITO WEB DELLA PIATTAFORMA E-LEARNING
HTTP://ELEARNING.INFORMATICA.UNISA.IT/EL-PLATFORM/

CONTATTI :
CDEFELICE@UNISA.IT
HTTPS://DOCENTI.UNISA.IT/001119/HOME

  BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2022-06-15]