Metodi matematici per l'informatica (2010/2011)

Codice insegnamento
4S02855
Docente
Roberto Giacobazzi
Coordinatore
Roberto Giacobazzi
crediti
6
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

Orario lezioni

I semestre
Giorno Ora Tipo Luogo Note
lunedì 9.30 - 11.30 lezione Aula M dal 11-ott-2010  al 31-gen-2011
venerdì 13.30 - 15.30 lezione Aula M  

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.

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

Statistiche esiti
Esiti Esami Esiti Percentuali Media voti Deviazione Standard
Positivi 85.71% 29 0
Respinti --
Assenti 14.28%
Ritirati --
Annullati --
Distribuzione degli esiti positivi
18 19 20 21 22 23 24 25 26 27 28 29 30 30 e Lode
0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 33.3% 0.0% 33.3% 33.3%

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