Gianluca DE MARCO | ELEMENTI DI TEORIA DELLA COMPUTAZIONE
Gianluca DE MARCO ELEMENTI DI TEORIA DELLA COMPUTAZIONE
cod. 0512100018
ELEMENTI DI TEORIA DELLA COMPUTAZIONE
| 0512100018 | |
| DIPARTIMENTO DI INFORMATICA | |
| CORSO DI LAUREA | |
| INFORMATICA | |
| 2022/2023 |
| OBBLIGATORIO | |
| ANNO CORSO 3 | |
| ANNO ORDINAMENTO 2017 | |
| SECONDO SEMESTRE |
| SSD | CFU | ORE | ATTIVITÀ | |
|---|---|---|---|---|
| INF/01 | 9 | 72 | LEZIONE |
| Obiettivi | |
|---|---|
| CONOSCENZA E CAPACITÀ DI COMPRENSIONE OBIETTIVO DELL'INSEGNAMENTO È L’ACQUISIZIONE DA PARTE DELLO STUDENTE: •DEL CONCETTO DI MODELLO ASTRATTO DI COMPUTAZIONE •DELLA DISTINZIONE TRA I CONCETTI DI COMPUTABILE E NON COMPUTABILE •DEL CONCETTO DI COMPLESSITÀ E DELLA 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 SÌ/NO). |
| Prerequisiti | |
|---|---|
| •MATEMATICA DISCRETA: INSIEMI, OPERAZIONI SU INSIEMI, CARDINALITÀ, PRODOTTO CARTESIANO, FUNZIONI •LOGICA: PREDICATI E QUANTIFICATORI. METODI E STRATEGIE DI DIMOSTRAZIONE •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 (24 ORE FRONTALI) 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. LINGUAGGI DECIDIBILI E LINGUAGGI INDECIDIBILI. IL PROBLEMA DELLA FERMATA. RIDUZIONI, TEOREMA DI RICE. (24 ORE FRONTALI) 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 (24 ORE FRONTALI). |
| 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 LO SVOLGIMENTO DI UNA PROVA SCRITTA DI DUE ORE. LA PROVA SCRITTA POTRÀ ESSERE SOSTITUITA DAL SUPERAMENTO DI DUE PROVE INTERCORSO. LA PROVA SCRITTA CONSISTE DI DOMANDE SU ARGOMENTI DEL CORSO ED ESERCIZI LA CUI SOLUZIONE PREVEDE L’APPLICAZIONE DI TALI ARGOMENTI. 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 E DELLA COMPLESSITÀ COMPUTAZIONALE. IL LIVELLO MASSIMO (30) È ATTRIBUITO QUANDO LO STUDENTE DIMOSTRA UNA CONOSCENZA COMPLETA E APPROFONDITA DEI CONCETTI E DEI METODI DELLA TEORIA DELLA COMPUTAZIONE. INOLTRE È IN GRADO DI RISOLVERE I PROBLEMI PROPOSTI PERVENENDO IN MODO EFFICIENTE ED ACCURATO ALLA SOLUZIONE E MOSTRA CAPACITÀ DI COLLEGARE TRA LORO CONCETTI DIVERSI. LA LODE È ATTRIBUITA QUANDO IL CANDIDATO DIMOSTRA SIGNIFICATIVA PADRONANZA DEI CONTENUTI TEORICI ED OPERATIVI 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. KLEINBERG, E. TARDOS, ALGORITHM DESIGN, ADDISON-WESLEY, 2005 |
BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2024-08-21]
