Fondamenti dell'informatica (2020/2021)

Codice insegnamento
4S00005
Docente
Roberto Giacobazzi
Coordinatore
Roberto Giacobazzi
crediti
6
Settore disciplinare
INF/01 - INFORMATICA
Lingua di erogazione
Italiano
Sede
VERONA
Periodo
I semestre dal 1-ott-2020 al 29-gen-2021.

Orario lezioni

Vai all'orario delle lezioni

Obiettivi formativi

Il corso si propone 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 del corso lo studente dovrà dimostrare di avere conoscenze e capacità di comprensione di temi avanzati riguardanti i problemi risolubili mediante calcolatore; avere capacità di applicare le co- 4 noscenze acquisite e capacità di comprensione al fine di risolvere problemi di calcolabilità 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
Dovier A. Giacobazzi R. Fondamenti dell'Informatica: Linguaggi Formali, Calcolabilità e Complessità. Bollati Boringhieri 2020 9788833933795
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman Introduction to Automata Theory, Languages and Computation (Edizione 2) Addison-Wesley 2000 0201441241
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 ottenere voti superiori a 26 (incluso), facoltativa altrimenti. Ovvero, ogni voto viene verbalizzato senza prova orale fino ad un massimo di 25.

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.