Informatica | ELEMENTI DI TEORIA DELLA COMPUTAZIONE

cod. 0512100018

ELEMENTI DI TEORIA DELLA COMPUTAZIONE

	0512100018
	DIPARTIMENTO DI INFORMATICA
	CORSO DI LAUREA
	INFORMATICA
	2014/2015

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 E LA SINTESI 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 ED INTRAPRENDERE STUDI PIÙ AVANZATI.

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 E LA SINTESI 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 ED INTRAPRENDERE STUDI PIÙ AVANZATI.

	Prerequisiti
	NOZIONI DI BASE DI MATEMATICA DISCRETA , LOGICA E ALGORITMI.

	Contenuti
	MODELLI DI COMPUTAZIONE: AUTOMI FINITI E MACCHINE DI TURING. IL CONCETTO DI COMPUTABILITÀ: LINGUAGGI DECIDIBILI E LINGUAGGI INDECIDIBILI. IL CONCETTO DI COMPLESSITÀ: LE CLASSI P ED NP, LA NOZIONE DI NP-COMPLETEZZA.