Metodi matematici per l'informatica (2010/2011)

Codice insegnamento 4S02855 Docente Roberto Giacobazzi Coordinatore Roberto Giacobazzi crediti 6 Corsi di studio in cui è offerto Laurea magistrale in Matematica Settore disciplinare INF/01 - INFORMATICA Lingua di erogazione Italiano Periodo I semestre dal 4-ott-2010 al 31-gen-2011. Pagina Web http://profs.sci.univr.it/~giaco/metodi.html

Pagine collegate Avvisi relativi al corso Seminari relativi al corso

Orario lezioni

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.

Modalita d'esame

Progetto collettivo da elaborare in gruppo e discutere singolarmente.

Statistiche per i requisiti di trasparenza (Attuazione Art. 2 del D.M. 31/10/2007, n. 544)

Valori relativi all'AA 2010/2011 calcolati su un campione di 7 iscritti. I valori in percentuale sono arrotondati al numero intero più vicino.