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 2025 al 30 gen 2026.

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

Matematica di Base, Logica, 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,
Godelizzazione,
Universalità e Teorema s-m-n,
Problemi risolubili e non: problema della terminazione,
Metaprogrammazione: compilazione,
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:
L'insegnamento è suddiviso in due parti, ciascuna delle quali può essere sostenuta separatamente (anche in appelli diversi) in quanto ogni esame permette di affrontare le singole parti separatamente.
Ogni esame scritto sarà preceduto da un pretest. Se la valutazione di tale pretest sarà maggiore o uguale a 18, si può scegliere di registrare 18 o di procedere con l'esame vero e proprio, la cui valutazione terrà conto del risultato del pretest.
Prova orale (possibile solo sull'intero esame):
La prova orale è facoltativa ma è possibile solo per chi ottiene una valutazione complessiva maggiore o uguale a 26, diventa obbligatoria per registrare voti superiori a 26, ovvero, senza sostenere una prova orale, il massimo voto registrabile è 26.

Criteri di valutazione

Correttezza matematica ed informatica dei contenuti scritti e degli esercizi svolti e proprietà di linguaggio.
Obiettivo del pretest è quello di accertare le conoscenze minime necessarie al superamento dell'esame.
Obiettivo della prova scritta è quello di accertare la capacità di applicare le conoscenze acquisite durante il corso nella risoluzione di esercizi.
Obiettivo della prova orale è quello di accertare un'avanzata conoscenza e comprensione dei contenuti che permetta un'analisi critica e una rielaborazione dei concetti e dei risultati studiati, anche mediante l’accertamento della conoscenza di teoremi e dimostrazioni.

Criteri di composizione del voto finale

Valutazione (da 0 a 3) del pretest sommato al voto in trentesimi (rapportato a 28) ottenuto come media delle valutazioni in trentesimi ottenute nelle due parti dell'esame (L’esame si ritiene superato se il voto risultante complessivo è maggiore o uguale a 18).

Lingua dell'esame

italiano