Fondamenti dell'informatica (2009/2010)

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 1-ott-2009 al 31-gen-2010.
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 B  
giovedì 9.30 - 12.30 lezione Aula B  

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 ed orale

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 22.85% 24 4
Respinti --
Assenti 74.28%
Ritirati 2.85%
Annullati --
Distribuzione degli esiti positivi
18 19 20 21 22 23 24 25 26 27 28 29 30 30 e Lode
12.5% 0.0% 12.5% 12.5% 0.0% 25.0% 0.0% 0.0% 0.0% 12.5% 0.0% 0.0% 0.0% 25.0%

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