Fondamenti dell'informatica (2015/2016)

Codice insegnamento
4S00005
Docente
Isabella Mastroeni
Coordinatore
Isabella Mastroeni
crediti
6
Settore disciplinare
INF/01 - INFORMATICA
Lingua di erogazione
Italiano
Periodo
I semestre dal 1-ott-2015 al 29-gen-2016.

Orario lezioni

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

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 (28h): 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à (34h): 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 in 4 appelli con prova intermedia. Gli appelli sono così distribuiti: 1 prova intermedia durante il corso, 2 appelli nella Sessione Straordinaria a fine corso, 1 Appello nella Sessione Estiva, 1 appello nella Sessione Autunnale. Prova orale obbligatoria per voti superiori a 26.

Opinione studenti frequentanti - 2015/2016


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.65% 21 3
Respinti 32.73%
Assenti 22.66%
Ritirati 12.94%
Annullati --
Distribuzione degli esiti positivi
18 19 20 21 22 23 24 25 26 27 28 29 30 30 e Lode
36.3% 15.9% 10.2% 7.9% 6.8% 2.2% 3.4% 3.4% 10.2% 0.0% 0.0% 1.1% 1.1% 1.1%

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