Luisa GARGANO | ELEMENTI DI TEORIA DELLA COMPUTAZIONE

cod. 0512100018

ELEMENTI DI TEORIA DELLA COMPUTAZIONE

	0512100018
	DIPARTIMENTO DI INFORMATICA
	CORSO DI LAUREA
	INFORMATICA
	2024/2025

PERCORSO COMUNE

	OBBLIGATORIO
	ANNO CORSO 3
	ANNO ORDINAMENTO 2017
	SECONDO SEMESTRE

MODULI

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

DOCENTI

	LUISA GARGANO T Curriculum
	GIANLUCA DE MARCO Curriculum

	Obiettivi
	OBIETTIVO GENERALE IL CORSO HA L’OBIETTIVO DI FORNIRE LE BASI TEORICHE FORMALI DEL CONCETTO DI PROBLEMA COMPUTABILE TRAMITE PROCEDURA EFFETTIVA 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 COMPRENSIONELO STUDENTE SARÀ IN GRADO DI: - ANALIZZARE IL COMPORTAMENTO DI AUTOMI FINITI E MACCHINE DI TURING; - ANALIZZARE SEMPLICI PROBLEMI DI DECISIONE (PROBLEMI CON RISPOSTA SÌ/NO) E PROGETTARE MODELLI DI COMPUTAZIONE PER LA RELATIVA SOLUZIONE, SE TALI MODELLI ESISTONO, VALUTANDONE LE RISORSE UTILIZZATE. AUTONOMIA DI GIUDIZIO LO STUDENTE ACQUISIRÀ CAPACITÀ DI GIUDIZIO IN AUTONOMIA SULLA COMPLESSITÀ DI UN PROBLEMA E DELLA SCELTA DEL MODELLO APPROPRIATO PER LA SOLUZIONE DI ESSO, SE TALE MODELLO ESISTE. ABILITÀ COMUNICATIVE DURANTE LE LEZIONI SARANNO PRESENTATI ESEMPI PER STIMOLARE GLI STUDENTI A “COSTRUIRE” CON IL DOCENTE CONCETTI E DIMOSTRAZIONI. INOLTRE, GLI STUDENTI SARANNO STIMOLATI A COMUNICARE SOLUZIONI A ESERCIZI PROPOSTI, CON PROPRIETÀ DI LINGUAGGIO E CORRETTO USO DELLA TERMINOLOGIA. CAPACITÀ DI APPRENDIMENTO LO STUDENTE ACQUISIRÀ 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

OBIETTIVO GENERALE

IL CORSO HA L’OBIETTIVO DI FORNIRE LE BASI TEORICHE FORMALI DEL CONCETTO DI PROBLEMA COMPUTABILE TRAMITE PROCEDURA EFFETTIVA

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 COMPRENSIONELO STUDENTE SARÀ IN GRADO DI:

- ANALIZZARE IL COMPORTAMENTO DI AUTOMI FINITI E MACCHINE DI TURING;
- ANALIZZARE SEMPLICI PROBLEMI DI DECISIONE (PROBLEMI CON RISPOSTA SÌ/NO) E PROGETTARE MODELLI DI COMPUTAZIONE PER LA RELATIVA SOLUZIONE, SE TALI MODELLI ESISTONO, VALUTANDONE LE RISORSE UTILIZZATE.

AUTONOMIA DI GIUDIZIO

LO STUDENTE ACQUISIRÀ CAPACITÀ DI GIUDIZIO IN AUTONOMIA SULLA COMPLESSITÀ DI UN PROBLEMA E DELLA SCELTA DEL MODELLO APPROPRIATO PER LA SOLUZIONE DI ESSO, SE TALE MODELLO ESISTE.
ABILITÀ COMUNICATIVE

DURANTE LE LEZIONI SARANNO PRESENTATI ESEMPI PER STIMOLARE GLI STUDENTI A “COSTRUIRE” CON IL DOCENTE CONCETTI E DIMOSTRAZIONI. INOLTRE, GLI STUDENTI SARANNO STIMOLATI A COMUNICARE SOLUZIONI A ESERCIZI PROPOSTI, CON PROPRIETÀ DI LINGUAGGIO E CORRETTO USO DELLA TERMINOLOGIA.
CAPACITÀ DI APPRENDIMENTO

