Clelia DE FELICE | ELEMENTI DI TEORIA DELLA COMPUTAZIONE
Clelia DE FELICE ELEMENTI DI TEORIA DELLA COMPUTAZIONE
cod. 0512100018
ELEMENTI DI TEORIA DELLA COMPUTAZIONE
| 0512100018 | |
| DIPARTIMENTO DI INFORMATICA | |
| CORSO DI LAUREA | |
| INFORMATICA | |
| 2016/2017 |
| OBBLIGATORIO | |
| ANNO CORSO 3 | |
| ANNO ORDINAMENTO 2008 | |
| SECONDO SEMESTRE |
| SSD | CFU | ORE | ATTIVITÀ | |
|---|---|---|---|---|
| INF/01 | 9 | 72 | LEZIONE |
| Obiettivi | |
|---|---|
| CONOSCENZA E CAPACITÀ DI COMPRENSIONE: A) MODELLO ASTRATTO DI COMPUTAZIONE B) MACCHINA DI TURING C) DISTINZIONE TRA I CONCETTI DI COMPUTABILE E NON COMPUTABILE D) COMPLESSITÀ DI TEMPO E) DISTINZIONE TRA PROBLEMA TRATTABILE E INTRATTABILE. CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE: ANALIZZARE IL COMPORTAMENTO DI AUTOMI FINITI E MACCHINE DI TURING. PROGETTARE SEMPLICI MODELLI DI COMPUTAZIONE PER LA SOLUZIONE DI PROBLEMI DI DECISIONE (PROBLEMI CON RISPOSTA SI/NO). |
| Prerequisiti | |
|---|---|
| A)MATEMATICA DISCRETA: INSIEMI, OPERAZIONI SU INSIEMI, CARDINALITÀ, PRODOTTO CARTESIANO, FUNZIONI. B)LOGICA: PREDICATI E QUANTIFICATORI. METODI E STRATEGIE DI DIMOSTRAZIONE. C)ALGORITMI: NOTAZIONI ASINTOTICHE. |
| Contenuti | |
|---|---|
| - MODELLI DI COMPUTAZIONE: AUTOMI FINITI DETERMINISTICI E NON DETERMINISTICI. ESPRESSIONI REGOLARI. PROPRIETÀ DI CHIUSURA DEI LINGUAGGI REGOLARI. TEOREMA DI KLEENE. PUMPING LEMMA PER I LINGUAGGI REGOLARI. MACCHINA DI TURING DETERMINISTICA A NASTRO SINGOLO. IL LINGUAGGIO RICONOSCIUTO DA UNA MACCHINA DI TURING. VARIANTI DI MACCHINE DI TURING E LORO EQUIVALENZA. - IL CONCETTO DI COMPUTABILITÀ: FUNZIONI CALCOLABILI, LINGUAGGI DECIDIBILI E LINGUAGGI TURING RICONOSCIBILI. PROBLEMI DECIDIBILI RELATIVI AI LINGUAGGI REGOLARI. LINGUAGGI INDECIDIBILI. IL PROBLEMA DELLA FERMATA. RIDUZIONI, TEOREMA DI RICE. - IL CONCETTO DI COMPLESSITÀ: MISURE DI COMPLESSITÀ: COMPLESSITÀ IN TEMPO DETERMINISTICO E NON DETERMINISTICO. RELAZIONI DI COMPLESSITÀ TRA VARIANTI DI MACCHINE DI TURING. LA CLASSE P. LA CLASSE NP. RIDUCIBILITÀ IN TEMPO POLINOMIALE. DEFINIZIONE DI NP-COMPLETEZZA. - RIDUZIONI POLINOMIALI. ESEMPI DI LINGUAGGI NP-COMPLETI. SAT, 3-SAT, CLIQUE, VERTEX-COVER, HAMPATH, UHAMPATH, SUBSET-SUM. |
| 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 | |
|---|---|
| LA VERIFICA DELL’APPRENDIMENTO DEI CONCETTI DI BASE PREVISTI DALL’INSEGNAMENTO ED ELENCATI NELLA SEZIONE “CONTENUTI DEL CORSO” E DELLA CAPACITÀ DI APPLICARE TALI CONCETTI COME DESCRITTO NELLA SEZIONE “OBIETTIVI”, AVVERRÀ IN DUE FASI. LA PRIMA PREVEDE UNA PROVA SCRITTA DI DUE ORE. LA PROVA SCRITTA CONSISTE DI DOMANDE SU ARGOMENTI DEL CORSO ED ESERCIZI LA CUI SOLUZIONE PREVEDE L’APPLICAZIONE DI TALI ARGOMENTI. IN CASO DI SUPERAMENTO DELLA PROVA SCRITTA, LO STUDENTE AFFRONTERÀ UN COLLOQUIO ORALE TESO A COMPLETARE LA VERIFICA DA PARTE DEL DOCENTE DELL’APPRENDIMENTO DEGLI ARGOMENTI DEL PROGRAMMA. |
| Testi | |
|---|---|
| 1.M. SIPSER, INTRODUZIONE ALLA TEORIA DELLA COMPUTAZIONE, MAGGIOLI EDITORE, 2016. 2. J. HOPCROFT, R. MOTWANI, J. ULLMAN, AUTOMI, LINGUAGGI E CALCOLABILITÀ, ADDISON WESLEY PEARSON EDUCATION ITALIA S.R.L, TERZA EDIZIONE, 2009. |
| Altre Informazioni | |
|---|---|
| IL PROGRAMMA DETTAGLIATO E ULTERIORI INFORMAZIONI SONO PRESENTI ALLA PAGINA HTTP://WWW.UNISA.IT/DIPARTIMENTI/DIP_INFORMATICA/DIDATTICA/DOCENTI/DEFELICE/INDEX |
BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2019-03-11]
