Fondamenti dell'informatica (2010/2011)

Codice insegnamento
4S00005
Docente
Roberto Giacobazzi
Coordinatore
Roberto Giacobazzi
crediti
6
Altri corsi di studio in cui è offerto
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/fondamenti3.html

Orario lezioni

I semestre
Giorno Ora Tipo Luogo Note
mercoledì 8.30 - 10.30 lezione Aula C  
giovedì 8.30 - 11.30 lezione Aula F  

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 è strutturato in 2 parti. Nella prima parte viene presentata la teoria degli automi e dei linguaggi formali, teoria a fondamento della descrizione e dell'implementazione dei linguaggi di programmazione. La seconda parte delinea i concetti e la natura dei problemi che ammettono soluzione effettiva, ovvero dei problemi risolvibili mediante calcolatore.

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 ingeneria del software e sicurezza.

Programma

Automi e linguaggi formali (20h): 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à (25h): 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

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 26.26% 21 3
Respinti 15.15%
Assenti 51.01%
Ritirati 6.56%
Annullati 1.01%
Distribuzione degli esiti positivi
18 19 20 21 22 23 24 25 26 27 28 29 30 30 e Lode
25.0% 7.6% 15.3% 7.6% 13.4% 9.6% 13.4% 0.0% 0.0% 0.0% 0.0% 0.0% 3.8% 3.8%

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