Codice insegnamento

4S00005

Docenti

Isabella Mastroeni, Mila Dalla Preda

Coordinatore

Isabella Mastroeni

Crediti

6

Lingua di erogazione

Italiano

Settore Scientifico Disciplinare (SSD)

INF/01 - INFORMATICA

Periodo

I sem. dal 3 ott 2016 al 31 gen 2017.

Moodle Seminari 0

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 dell’insegnamento lo studente dovrà dimostrare di avere conoscenze e capacità di comprensione di temi avanzati; avere capacità di applicare le conoscenze 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 voti superiori a 26, facoltativa altrimenti.

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.