ELEMENTI DI TEORIA DELLA COMPUTAZIONE

Informatica ELEMENTI DI TEORIA DELLA COMPUTAZIONE

0512100018
DIPARTIMENTO DI INFORMATICA
CORSO DI LAUREA
INFORMATICA
2015/2016



OBBLIGATORIO
ANNO CORSO 3
ANNO ORDINAMENTO 2008
SECONDO SEMESTRE
CFUOREATTIVITÀ
972LEZIONE


Obiettivi
CONOSCENZA E CAPACITÀ DI COMPRENSIONE:

OBIETTIVO DEL CORSO È L’ACQUISIZIONE DA PARTE DELLO STUDENTE A) DEL CONCETTO DI MODELLO ASTRATTO DI COMPUTAZIONE, B) DELLA DISTINZIONE TRA I CONCETTI DI COMPUTABILE E NON COMPUTABILE, C) DEL CONCETTO DI COMPLESSITÀ E DELLA DISTINZIONE TRA PROBLEMA TRATTABILE E INTRATTABILE. QUESTI CONCETTI VERRANNO PRESENTATI ATTRAVERSO LO STUDIO DEL MODELLO CLASSICO DELLA MACCHINA DI TURING E DELLE MISURE DI COMPLESSITÀ DI TEMPO.

CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE:

BASANDOSI SULLE CONOSCENZE DESCRITTE NEL PRECEDENTE PARAGRAFO, SI INTENDE RENDERE LO STUDENTE CAPACE DI REALIZZARE L’ANALISI (DESCRIZIONE DEL COMPORTAMENTO) E LA SINTESI (PROGETTO) DI SEMPLICI MODELLI DI COMPUTAZIONE PER LA SOLUZIONE DI PROBLEMI DI DECISIONE.

AUTONOMIA DI GIUDIZIO:

ALLA FINE DEL CORSO GLI STUDENTI DOVREBBERO AVER ACQUISITO CAPACITÀ DI GIUDIZIO IN AUTONOMIA NELLA SCELTA DEL MODELLO APPROPRIATO PER LA SOLUZIONE DI UN PROBLEMA.

ABILITÀ COMUNICATIVE:
DURANTE LE LEZIONI FRONTALI, SARANNO PRESENTATI ESEMPI PER STIMOLARE GLI STUDENTI A “COSTRUIRE” CON IL DOCENTE CONCETTI E DIMOSTRAZIONI. DURANTE LE ESERCITAZIONI GLI STUDENTI SARANNO STIMOLATI A COMUNICARE SOLUZIONI ALTERNATIVE.

CAPACITÀ DI APPRENDIMENTO:

AL TERMINE DEL CORSO LO STUDENTE DOVREBBE AVER ACQUISITO LE ABILITÀ DI APPRENDIMENTO NECESSARIE PER POTER AGGIORNARE E CONSOLIDARE LE PROPRIE CONOSCENZE NELL’AMBITO DELLA TEORIA DELLA COMPUTAZIONE, APPLICARE QUESTE CONOSCENZE A CONTESTI DIVERSI E INTRAPRENDERE STUDI PIÙ AVANZATI CON UN BUON GRADO DI SICUREZZA E AUTONOMIA.
Prerequisiti
NOZIONI DI BASE DI MATEMATICA DISCRETA, LOGICA E ALGORITMI.
Contenuti
MODELLI DI COMPUTAZIONE: AUTOMI FINITI, LINGUAGGI REGOLARI, MACCHINE DI TURING. IL CONCETTO DI COMPUTABILITÀ: LINGUAGGI DECIDIBILI, LINGUAGGI INDECIDIBILI, RIDUZIONI, TEOREMA DI RICE. IL CONCETTO DI COMPLESSITÀ: LE CLASSI P ED NP, LA NOZIONE DI NP-COMPLETEZZA, RIDUZIONI POLINOMIALI. ESEMPI DI LINGUAGGI NP-COMPLETI.

Metodi Didattici
LEZIONI FRONTALI COMPRENSIVE DI ESERCITAZIONI.
Verifica dell'apprendimento
PROVA SCRITTA ED ESAME ORALE.
Testi
1.M. SIPSER, INTRODUCTION TO THE THEORY OF COMPUTATION, COURSE TECHNOLOGY, SECOND EDITION, 2005.
2. J. HOPCROFT, R. MOTWANI, J. ULLMAN , AUTOMI, LINGUAGGI E CALCOLABILITÀ, ADDISON WESLEY PEARSON EDUCATION ITALIA S.R.L, TERZA EDIZIONE, 2009.
Altre Informazioni
PER IL PROGRAMMA DETTAGLIATO E ULTERIORI INFORMAZIONI SI VEDA ALL'URL
HTTP://WWW.UNISA.IT/DIPARTIMENTI/DIP_INFORMATICA/DIDATTICA/DOCENTI/DEFELICE/INDEX
  BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2016-09-30]