LO STUDENTE ACQUISIRÀ 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

	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] MACCHINA DI TURING DETERMINISTICA A NASTRO SINGOLO. IL LINGUAGGIO RICONOSCIUTO DA UNA MACCHINA DI TURING. [12 ORE] • IL CONCETTO DI COMPUTABILITÀ: FUNZIONI CALCOLABILI, VARIANTI DI MACCHINE DI TURING E LORO EQUIVALENZA, LINGUAGGI DECIDIBILI E LINGUAGGI TURING RICONOSCIBILI. LINGUAGGI DECIDIBILI E LINGUAGGI INDECIDIBILI. IL PROBLEMA DELLA FERMATA. RIDUZIONI, TEOREMA DI RICE. [20 ORE] • 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. [16 ORE]

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] MACCHINA DI TURING DETERMINISTICA A NASTRO SINGOLO. IL LINGUAGGIO RICONOSCIUTO DA UNA MACCHINA DI TURING. [12 ORE]
• IL CONCETTO DI COMPUTABILITÀ: FUNZIONI CALCOLABILI, VARIANTI DI MACCHINE DI TURING E LORO EQUIVALENZA, LINGUAGGI DECIDIBILI E LINGUAGGI TURING RICONOSCIBILI. LINGUAGGI DECIDIBILI E LINGUAGGI INDECIDIBILI. IL PROBLEMA DELLA FERMATA. RIDUZIONI, TEOREMA DI RICE. [20 ORE]
• 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. [16 ORE]

	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. SE DOVESSERO PERDURARE LE CONDIZIONI DI EMERGENZA COVID-19 E LE RESTRIZIONI AD ESSE CONNESSE, LE SUDDETTE PROVE POTREBBERO ESSERE SVOLTE IN MODALITÀ TELEMATICA A DISTANZA. 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, È 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.

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. SE DOVESSERO PERDURARE LE CONDIZIONI DI EMERGENZA COVID-19 E LE RESTRIZIONI AD ESSE CONNESSE, LE SUDDETTE PROVE POTREBBERO ESSERE SVOLTE IN MODALITÀ TELEMATICA A DISTANZA.
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, È 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. HOPCROFT, R. MOTWANI, J. ULLMAN, AUTOMI, LINGUAGGI E CALCOLABILITÀ, ADDISON WESLEY PEARSON EDUCATION ITALIA S.R.L, TERZA EDIZIONE, 2009. ULTERIORI MATERIALI E SUPPORTI NECESSARI PER AFFRONTARE LO STUDIO E LA GESTIONE DELLA PROVA DI VERIFICA POTRANNO ESSERE FORNITI TRAMITE LA PIATTAFORMA E-LEARNING ALL’INDIRIZZO HTTP://ELEARNING.INFORMATICA.UNISA.IT/ E LE PAGINE WEB DEI DOCENTI HTTPS://DOCENTI.UNISA.IT/001367/HOME HTTPS://DOCENTI.UNISA.IT/023039/HOME

Testi

• M. SIPSER, INTRODUZIONE ALLA TEORIA DELLA COMPUTAZIONE, APOGEO, 2016
• J. HOPCROFT, R. MOTWANI, J. ULLMAN, AUTOMI, LINGUAGGI E CALCOLABILITÀ, ADDISON WESLEY PEARSON EDUCATION ITALIA S.R.L, TERZA EDIZIONE, 2009.

ULTERIORI MATERIALI E SUPPORTI NECESSARI PER AFFRONTARE LO STUDIO E LA GESTIONE DELLA PROVA DI VERIFICA POTRANNO ESSERE FORNITI TRAMITE LA PIATTAFORMA E-LEARNING ALL’INDIRIZZO HTTP://ELEARNING.INFORMATICA.UNISA.IT/ E LE PAGINE WEB DEI DOCENTI

HTTPS://DOCENTI.UNISA.IT/001367/HOME

HTTPS://DOCENTI.UNISA.IT/023039/HOME

	Altre Informazioni
	ULTERIORI MATERIALI E SUPPORTI NECESSARI PER AFFRONTARE LO STUDIO E LA GESTIONE DELLA PROVA DI VERIFICA POTRANNO ESSERE FORNITI TRAMITE LA PIATTAFORMA E-LEARNING ALL’INDIRIZZO HTTP://ELEARNING.INFORMATICA.UNISA.IT/ E LE PAGINE WEB DEI DOCENTI HTTPS://DOCENTI.UNISA.IT/001367/HOME HTTPS://DOCENTI.UNISA.IT/023039/HOME

BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2024-11-18]

Luisa GARGANO | ELEMENTI DI TEORIA DELLA COMPUTAZIONE