Fondamenti dell'informatica (2017/2018)

Codice insegnamento
4S00005
Docenti
Roberto Giacobazzi, Mila Dalla Preda
Coordinatore
Roberto Giacobazzi
crediti
6
Settore disciplinare
INF/01 - INFORMATICA
Lingua di erogazione
Italiano
Periodo
I sem. dal 2-ott-2017 al 31-gen-2018.
Pagina Web
http://profs.scienze.univr.it/~giaco/styled-19/index.html

Orario lezioni

Vai all'orario delle lezioni

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 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 conoscenze acquisite 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
P. Odifreddi Classical recursion theory Elsevier North-Holland 1989
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
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.

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

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