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 dettagliato
- 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)
- Calcolabilità (20h):
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
- Virologia sintetica (15h):
Calcolabilità e metaprogrammazione;
Virologia computazionale.
Modalità d'esame: Progetto collettivo da elaborare in gruppo e discutere singolarmente