Fondamenti dell'informatica (2007/2008)

Corso a esaurimento

Codice insegnamento
4S00005
Docente
Roberto Giacobazzi
crediti
6
Altri corsi di studio in cui è offerto
Settore disciplinare
INF/01 - INFORMATICA
Lingua di erogazione
Italiano
Periodo
1° Q dal 3-ott-2007 al 4-dic-2007.
Pagina Web
http://profs.sci.univr.it/~giaco/fondamenti3.html

Orario lezioni

1° Q
Giorno Ora Tipo Luogo Note
lunedì 9.30 - 11.30 lezione Aula D dal 20-nov-2007  al 4-dic-2007
mercoledì 13.30 - 15.30 lezione Aula B  
giovedì 10.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 e verifica automatica di sistemi, sicurezza e crittografia, i corsi di linguaggi e compilatori, intelligenza artificiale, deduzione automatica, semantica, modelli di calcolo non convenzionali, etc.

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. Voto minimo di ammissione all'orale è 16. L'orale è obbligtorio per i voti di ammissione inferiori al 18 e per ottenere un voto complessivo maggiore di 24. Il voto dello scritto è valido per l'ammissione all'orale solo nell'arco dell'Anno Accademico di riferimento, ovvero una volta scaduto tale termine (ultimo appello di Ottobre) lo scritto deve essere risostenuto al fine di essere ammesso all'orale. Le date degli orali sono espsote al momento della correzione degli scritti.

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 39.77% 21 2
Respinti --
Assenti 46.40%
Ritirati 13.81%
Annullati --
Distribuzione degli esiti positivi
18 19 20 21 22 23 24 25 26 27 28 29 30 30 e Lode
22.2% 8.3% 19.4% 15.2% 12.5% 4.1% 15.2% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 2.7%

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