Fondamenti dell'informatica (2016/2017)

Codice insegnamento
4S00005
Docenti
Isabella Mastroeni, Mila Dalla Preda
Coordinatore
Isabella Mastroeni
crediti
6
Settore disciplinare
INF/01 - INFORMATICA
Lingua di erogazione
Italiano
Periodo
I sem. dal 3-ott-2016 al 31-gen-2017.

Orario lezioni

I sem.
Giorno Ora Tipo Luogo Note
lunedì 8.30 - 11.30 lezione Aula B  
giovedì 8.30 - 10.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 mira quindi a dare competenze nell’ambito dell’informatica teorica e dei linguaggi di programmazione.
Al termine dell’insegnamento lo studente dovrà dimostrare di avere conoscenze e capacità di comprensione di temi avanzati; avere capacità di applicare le conoscenze e capacità di comprensione al fine di risolvere problemi nel proprio campo di studi; saper sviluppare le competenze necessarie per intraprendere studi successivi con un alto grado di autonomia.

Programma

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

Il corso è strutturato in 2 parti.

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.

Testi di riferimento
Autore Titolo Casa editrice Anno ISBN Note
N. Jones Computability and Complexity MIT Press 1997
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, 2 appelli nella Sessione Straordinaria a fine corso, 1 Appello nella Sessione Estiva, 1 appello nella Sessione Autunnale. Ogni esame è suddiviso in due parti superabili separatamente e il voto complessivo, della prova scritta, è dato dalla media matematica delle valutazioni in 30esimi ottenute nelle due parti. L’esame si ritiene superato se la media delle parti è maggiore o uguale a 18. Ogni valutazione rimane valida per l’intero anno accademico in corso.

Prova orale obbligatoria per voti superiori a 26, facoltativa altrimenti.

Obiettivo della prova scritta è quello di accertare la comprensione dei contenuti e la capacità di applicare tali contenuti nella risoluzione di esercizi in cui si devono principalmente riconoscere e classificare linguaggi (regolari o liberi dal contesto) e insiemi (ricorsività e completezza) mediante l’utilizzo degli strumenti formali di dimostrazione forniti durante il corso.
Obiettivo della prova orale è quello di accertare una avanzata comprensione dei contenuti che permette una analisi critica e una rielaborazione dei concetti e dei risultati studiati, anche mediante l’accertamento della conoscenza di teoremi e dimostrazioni.

Opinione studenti frequentanti - 2015/2016


Statistiche per i requisiti di trasparenza (Attuazione Art. 2 del D.M. 31/10/2007, n. 544)

I dati relativi all'AA 2016/2017 non sono ancora disponibili