Codice insegnamento

4S00005

Docente

Isabella Mastroeni

Coordinatore

Isabella Mastroeni

Crediti

6

Lingua di erogazione

Italiano

Settore Scientifico Disciplinare (SSD)

INF/01 - INFORMATICA

Periodo

I semestre dal 1 ott 2024 al 31 gen 2025.

Corsi Singoli

Autorizzato

Orario Lezioni Moodle Seminari 0

Obiettivi di apprendimento

Il corso si propone di fornire gli strumenti formali e le nozioni fondamentali per studiare problemi trattabili e non mediante calcolatore. Il corso mira quindi a dare competenze nell’ambito dell’informatica teorica e dei linguaggi di programmazione. Al termine del corso lo studente dovrà dimostrare di avere conoscenze e capacità di comprensione di temi avanzati riguardanti i problemi risolubili mediante calcolatore; avere capacità di applicare le co- 4 noscenze acquisite e capacità di comprensione al fine di risolvere problemi di calcolabilità nel proprio campo di studi; saper sviluppare le competenze necessarie per intraprendere studi successivi con un alto grado di autonomia.

Prerequisiti e nozioni di base

Analisi matematica, Logica ed Algebra, Programmazione e Algoritmi e strutture dati.

Programma

Il corso è strutturato in 2 parti.
Automi e linguaggi formali):
Linguaggi e grammatiche,
Automi a stati finiti e linguaggi regolari,
Linguaggi liberi da contesto, forme normali e automi a pila,
Classificazione di Chomsky (cenni).
Teoria della Calcolabilità:
Nozione intuitiva di algoritmo,
Modelli formali per il calcolo: Macchine di Turing/funzioni ricorsive/programmi While,
Tesi di Church,
Goedelizzazione,
Universalità e Teorema s-m-n,
Problemi solubili e non: problema della terminazione,
Metaprogrammazione: compliazione,
interpretazione e specializzazione,
Insiemi ricorsivi e r.e.,
Teoremi di Ricorsione e Teorema di Rice,
Riducibilità funzionale: Insiemi completi, creativi e produttivi.

Bibliografia

Modalità didattiche

Lezioni ed esercitazione frontali.

Modalità di verifica dell'apprendimento

Esame scritto in 4 appelli con prova intermedia. Gli appelli sono così distribuiti: 1 prova intermedia durante il corso, 2 appelli nella Sessione Straordinaria a fine corso, 1 Appello nella Sessione Estiva, 1 appello nella Sessione Autunnale. Ogni esame è suddiviso in due parti superabili separatamente e il voto complessivo, della prova scritta, è dato dalla media matematica delle valutazioni in 30esimi ottenute nelle due parti. L’esame si ritiene superato se la media delle parti è maggiore o uguale a 18. Ogni valutazione rimane valida per l’intero anno accademico in corso.
Prova orale obbligatoria per ottenere voti superiori a 26, facoltativa altrimenti. Ovvero, ogni voto viene verbalizzato senza prova orale fino ad un massimo di 26. Obiettivo della prova scritta è quello di accertare la comprensione dei contenuti e la capacità di applicare tali contenuti nella risoluzione di esercizi in cui si devono principalmente riconoscere e classificare linguaggi (regolari o liberi dal contesto) e insiemi (ricorsività e completezza) mediante l’utilizzo degli strumenti formali di dimostrazione forniti durante il corso.
Obiettivo della prova orale è quello di accertare una avanzata comprensione dei contenuti che permette una analisi critica e una rielaborazione dei concetti e dei risultati studiati, anche mediante l’accertamento della conoscenza di teoremi e dimostrazioni.

Criteri di valutazione

Correttezza matematica ed informatica degli esercizi svolti e proprietà di linguaggio.

Criteri di composizione del voto finale

50% Prima parte e 50% Seconda parte

Lingua dell'esame

Italiano