Obiettivi formativi

Scopo del corso è quello 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 conoscenze acquisite e capacità di comprensione al fine di risolvere problemi nel proprio campo di studi, saper sviluppare le competenze necessarie per intraprendere studi successivi con un alto grado di autonomia.

Programma

Propedeuticità consigliate: Il corso ha come prerequisiti i corsi del I e II anno. Esso è propedeutico per tutti i corsi di informatica teorica, in particolar modo per i corsi di complessità, analisi statica e protezione, sicurezza e crittografia, i corsi di linguaggi e compilatori, intelligenza artificiale, deduzione automatica, semantica, modelli di calcolo non convenzionali, per i corsi dell'indirizzo sistemi embedded ed ingegneria del software e sicurezza.


Il corso è strutturato in 2 parti.

Automi e linguaggi formali (28h):
Linguaggi e grammatiche,
Automi a stati finiti e linguaggi regolari,
Linguaggi liberi da contesto, forme normali e automi a pila,
Classificazione di Chomsky (cenni).

Calcolabilità (34h):
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.

Modalità d'esame

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 (incluso), facoltativa altrimenti. Ovvero, ogni voto viene verbalizzato senza prova orale fino ad un massimo di 25.

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.