Fondamenti dell'informatica (2013/2014)

Codice insegnamento
4S00005
Docenti
Roberto Giacobazzi, Isabella Mastroeni
Coordinatore
Roberto Giacobazzi
crediti
6
Settore disciplinare
INF/01 - INFORMATICA
Lingua di erogazione
Italiano
Periodo
I semestre dal 1-ott-2013 al 31-gen-2014.
Pagina Web
http://profs.sci.univr.it/~giaco/fondamenti3.html

Orario lezioni

I semestre
Giorno Ora Tipo Luogo Note
mercoledì 8.30 - 11.30 lezione Aula C  
giovedì 9.30 - 11.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.

Testi di riferimento
Autore Titolo Casa editrice Anno ISBN Note
N. Jones Computability and Complexity MIT Press 1997
Christos H. Papadimitriou Computational complexity Addison Wesley 1994 0201530821
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman Introduction to Automata Theory, Languages and Computation (Edizione 2) Addison-Wesley 2000 0201441241
Michael Sipser Introduction to the Theory of Computation PWS 1997 053494728X
H. Rogers Theory of recursive functions and effective computability MIT Press 1988

Modalità d'esame

Esame scritto in 4 appelli con prova intermedia. Gli appelli sono così distribuiti: 1 prova intermedia durante il corso, 1 appello nella Sessione Straordinaria a fine corso, 1 Appello nella Sessione Estiva, 1 appello nella Sessione Autunnale.

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 31.81% 21 2
Respinti --
Assenti 68.18%
Ritirati --
Annullati --
Distribuzione degli esiti positivi
18 19 20 21 22 23 24 25 26 27 28 29 30 30 e Lode
42.8% 14.2% 0.0% 0.0% 0.0% 14.2% 28.5% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0%

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