Informatica | ELEMENTI DI TEORIA DELLA COMPUTAZIONE

cod. 0512100018

ELEMENTI DI TEORIA DELLA COMPUTAZIONE

	0512100018
	DIPARTIMENTO DI INFORMATICA
	CORSO DI LAUREA
	INFORMATICA
	2013/2014

CURRICULUM METODOLOGICO

	OBBLIGATORIO
	ANNO CORSO 3
	ANNO ORDINAMENTO 2008
	SECONDO SEMESTRE

MODULI

	SSD	CFU	ORE	ATTIVITÀ	TIPO DI ATTIVITÁ FORMATIVA
	INF/01	9	72	LEZIONE	CARATTERIZZANTE

	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.

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]