ELEMENTI DI TEORIA DELLA COMPUTAZIONE

Informatica ELEMENTI DI TEORIA DELLA COMPUTAZIONE

0512100018
DIPARTIMENTO DI INFORMATICA
CORSO DI LAUREA
INFORMATICA
2017/2018



OBBLIGATORIO
ANNO CORSO 3
ANNO ORDINAMENTO 2015
SECONDO SEMESTRE
CFUOREATTIVITÀ
648LEZIONE
324LABORATORIO


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

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.
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 E DELLA CAPACITÀ DI APPLICARE TALI CONCETTI, AVVERRÀ ATTRAVERSO 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. LA PROVA SCRITTA POTRÀ ESSERE SOSTITUITA DAL SUPERAMENTO DI DUE PROVE INTERCORSO.

I CRITERI DI VALUTAZIONE RIGUARDANO LA COMPLETEZZA, LA CORRETTEZZA E LA CHIAREZZA ESPOSITIVA.
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: 2019-05-14]