Obiettivi formativi

Scopo del corso è quello di fornire gli strumenti formali e le nozioni fondamentali per studiare problemi trattabili e non mediante calcolatore. Viene presentata la teoria degli automi e dei linguaggi formali, teoria a fondamento della descrizione e dell'implementazione dei linguaggi di programmazione, affrontando gli aspetti espressivi di vari sistemi di calcolo via via più complessi. Viene inoltre trattata la natura dei problemi che ammettono soluzione effettiva, ovvero dei problemi risolvibili mediante calcolatore. Verranno inoltre trattate tematiche legate alla virologia computazione, al fine di veicolare le tematiche legate alla metaprogrammaizione attraverso un interessante esperimento didattico fornendo agli allievi una chiave di lettura della calcolabilità che permetterà al didatta futuro di agganciare l'interesse degli studenti attraverso la comprensione profonda di un fenomeno ampiamente noto, quotidianamente visibile ed empiricamente stimabile come quello della sicurezza informatica.

Programma

Automi e linguaggi formali (15h):
Linguaggi e grammatiche
Automi a stati finiti e linguaggi regolari
Linguaggi liberi da contesto, forme normali e automi a pila
Classificazione di Chomsky (cenni)
Nozione intuitiva di algoritmo
Modelli formali per il calcolo:
Macchine di Turing/funzioni ricorsive/programmi While
Aritmetica primitiva e programmazione: funzione di Ackermann;
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
Calcolabilità e metaprogrammazione;
Virologia computazionale.

Modalità d'esame

Progetto collettivo da elaborare in gruppo e discutere singolarmente.